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);};
The only difference between Node<T> and DoublyNode<T> is the existence of the Previous pointer (as well as the data type name absolutely). By using this new DoublyNode data type, we are going to refactor the preceding LinkedList ADT into the DoublyLinkedList ADT.