A linked list is a sequential data structure where every value is encapsulated into a node that links to a next node. If C++ is used, each node must follow a prototype like:
template<typename T>
struct LinkedListNode {
T value;
LinkedListNode* next;
};
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 LinkedList {
...
private:
LinkedListNode<T>* head;
LinkedListNode<T>* tail;
std::size_t size;
};
How values are added to linked list tail:
As you can notice in animation above, by keeping track only of next node, it supports only forward traversal (HEAD to TAIL)! For a complete implementation example, check LinkedList class documentation or its GitHub code.
As a sequential data structure, 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 previous TAIL (if exists) to itself, sets itself as 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-1 is reached, links entry found there to itself, links itself to entry found 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. |
| removeIndex | Loops through the linking chain until POSITION-1 is reached, links entry found to that at POSITION+1, deallocates entry found at POSITION then decrements SIZE. |
| removeValue | Loops through the linking chain keeping track of position. If next entry value matches VALUE by COMPARATOR, deallocates matching entry, links entry at POSITION-1 to that at POSITION+1 then decrements SIZE. |
| isEmpty | Checks if SIZE equals zero |
| size | Gets SIZE value |
Compared to Dynamic Array as List implementation, linked list thus fits a very different profile: