Understanding Singly Linked Lists in Detail
A Singly Linked List is a linear data structure where each element (called a node) contains two things: the data it holds, and a pointer (reference) to the next node in the sequence. Unlike arrays, linked list nodes are not stored contiguously in memory — each node can be anywhere in the heap, connected only by these pointers.
Imagine a scavenger hunt where each clue tells you the location of the next clue. You must start at the first clue (the head) and follow the chain — you cannot jump directly to clue #5 without visiting clues #1 through #4 first. This is the fundamental trade-off: you lose O(1) random access but gain O(1) insertions and deletions at the head without shifting any elements.
Linked lists are a building block for more complex data structures like stacks, queues, hash table chaining, adjacency lists for graphs, and LRU caches. Mastering them is essential for coding interviews — they are the second most tested data structure after arrays.
How Singly Linked Lists Work Internally
Node Structure
Each node is an object with two fields: data (the value stored) and next (a pointer to the following node). The last node's next pointer is null, signaling the end of the list. This is sometimes called the sentinel or terminator.
Head Pointer
The linked list itself is defined by a single pointer to the first node, called the head. If head is null, the list is empty. Every operation starts by accessing the head — there is no other entry point into the list.
Dynamic Size
Unlike arrays, a linked list has no fixed capacity. Each new node is allocated individually on the heap. The list grows and shrinks with each insertion or deletion, with zero wasted space. There is never a "resize" operation.
One-Way Traversal
In a singly linked list, you can only move forward — from head to tail. There is no way to go backward to a previous node without traversing from the head again. This limitation is addressed by the Doubly Linked List variant.
Memory Layout
The scattered memory layout of linked lists has profound performance implications compared to arrays.
Heap-Allocated Nodes
Each node is individually allocated on the heap using new/malloc. This means nodes can be scattered across different memory regions. Allocating many small objects can also cause heap fragmentation over time.
Per-Node Overhead
Every node stores a pointer in addition to its data. On a 64-bit system, each pointer takes 8 bytes. For a list of integers (4 bytes each), the pointer overhead is 200% — you use more memory for pointers than for actual data. This makes linked lists memory-inefficient for small data types.
Poor Cache Performance
Because nodes are scattered across memory, traversing a linked list causes frequent CPU cache misses. The CPU fetches a cache line for one node, but the next node is likely in a completely different memory region. This makes linked list traversal 10-100x slower than array traversal in practice, despite both being O(n).
Core Operations Explained
The beauty of linked lists lies in their pointer manipulation. Each operation is about rewiring connections rather than moving data.
Complexity Analysis
The key insight is that linked lists excel at head operations (O(1)) but struggle with anything requiring traversal. The cost of finding a position (O(n)) dominates the cost of the actual insertion/deletion (O(1)).
Operation Complexity
| Operation | Time |
|---|---|
| Access by Index | O(n) |
| Search | O(n) |
| Insert at Head | O(1) |
| Insert at Tail | O(n) |
| Insert at Index | O(n) |
| Delete at Head | O(1) |
| Delete at Tail | O(n) |
| Delete at Index | O(n) |
Space Complexity
A linked list of n elements uses O(n) memory, but with significantly higher per-element overhead than arrays. Each node stores both data and a next pointer (8 bytes on 64-bit systems). For a list of 1 million 4-byte integers, the total memory is ~12 MB (4 + 8 bytes per node), compared to ~4 MB for an array. There is no wasted capacity — memory usage equals exactly what is needed.
Common Interview Patterns
Linked list problems test your ability to think about pointer manipulation, edge cases (empty list, single node), and the fast/slow pointer technique. These are the patterns that appear most frequently.
Reverse a Linked List
EasyThe single most common linked list interview question. Reverse the direction of all pointers so the tail becomes the head. Appears in almost every FAANG interview loop.
Detect a Cycle (Floyd's Algorithm)
MediumDetermine if a linked list has a loop where the tail connects back to an earlier node. Uses the famous "tortoise and hare" approach with O(1) extra space.
Merge Two Sorted Lists
EasyGiven two sorted linked lists, merge them into one sorted list. A fundamental building block for Merge Sort on linked lists and a very common interview question.
Find Middle Node
EasyFind the middle element of a linked list in one pass without knowing the length. A building block for many other problems (e.g., sorting a linked list with Merge Sort).
Singly Linked List vs Array
Understanding when to choose a linked list over an array (and vice versa) is a core skill tested in interviews and essential for system design.
| Feature | Array | Singly Linked List |
|---|---|---|
| Access by Index | O(1) — direct calculation | O(n) — traverse from head |
| Insert at Head | O(n) — shift all elements | O(1) — update two pointers |
| Insert at Tail | O(1) amortized | O(n) without tail pointer |
| Delete at Head | O(n) — shift all elements | O(1) — move head pointer |
| Memory Efficiency | No per-element overhead | 8 bytes overhead per node |
| Cache Performance | Excellent (contiguous) | Poor (scattered nodes) |
| Dynamic Growth | Expensive resize + copy | Grows node by node, no copy |
When to Use Singly Linked Lists
Linked lists are the right choice when your primary operations are insertions and deletions at the front, and you rarely need random access.
Implementing Stacks
A stack backed by a linked list offers O(1) push and pop at the head with no capacity limits. This is how many language runtime stacks work internally.
Hash Table Chaining
When multiple keys hash to the same bucket, a linked list stores all colliding entries. Each bucket is a small linked list that grows and shrinks dynamically.
Undo History & Playlists
Any sequential data where you frequently add/remove at the front or navigate forward — music playlists, undo stacks, and process scheduling queues are natural fits.
Common Mistakes to Avoid
Losing the Head Reference
If you reassign head during traversal without saving it, the entire list becomes unreachable and is lost forever. Always use a separate current variable for traversal and keep head untouched.
Null Pointer Exceptions
Accessing current.next when current is null crashes your program. Always check if current !== null before accessing its properties. Edge cases: empty list (head is null) and single-node list (head.next is null).
Forgetting Edge Cases
Many linked list bugs come from not handling: empty list (head = null), single node (head.next = null), or operations at the tail. Always test your solution with 0, 1, and 2 nodes before submitting.
Memory Leaks in C/C++
In languages without garbage collection, deleting a node without freeing its memory causes a leak. When removing a node, always save a reference to it, unlink it from the list, then call free/delete on the saved reference.