Singly Linked List
A singly linked list is a chain in which each element (a node) has two parts: the stored value and a reference to the next node (next). The last node's next is null.
The key difference from an array: nodes are not contiguous in memory — each can sit anywhere on the heap, and the chain is held together only by pointers. Everything else follows from that:
- There is no index — reaching the
n-th element means walking from the head,O(n) - In exchange, insertion and deletion require no shifting — just a few pointer updates
- No size is reserved up front, and there is no growing or copying
Access to the list goes through a single entry point — the head pointer. Lose the head and you lose the whole list (and the GC reclaims it). A tail pointer is often kept as well so that appending is O(1) rather than O(n).
| Operation | Singly Linked List | Dynamic array | Note |
|---|---|---|---|
| Insert at head | O(1) | O(n) | The linked list's strongest point |
| Remove from head | O(1) | O(n) | `head = head.next` |
| Insert at tail | O(n); O(1) with a tail pointer | amortized O(1) | Keeping a tail is almost always worth it |
| Remove from tail | O(n) | O(1) | You must find the second-to-last node |
| Delete from the middle (given the node) | O(1) — if the previous node is known | O(n) | In a singly list, finding the previous is `O(n)` |
| Access element `i` | O(n) | O(1) | The array's strongest point |
| Search | O(n) | O(n) | Linear in both |
| Memory | An extra pointer per element | Dense, cache-friendly | Arrays iterate faster in practice |
The logic of the core operations — all of them are pointer rewiring, and the order matters.
- Insert at head: create the node, set
newNode.next = head, thenhead = newNode. Reverse that order and you lose the rest of the list. - Insert at tail (without a tail pointer): walk until
nextisnull, then setlast.next = newNode. If the list is empty,headitself must be set — the most frequently forgotten case. - Delete: find the node before the target and set
prev.next = target.next. If the head is being deleted,head = head.next. - Traversal:
let cur = head; while (cur) { ...; cur = cur.next; }
A classic technique is two pointers (fast & slow): slow moves one step, fast two. When fast reaches the end, slow is at the middle. The same technique detects a cycle: if the list has one, fast and slow are guaranteed to meet (Floyd's algorithm) — both O(n) time, O(1) space.
When does a linked list actually win in practice? The honest answer is rarely — and that honesty is well received in interviews.
Where it wins:
- Frequent insertion/removal at the head — stacks, queues, undo chains
- Deleting when you already hold the node — as in an LRU cache, where a hash map points straight at the node making removal
O(1)(this needs a doubly linked list) - When copying large elements is expensive — a linked list never relocates the whole structure
- Splicing lists together — two lists can be joined in
O(1)
Where it loses (i.e. most of the time): no index access; an extra pointer of memory per node; and poor cache locality — nodes are scattered in memory and every hop risks a cache miss. So in real measurements walking an array beats walking a linked list by a wide margin, even though both are O(n).
That's why ArrayList/Array is the default in practice, while linked lists mostly serve as building material inside other structures (hash map buckets, LRU caches, queue implementations).
Interview tip. "Reverse a linked list" may be the single most-asked question anywhere. The expected iterative solution keeps three pointers — prev, curr, next — and sets curr.next = prev on each step; O(n) time, O(1) space. Drawing three nodes on paper and tracing the pointer moves before writing code makes a strong impression.
Other frequent ones: find the middle (fast & slow), detect a cycle (Floyd), find the k-th node from the end (two pointers k apart), merge two sorted lists, remove duplicates.
The most common mistakes: forgetting null checks (empty list, single-node list, deleting the head); rewiring pointers in the wrong order and losing the rest of the chain; and confusing while (cur.next) with while (cur). Listing the edge cases out loud — empty, one element, two elements — is the behaviour the interviewer is waiting for.
One very useful technique: use a dummy (sentinel) head node. It removes the head as a special case and simplifies the code noticeably.