Building the Doubly Linked List ADT

The Doubly Linked List is almost the same as the Singly Linked List, except the Node used by Doubly Linked List has a Previous pointer instead of only having the Next pointer. The existence of the Previous pointer will make the Doubly Linked List possible to move backwards from Tail to Head. As a result, we can reduce the complexity of the RemoveTail() operation to O(1) instead of O(N), like we have in the Singly Linked List data type. We are going to discuss this further later in this section. As of now, let's prepare the new Node data type.

Refactoring the Node<T> data type

Before we build a Doubly Linked List, we need to add a Previous pointer to the existing Node data type. To avoid any confusion, we will create a new data type named DoublyNode with the following declaration:

template <typename T>
class DoublyNode
{
    public:
        T Value;
DoublyNode<T> * Previous;
        DoublyNode<T> * Next;

        DoublyNode(T value...