Data Structures and Algorithms: Linked Lists

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