Linked Lists

What Is a Linked List?

A linked list is a data structure that stores a sequence of values the way arrays do, but organises them completely differently underneath. Instead of sitting in one continuous block of memory, each item lives in its own node, and each node points to the location of the next one.

A node has exactly two parts:

• Data — the actual value being stored (a number, a name, a record — anything)
• Pointer — a reference to where the next node lives in memory

The first node is called the head. The last node is called the tail, and its pointer is set to null — a special value meaning "there is nothing after this."

head → [ 12 | •]→ [ 7 | •]→ [ 19 | •]→ [ 3 | null ]

To read the list, you start at the head and follow the pointers one at a time: 12, then 7, then 19, then 3, then null — the signal to stop.

Why Not Just Use an Array?

Arrays store elements in one contiguous block, so the computer can jump straight to any position with simple arithmetic — scores[499] is instant, no matter how large the array is. That is a genuine strength arrays have that linked lists cannot match: reaching the 500th node in a linked list means walking through 499 pointers first, one node at a time, because there is no way to calculate where node 500 sits in memory.

So why bother with linked lists at all? Because arrays pay a different price. In many languages, an array is created with a fixed size, and inserting a new value in the middle means shifting every later element along one slot to make room — an expensive operation as the array grows. Linked lists sidestep this entirely.

Inserting and Deleting

Inserting into a linked list only requires rewriting a couple of pointers — nothing else in the list has to move.

Suppose you want to insert a new node containing 15 between the nodes holding 7 and 19:

Before:  ... → [7 | •] → [19 | •] → ...
Insert 15:  new node [15 | •] created, pointing at 19
Rewire:  [7 | •] now points at [15 | •] instead of [19 | •]
After:   ... → [7 | •] → [15 | •] → [19 | •] → ...

Only two pointers changed. Compare that to an array, where inserting 15 at that position would shift every element from that point onward down by one slot. Deletion works the same way in reverse: to remove a node, you simply point its predecessor directly at its successor, skipping over the node being removed. The old node is left with nothing pointing to it and is eventually cleaned up.

Singly vs Doubly Linked Lists

The list described so far — where each node only knows about the next node — is a singly linked list. You can only travel forward, from head to tail.

A doubly linked list gives every node two pointers: one to the next node and one to the previous node. This roughly doubles the memory used per node, but it means the list can be traversed in either direction, and a node can be deleted using only a reference to itself (since it already knows its neighbour on both sides), without needing to search from the head first.

Where Linked Lists Show Up

Linked lists are not just a classroom exercise — they underpin real systems:

Undo history in some editors is implemented as a linked list of states, where moving backward and forward just means following pointers rather than copying whole snapshots around.

Music or playlist apps often use doubly linked lists so "next track" and "previous track" are both instant operations regardless of playlist length.

Memory allocators inside operating systems track free blocks of memory using linked lists, since free blocks appear and disappear constantly and are rarely stored next to each other.

Browser history with branching (visiting a link, going back, then visiting a different link) is easier to model with linked structures than with a simple array.

Arrays vs Linked Lists — A Quick Comparison

Feature	Array	Linked List
Access item by position	Instant	Must walk from the head
Insert/delete in the middle	Shifts later elements	Rewires a couple of pointers
Memory layout	One contiguous block	Scattered nodes, linked by pointers
Size	Often fixed at creation	Grows and shrinks freely
Extra memory per item	None	One or two pointers per node

Neither structure is "better" in every case — the right choice depends on whether your program does more reading by position or more inserting and deleting.

Key Words

• Node — a single element of a linked list, containing data plus a pointer
• Head — the first node in the list
• Tail — the last node in the list, whose pointer is null
• Null pointer — a pointer that points to nothing, marking the end of the list
• Singly linked list — each node points only to the next node
• Doubly linked list — each node points to both the next and the previous node
• Traversal — visiting each node in order, starting from the head