A linked list is a data structure that consists of a chain of nodes, where each node contains some data and a pointer to the next node in the list.
The first node in a linked list is referred to as the Head whilst the last node is referred to as the Tail. We can reference the position of each node in a linked list similarly to the way we reference position in arrays, where the Head has an index of zero. The tail of a linked list always points to null.
The example below shows a simple linked list containing integers.
It is worth noting that each node will only reference the following node, and not the node(s) that came before it. This means that a linked list can only be transversed in one direction.
Advantages
- Elements can be easily added or removed without reorganising the entire structure.
- Dynamic size, that is to say that the linked list can grow or shrink on demand.
- No wasted memory at run time, as only the amount of memory for the nodes will be used, increasing or decreasing as necessary.
Disadvantages
- Random access is not feasible as one would have to traverse the linked list from the beginning whenever one wants to find a specific node.
- Searching a linked list can be time consuming, having linear time complexity: O(n).
- Traversal is only possible in one direction
Top comments (0)