Linked lists were one of the very first “real” data structures I learned, right after arrays, and I still think they’re one of the best ways to understand the trade-off between contiguous and pointer-based memory layouts. Unlike an array, where elements sit next to each other in memory and I access them by a computed offset, a linked list is a chain of separately allocated nodes, each holding a piece of data and a pointer (or two) to its neighbor(s). This gives me flexibility that arrays can’t: I can insert or delete an element without shifting everything else around.
I find linked lists worth understanding deeply not because they’re always the fastest choice — they usually aren’t, compared to arrays, for pure sequential access — but because the pointer-manipulation skills they teach show up constantly in more advanced structures: trees, graphs, hash table chaining, and beyond.
History and Background
Linked lists are among the oldest data structures in computer science, with roots going back to the mid-1950s. The information-processing language IPL (Information Processing Language), developed by Allen Newell, Cliff Shaw, and Herbert Simon starting around 1956, is widely credited as one of the earliest languages to use linked list structures as a core organizing principle for symbolic data manipulation, particularly for their work on early AI programs like the Logic Theorist.
The concept was substantially popularized and formalized through Lisp, created by John McCarthy in 1958, whose fundamental “cons cell” (constructing a pair of a value and a pointer to the rest of the list) is essentially a singly linked list node. Linked lists have remained a staple of computer science education and practical programming ever since, with detailed treatments appearing in classic references including Knuth’s “The Art of Computer Programming” and, more recently, Cormen, Leiserson, Rivest, and Stein’s “Introduction to Algorithms.”
Problem Statement
I want a data structure that stores an ordered sequence of elements while supporting efficient insertion and deletion at arbitrary positions — something a plain array struggles with, since inserting or removing an element in the middle of an array requires shifting every subsequent element, costing $O(n)$ time. I’m willing to give up an array’s $O(1)$ random access by index in exchange for $O(1)$ insertion and deletion once I already have a reference to the relevant position.
Core Concepts
- Node: A single element of the list, typically containing a data field (
key) and one or more pointer fields linking it to neighboring nodes. - Singly linked list: Each node has only a
nextpointer, referencing the following node; traversal is possible only in the forward direction. - Doubly linked list: Each node has both a
nextand aprevpointer, allowing traversal in both directions and simplifying certain deletion operations. - Head: A pointer to the first node of the list (or
NILif the list is empty). - Sentinel (dummy node): A special node that doesn’t hold real data but simplifies boundary-case logic by ensuring every real node always has a genuine predecessor and successor, even at the “ends” of the list — this technique turns the list into a circular structure with no special-cased NIL checks needed in the core operations.
- Circular linked list: A variant where the last node’s
nextpointer points back to the first node (and, for doubly linked circular lists, the first node’sprevpoints to the last), forming a ring rather than a terminated chain.
How It Works
In a singly linked list, I maintain a head pointer. To insert a new node at the front, I set the new node’s next to the current head, then update head to point to the new node — an $O(1)$ operation. To search for a key, I start at head and follow next pointers, comparing keys, until I either find a match or reach NIL. To delete a node, I need a pointer to its predecessor (since a singly linked list can’t look backward), so I typically search for the node just before the one I want to remove, then update that predecessor’s next to skip over the removed node.
In a doubly linked list, insertion and deletion become more symmetric and, notably, deletion becomes $O(1)$ once I already have a pointer to the node I want to remove, since I can directly access both its predecessor (prev) and successor (next) without needing to search for them. To insert a new node x right after an existing node y, I set x.next = y.next, x.prev = y, update y.next.prev = x (if y.next isn’t NIL), and finally y.next = x.
Using a sentinel node (commonly for circular, doubly linked lists) eliminates almost all boundary-case checks: instead of checking “is this the first/last node” or “is the list empty,” every real node — including what would otherwise be the first and last — always has a genuine, non-NIL predecessor and successor, since the sentinel itself plays that role at the boundary.
Working Principle
The core mechanism that makes linked lists efficient for insertion and deletion is that these operations only ever touch a small, constant number of pointers — regardless of how large the list is — as long as I already have a reference to the relevant node(s). This is fundamentally different from an array, where inserting in the middle requires physically moving every subsequent element to make room.
The trade-off is that linked lists sacrifice the ability to jump directly to the $i$-th element; I have to walk the list one node at a time from the head (or, in a doubly linked list, potentially from either end) to reach a specific position, which costs $O(n)$ in the worst case. This is the fundamental tension between linked lists and arrays: one favors fast modification at known positions, the other favors fast positional access.
Mathematical Foundation
Search cost. For a singly or doubly linked list of $n$ elements, searching for a key in the worst case (the key is at the end, or absent) requires examining all $n$ nodes:
$$ T_{search}(n) = \Theta(n) $$
Insertion cost. Given a pointer to the insertion point (e.g., the head, or a specific node y after which to insert), insertion takes constant time:
$$ T_{insert} = O(1) $$
If instead I need to insert after searching for a specific key’s position first, the total cost becomes:
$$ T_{insert,\ by\ key} = \Theta(n) $$
dominated by the search.
Deletion cost. In a doubly linked list, given a pointer directly to the node to delete:
$$ T_{delete} = O(1) $$
In a singly linked list, deleting a specific node (not already known via a predecessor pointer) requires first finding its predecessor by traversal:
$$ T_{delete,\ singly\ linked} = \Theta(n) $$
This asymmetry — $O(1)$ deletion in doubly linked lists versus $\Theta(n)$ in singly linked lists when only given the target node — is one of the most important practical distinctions between the two variants.
Diagrams
flowchart LR
H[head] --> N1[Node A<br/>prev: NIL, next: B]
N1 <--> N2[Node B<br/>prev: A, next: C]
N2 <--> N3[Node C<br/>prev: B, next: NIL]Pseudocode
Doubly linked list search:
LIST-SEARCH(L, k)
x = L.head
while x != NIL and x.key != k
x = x.next
return x
Doubly linked list insertion (at the front):
LIST-INSERT(L, x)
x.next = L.head
if L.head != NIL
L.head.prev = x
L.head = x
x.prev = NIL
Doubly linked list deletion:
LIST-DELETE(L, x)
if x.prev != NIL
x.prev.next = x.next
else
L.head = x.next
if x.next != NIL
x.next.prev = x.prev
Sentinel-based circular doubly linked list operations:
LIST-INSERT'(L, x)
x.next = L.nil.next
L.nil.next.prev = x
L.nil.next = x
x.prev = L.nil
LIST-DELETE'(L, x)
x.prev.next = x.next
x.next.prev = x.prev
LIST-SEARCH'(L, k)
x = L.nil.next
while x != L.nil and x.key != k
x = x.next
return x
Step-by-Step Example
Let me trace a doubly linked list starting empty, then performing INSERT(10), INSERT(20), INSERT(30), then DELETE(20).
INSERT(10): List is empty,L.head = NIL. New node10hasnext = NIL,prev = NIL. SinceL.headwasNIL, I just setL.head = 10. List:10.INSERT(20):20.next = L.head = 10. SinceL.head(10) isn’t NIL,10.prev = 20. ThenL.head = 20, and20.prev = NIL. List:20 <-> 10.INSERT(30):30.next = L.head = 20.20.prev = 30.L.head = 30,30.prev = NIL. List:30 <-> 20 <-> 10.DELETE(20): Node20hasprev = 30(not NIL), so30.next = 20.next = 10. Node20hasnext = 10(not NIL), so10.prev = 20.prev = 30. List becomes:30 <-> 10.
This shows the $O(1)$ nature of doubly linked list deletion — I never had to search the list at all, since I already had a direct reference to node 20 and could use its own prev and next pointers to reconnect its neighbors.
Time Complexity
| Operation | Singly Linked List | Doubly Linked List |
|---|---|---|
| Search by key | $O(n)$ | $O(n)$ |
| Insert at front | $O(1)$ | $O(1)$ |
| Insert after a known node | $O(1)$ | $O(1)$ |
| Delete a known node | $O(n)$ (must find predecessor) | $O(1)$ |
| Delete by key (search + delete) | $O(n)$ | $O(n)$ |
| Access $i$-th element | $O(n)$ | $O(n)$ (or $O(\min(i, n-i))$ if traversing from whichever end is closer) |
The standout difference is deletion of a node I already have a direct reference to: $O(1)$ for doubly linked lists versus $O(n)$ for singly linked lists, since only the doubly linked version gives me direct access to the predecessor without a search.
Space Complexity
A singly linked list with $n$ nodes uses $\Theta(n)$ space, with each node needing one pointer field (next) plus its data. A doubly linked list also uses $\Theta(n)$ space, but each node needs an additional pointer field (prev), roughly doubling the pointer overhead per node compared to a singly linked list, though the asymptotic space class is the same. A sentinel-based implementation adds exactly one constant extra node regardless of list size, which is asymptotically negligible.
Correctness Analysis
Correctness of linked list operations depends on maintaining the invariant that the chain of next (and, for doubly linked lists, prev) pointers always accurately reflects the intended logical ordering of elements, with no dangling or incorrectly-linked pointers at any point after an operation completes.
For insertion, correctness follows from carefully ordering the pointer updates so that no link is lost mid-update — for example, in LIST-INSERT, I must set x.next to the old head before overwriting L.head, otherwise I’d lose the reference to the rest of the list entirely. For deletion, correctness in the doubly linked case relies on the fact that a node’s prev and next pointers, by the list’s invariant, always correctly identify its true neighbors, so re-linking those neighbors to each other (bypassing the deleted node) correctly preserves the list’s remaining order. The NIL checks (or, in the sentinel version, the sentinel node’s role) ensure boundary cases — deleting the first or last node — are handled without leaving stale references.
Advantages
- $O(1)$ insertion and deletion at a known position, without needing to shift other elements, unlike arrays.
- Dynamic size — no need to know or pre-allocate a maximum capacity in advance, unlike a fixed-size array.
- Efficient implementation of other structures like stacks, queues, and adjacency lists for graphs.
- Doubly linked lists support efficient bidirectional traversal and $O(1)$ deletion given a direct node reference.
Disadvantages
- No $O(1)$ random access by index — reaching the $i$-th element requires $O(i)$ traversal, unlike an array’s $O(1)$ indexed access.
- Extra memory overhead per element for pointer fields, compared to a tightly packed array.
- Poorer cache locality than arrays, since nodes are typically scattered across memory rather than stored contiguously, which can hurt real-world performance despite matching asymptotic complexity.
- Slightly more complex and error-prone to implement correctly, especially deletion and boundary-case handling, compared to array-based structures.
Applications
- Implementing other abstract data types: stacks, queues, and deques are all commonly built on top of linked lists.
- Hash table chaining, where each bucket holds a linked list of colliding elements.
- Adjacency list representations of graphs, where each vertex has a linked list of its neighboring edges.
- Operating system kernels use linked lists extensively for managing lists of processes, free memory blocks, and I/O request queues, often using intrusive doubly linked list techniques (like the Linux kernel’s
list_headstructure). - Browser history / undo-redo functionality, often implemented conceptually as a doubly linked list allowing forward and backward navigation.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
struct Node *next;
struct Node *prev;
} Node;
typedef struct {
Node *head;
} DoublyLinkedList;
void initList(DoublyLinkedList* list) {
list->head = NULL;
}
Node* newNode(int key) {
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->next = NULL;
node->prev = NULL;
return node;
}
/* Inserts a new node with the given key at the front of the list. */
void listInsert(DoublyLinkedList* list, int key) {
Node* x = newNode(key);
x->next = list->head;
if (list->head != NULL) {
list->head->prev = x;
}
list->head = x;
x->prev = NULL;
}
Node* listSearch(DoublyLinkedList* list, int key) {
Node* x = list->head;
while (x != NULL && x->key != key) {
x = x->next;
}
return x;
}
/* Deletes a specific node in O(1), given a direct pointer to it. */
void listDelete(DoublyLinkedList* list, Node* x) {
if (x->prev != NULL) {
x->prev->next = x->next;
} else {
list->head = x->next;
}
if (x->next != NULL) {
x->next->prev = x->prev;
}
free(x);
}
void listPrint(DoublyLinkedList* list) {
Node* x = list->head;
while (x != NULL) {
printf("%d ", x->key);
x = x->next;
}
printf("\n");
}
void listFree(DoublyLinkedList* list) {
Node* x = list->head;
while (x != NULL) {
Node* temp = x;
x = x->next;
free(temp);
}
}
int main(void) {
DoublyLinkedList list;
initList(&list);
listInsert(&list, 10);
listInsert(&list, 20);
listInsert(&list, 30);
printf("List after inserting 10, 20, 30: ");
listPrint(&list);
Node* found = listSearch(&list, 20);
if (found != NULL) {
printf("Found key 20, deleting it in O(1)...\n");
listDelete(&list, found);
}
printf("List after deleting 20: ");
listPrint(&list);
listFree(&list);
return 0;
}
Notice how listDelete takes a direct Node* pointer rather than a key — this is deliberate, since it demonstrates the $O(1)$ deletion capability that’s the whole point of using a doubly linked list. If I only had a key, I’d need to call listSearch first, which is the $\Theta(n)$ part of the combined operation.
Sample Input and Output
Input:
Insert (at front): 10, 20, 30
Search for and delete: 20
Output:
List after inserting 10, 20, 30: 30 20 10
Found key 20, deleting it in O(1)...
List after deleting 20: 30 10
This matches my hand-traced example exactly: inserting at the front reverses the apparent order (30 ends up first since it was inserted last), and deleting 20 correctly reconnects 30 and 10 directly.
Optimization Techniques
- Using a sentinel node: Eliminates repeated
NIL/NULLboundary checks throughout insertion, deletion, and search code, simplifying logic and reducing the chance of boundary-case bugs. - Maintaining a tail pointer: If frequent insertion at the end of the list is needed, keeping an explicit
tailpointer avoids an $O(n)$ traversal just to find the last node. - Memory pooling: For workloads with heavy node allocation/deallocation churn, using a custom pool allocator (as discussed in the pointers-and-objects topic) reduces
malloc/freeoverhead. - XOR linked lists: An advanced, rarely-used technique that combines
prevandnextinto a single XORed pointer field to halve pointer memory overhead, at the cost of significantly more complex and less debuggable traversal code — mostly of academic interest today. - Skip lists: When search performance matters more than plain linked list search allows, layering extra “express lane” pointers on top of a linked list (forming a skip list) can bring average search time down to $O(\lg n)$.
Common Mistakes
- Losing the reference to the rest of the list during insertion, by overwriting
head(or another pointer) before saving the old value into the new node’snextfield. - Forgetting to update both directions in a doubly linked list, updating
nextbut forgetting the correspondingprevupdate (or vice versa), which silently corrupts the list’s bidirectional consistency even though forward traversal might still look correct. - Not handling empty-list and single-node edge cases, such as deleting the only node in the list, which requires correctly setting
headback toNULL/NIL. - Dangling pointer bugs after deletion: freeing a node’s memory and then continuing to use a stale pointer to it elsewhere in the code.
- Off-by-one confusion between “insert before” and “insert after” semantics, especially when translating pseudocode or examples between different conventions for where insertion happens relative to a reference node.
- Memory leaks from forgetting to free all nodes when destroying the whole list, especially if cleanup code has an early return or exception path that skips the freeing loop.
Further Reading
- Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Chapter 10: “Elementary Data Structures,” MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Knuth, Donald E., The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley: https://www-cs-faculty.stanford.edu/~knuth/taocp.html
- Linux Kernel Documentation, “Linked Lists” (
list_headimplementation): https://docs.kernel.org/core-api/kernel-api.html#list-management-functions - GeeksforGeeks, “Linked List Data Structure”: https://www.geeksforgeeks.org/dsa/linked-list-data-structure/
- Sedgewick, Robert, and Kevin Wayne, Algorithms, 4th Edition, Addison-Wesley: https://algs4.cs.princeton.edu/13stacks/
