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).
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:
- Create the new node E.
- Point E at B's current next (C).
- 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
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.
Node A at address 0x1000Node 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.
Show one answer
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.