Double Linked List

Double Linked List Demonstration

The Double Linked List is a variation on the Single Linked list

to make the conversion add another pointer to the class, it is generally called tail

it points to the last node in the sequence

now that there is a ponter to the first node (head) and the last node (tail)

we can start to traverse the list at both ends.

Each node also needs a second pointer called previous  prev for short

now each node has a pointer to not only the next node in the sequence but also the previous node.

if you take a look at this image from the interactive demo you will see a visual representation of the list

you can traverse the list front to back exactly the same as you would a Single Linked List 

DLinkedList * tmp = head;
while ( tmp != nullptr )
   cout << tmp->data  << endl;
   tmp = tmp->next;

but you can now traverse it back to front as well

DLinkedList * tmp = tail;
while ( tmp != nullptr )
   cout << tmp->data  << endl;
   tmp = tmp->prev;

Sadly insertion and deletion is more complicated as now you have more pointers to set and keep track of

you can use the interactive demo to see each specific change to the pointers in action