Doubly Linked List

• Implement a Doubly Linked List

"Using a vector for small lists is almost always superior to using list." Sutter, Alexandruscu (2005)

A doubly linked list admits traversal from tail to head as well as from head to tail. It is not restricted to either front-end or back-end addition or removal. We may insert a node before or after any other node and remove any node in the list. This kind of list has a more complicated structure than a stack or a queue.

Consider the following example,

// Algorithms - Doubly Linked List
// doubly.cpp

#include <iostream>
using namespace std;

class Data
{
    int data;
public:
    Data(int d = 0) : data(d) {}
    int out() const
    {
        return data;
    }
};

struct Node
{
    Data data;
    Node* next;
    Node* previous;
    Node (const Data& d, Node* n, Node* p) : data(d), next(n), previous(p) {}
};

class DLList
{
    Node* head;
    Node* tail;
    Node* current;
public:
    DLList() : head(NULL), tail(NULL), current(NULL) {}
    ~DLList()
    {
        while (current = head)
        {
            head = head->next;
            delete current;
        }
    }

    void goHead()
    {
        current = head;
    }

    void goNext()
    {
        if (current)
            current = current->next;
    }

    void remove()
    {
        if (current)
        {
            Node* p = current;
            if (current == head)
            {
                head = head->next;
            }
            else
            {
                current->next->previous = current->previous;
                current->previous->next = current->next;
                current = current->next;
            }
            delete p;
        }
    }

    bool end()
    {
        return !current;
    }

    Data get() const
    {
        return current ? current->data : Data();
    }

    void insertBefore(const Data& a)
    {
        if (current)
        {
            Node* p = new (nothrow) Node(a, current, current->previous);
            if (p)
            {
                if (current->previous)
                    current->previous->next = p;
                else
                    head = p;
                current->previous = p;
            }
        }
        else
        {
            Node* p = new (nothrow) Node(a, nullptr, nullptr);
            if (p)
                head = tail = current = p;
        }
    }

    void insertAfter(const Data& a)
    {
        if (current)
        {
            Node* p = new (nothrow) Node(a, current->next, current);

            if (p)
            {
                if (current->next)
                    current->next->previous = p;
                else
                    tail = p;
                current->next = p;
            }
        }
        else
        {
            Node* p = new (nothrow) Node(a, nullptr, nullptr);
            if (p)
                head = tail = current = p;
        }
    }
};

int main ()
{
    DLList r;

    // Insert Data
    r.insertAfter(3);
    r.insertAfter(5);
    r.goHead();
    r.insertAfter(9);
    r.goNext();
    r.insertAfter(8);

    // Display Data
    r.goHead();
    while (!r.end())
    {
        cout << r.get().out() << ' ';
        r.goNext();
    }
    cout << endl;
}

3 9 8 5

The DLList class contains three instance pointers: a pointer to the head of the list, a pointer to the tail of the list and a pointer to the current element. Each node contains two instance pointers: a pointer to the previous node and a pointer to the next node.

The DLList object positions its current pointer through the goHead() and goNext() methods. We can add an element before or after the current one using the insertBefore() or insertBefore() methods and remove the current element using the remove() method. We can extract the data held in the current element through the get() query.