Skip to main content
Be Bitwise

Linked Lists: Pointers in Action

Arrays, Lists & Data Structures · Coding Fundamentals track

8 min read

In this module

Beyond Contiguous Memory

Arrays are great when you know your data's size upfront and want fast random access. They have one glaring weakness: inserting or removing elements in the middle means shifting half the array. What if you need a structure where insertions and deletions are cheap?

A linked list is a data structure where each element (called a node) contains a value and a pointer to the next node. The nodes don't need to be adjacent in memory; they can sit wherever the allocator stuck them. The pointers thread them together in order.

Each box is a node. The left side holds the data value, and the right side holds the pointer to the next node. The last node's pointer is null, which is how you know you've reached the end of the list.

Singly Linked Lists

In a singly linked list, each node points only to the next node. Traversal goes one way: head to tail.

To reach the element at position 3, you start at the head and follow three pointers. No shortcuts. That's O(n) access time — compare with an array's O(1).

Key Concept

A linked list stores elements in nodes connected by pointers. Nodes can live anywhere in memory. This makes insertion and deletion cheap (just update pointers), but random access expensive (you must traverse from the head).

Insertion and Deletion

Where linked lists earn their keep is reshaping the structure. To insert a new node after node B:

  1. Create the new node E.
  2. Point E at B's current next (C).
  3. Point B at E.

Before:

After:

That's O(1) — two pointer updates and you're done. No shuffling of elements. Deletion is just as quick: to remove C, point B at D and free C's memory.

The stepper shows each node with its next field, in whatever order the nodes happen to sit in memory. The walk from head is the list as a program sees it. It inserts E after B, deletes C (whose predecessor is now E), and then replays the insert with the two pointer writes swapped, so you can see what goes wrong.

Insert after B, delete C, then the wrong order

nodes in memory
A
next: B
B
next: C
C
next: D
D
next: null
walk from head = A → B → C → D → null
The starting list. head points at A.
Step 1/8

Compare with an array, where inserting in the middle means shifting every subsequent element. If your data changes shape frequently, with elements going in and out all the time, a linked list can be the better fit.

Doubly Linked Lists

A doubly linked list adds a second pointer to each node — one pointing forward (next), one pointing backward (prev).

Now you can traverse both directions. Some operations get simpler too — deleting a node when you've already got a direct reference to it, for example. In a singly linked list you'd need to walk forwards from the head to find the predecessor; here the node already knows who came before it.

The cost is memory: each node now carries two pointers instead of one.

Linked Lists in Memory

Linked list nodes are allocated individually on the heap, one at a time. Each one might land at a completely different address. The result is poor cache locality — following pointers means leaping around in memory, and the cache is frequently caught flat-footed.

text
Node A at address 0x1000
Node B at address 0x3F00 (far away!)
Node C at address 0x2200 (somewhere else entirely)

That's the core performance tradeoff: linked lists trade cache efficiency for structural flexibility.

When to Use Linked Lists

Choose a linked list when:

  • You frequently insert or remove elements from the middle of the collection.
  • You don't need random access by index.
  • The collection size changes unpredictably.
  • You're building more elaborate structures (stacks, queues, graphs) where node-based storage is natural.

Choose an array when:

  • You need fast random access by index.
  • Your data size stays relatively stable.
  • You iterate through elements sequentially (cache-friendly).
  • Memory efficiency matters and per-element pointer overhead would sting.

The Pointer Connection

Linked lists are the cleanest demonstration of why pointers matter. Every linked list operation comes down to reading or writing memory addresses. Inserting a node means writing an address into another node's pointer field. Traversing the list means dereferencing pointers one after another.

If pointers felt vague when you first met them, linked lists make them concrete. You can't implement a linked list without internalising that a pointer is an address, that dereferencing reads the value at that address, and that overwriting a pointer changes which node comes next in the chain.

Here's a small singly linked list in C. push_front already works. reverse is a stub that hands the list back unchanged: fill it in so the second line prints the list backwards, using nothing but pointer rewiring.

Try itImplement reverse() by flipping each node's next pointer as you walk the list.
C (GCC 9.2.0)
Show one answer
c
static struct node *reverse(struct node *head) {
struct node *prev = NULL;
while (head != NULL) {
struct node *next = head->next; /* remember the rest of the list */
head->next = prev; /* point this node backwards */
prev = head;
head = next;
}
return prev; /* the old tail is the new head */
}

Three pointers, one pass, no new allocations. Lose track of next before overwriting head->next and the rest of the list is gone for good.

Choosing Between Arrays and Linked Lists

The choice comes down to access patterns. Hammering elements by index or iterating sequentially? Arrays win — their contiguous memory layout hands them a huge cache performance advantage. Constantly inserting or deleting in the middle? Linked lists win — they manage those operations in O(1) once you have a reference to the right node, while an array would have to shuffle everything that follows. Modern hardware leans so heavily on contiguous memory that arrays (and their dynamic cousins, array lists) end up as the default for most applications. Linked lists earn their place in specific scenarios: LRU caches, graph adjacency lists, and other data structures where pointer-based connectivity is the natural fit.