A doubly linked list is a sequential data structure where every value is encapsulated into a node that links to both previous and next node. If C++ is used, each node must follow a prototype like:
template<typename T>
struct DoublyLinkedListNode {
T value;
DoublyLinkedListNode* next;
DoublyLinkedListNode* previous;
};
Taking this linking chain together, nodes (all allocated at random RAM positions) form the appearance of a sequence. In order to make it efficient when writing at both HEAD and TAIL, keeping separate track of these nodes as well as list SIZE is a de-facto requirement! C++:
template<typename T>
class DoublyLinkedList {
...
private:
DoublyLinkedListNode<T>* head;
DoublyLinkedListNode<T>* tail;
std::size_t size;
};
How values are added to doubly linked list tail:
As you can notice in animation above, by keeping track of both previous and next node, it supports both forward and backward traversal (HEAD ⇄ TAIL)! To see a real life implementation example, check DoublyLinkedList class documentation or its GitHub code.
As a sequential data structure, doubly linked list can be used to implement many abstract data types. Let us take its List implementation as an example to understand how it works:
| Operation | Description |
| addToHead | Encapsulates VALUE, links itself to old HEAD (if exists), makes itself HEAD, then increments SIZE. |
| addToTail | Encapsulates VALUE, links old TAIL to itself, makes itself TAIL, then increments SIZE. |
| clear | Loops through the linking chain, dealocates every structure found, resets SIZE to zero. |
| containsIndex | Checks if position is smaller than SIZE. |
| containsValue | Loops through the linking chain and checks if any value of entry equals VALUE by COMPARATOR. |
| emplace | Encapsulates VALUE, loops through the linking chain until POSITION is reached, links entry at POSITION-1 to itself, links itself to entry at POSITION, then increments SIZE. |
| get | Loops through the linking chain and returns value of entry found at POSITION. |
| set | Loops through the linking chain and modifies value of entry found at POSITION with VALUE. |
| removeInHow does it workdex | Loops through the linking chain until POSITION is reached, links entry found at POSITION-1 to that at POSITION+1, deallocates entry found at POSITION then decrements SIZE. |
| removeValue | Loops through the linking chain keeping track of position. If entry value matches VALUE by COMPARATOR makes previous entry link to next entry, deallocates matching entry then decrements SIZE. |
| isEmpty | Checks if SIZE equals zero |
| size | Gets SIZE value |
Compared to Dynamic Array as List implementation, doubly linked list thus fits a very different profile: