Re: Looking for a Simple Doubly Linked List Implementation

[Dennis via Digitalmars-d-learn]

On Friday, 20 September 2019 at 20:26:03 UTC, Ron Tarrant wrote:
If someone could please post a minimal example (if there's 
extra stuff in there, I'll get confused; I'm getting that old, 
dammit) I'd be ever so grateful.

Below is a simple doubly linked list with Garbage Collected 
memory.
It's not performant or complete by any means, just a minimal 
example in D like you wanted.
You probably also want methods for removing nodes or inserting in 
the middle (else why don't you use an array?), I think you can 
think of an implementation for those yourself (or look them up, 
there should be plenty examples online).

If not, just ask again.

```

struct Node(T) {
    private T value;
    private Node!T* next = null;
    private Node!T* previous = null;

    this(T value) {
        this.value = value;
    }
}

struct DoublyLinkedList(T) {
    Node!T* head = null;
    Node!T* tail = null;

    import std.range: isInputRange, ElementType;
    this(R)(R initialList) if (isInputRange!R && is(ElementType!R 
: T)) {
        foreach(elem; initialList) {
            addLast(elem);
        }
    }

    void addFirst(T value) {
        auto n = new Node!T(value);
        if (head !is null) {
            head.previous = n;
        } else {
            tail = n;
        }
        n.next = head;
        head = n;
    }

    void addLast(T value) {
        if (head is null) {
            addFirst(value);
        } else {
            auto n = new Node!T(value);
            tail.next = n;
            n.previous = tail;
            tail = n;
        }
    }

    size_t length() const {
        size_t result = 0;
        for(const(Node!T)* a = head; a !is null; a = a.next) 
result++;
        return result;
    }

    T opIndex(size_t pos) const {
        const(Node!T)* p = head;
        for(; p !is null && pos-- != 0; p = p.next) {}
        return p.value;
    }
}

unittest {
    auto a = DoublyLinkedList!int([10, 20, 30]);
    assert(a[2] == 30);
    assert(a.length == 3);
    a.addFirst(-10);
    a.addLast(100);
    assert(a[0] == -10);
    assert(a.tail.value == 100);
}
```