Linked List

Linked List

Imagine a treasure hunt. Each clue tells you the location of the next clue, but nothing tells you where clue #5 is directly — you must start at clue #1 and follow the chain. A linked list is exactly this: a sequence of independent boxes (called nodes) scattered anywhere in memory, where each box holds a value plus the address of the next box. Contrast this with an array, which is one solid block of numbered lockers you can jump into instantly. The linked list trades that instant jump for a superpower array lacks: you can splice a new box into the middle of the chain by rewriting just one or two pointers, without shifting anything else.

Precise definition

A linked list is a linear data structure made of nodes. Each node stores: (1) a value (the payload), and (2) one or more references (pointers) to other nodes. The list is accessed through a head pointer to the first node; the last node's next pointer is null, marking the end.

• Singly linked: each node points only to next. Traversal is one-directional.
• Doubly linked: each node also has a prev pointer, allowing backward traversal and O(1) deletion of a known node.
• Circular: the tail's next points back to the head instead of null.

Crucially, nodes are not contiguous in memory. There is no index arithmetic — to reach position k you must walk k links from the head.

Worked example: search vs. insert, with the operations counted

Take the list head → 10 → 20 → 30 → null from the diagram. Let's count real work.

Search for 30. Start at head (10). Compare 10 ≠ 30, follow next. At 20: 20 ≠ 30, follow next. At 30: match. That's 3 node visits and 3 comparisons to find the element at position 3. To confirm a value is absent, you must walk all the way to null — the full n visits. Searching is O(n), no shortcut, because there is no random access.

Insert 25 after the node holding 20. Assume we already hold a reference to node(20). Steps: (1) allocate a new node with value 25; (2) set new.next = node20.next (which is node(30)); (3) set node20.next = new. That is 2 pointer writes and 1 allocation — a fixed amount of work regardless of list size. This is the headline win: O(1) insertion at a known position. Compare an array of 1,000,000 elements: inserting in the middle forces you to shift ~500,000 elements right — O(n) copying.

The catch: that O(1) assumed you already had the node. If you only know the value 20, you first pay O(n) to find it. The cheap splice and the expensive search are separate costs — interviewers love to see if you conflate them.

Complexity summary (be honest about the fine print)

• Access k-th element: O(n) — must walk from head. (Array: O(1).)
• Search: O(n) worst/average; O(1) best (target is head).
• Insert / delete at head: O(1) always — this is why linked lists back stacks, queues, and LRU caches.
• Insert / delete at a known node: O(1) for doubly linked. For singly linked you need the predecessor, so deleting a node you only have a pointer to is O(n) unless you use the copy-next-node trick.
• Insert at tail: O(n) if you only keep head; O(1) if you also maintain a tail pointer.

Common pitfalls and what an interviewer probes

• Losing the chain. When rewiring, order matters. If you write node20.next = new before saving the old next, you lose the pointer to node(30) and orphan the rest of the list. Always capture the successor first.
• Null-pointer dereference at the boundaries. Empty list (head == null), single-element list, and operations on the tail are the classic edge cases. Interviewers deliberately test these.
• The dummy (sentinel) head node. Insertions/deletions at the front are a special case because they change head itself. A dummy node before the real head makes every position uniform, eliminating branchy edge-case code — a strong signal in an interview.
• Two-pointer technique. Detecting a cycle (Floyd's fast/slow pointers), finding the middle in one pass, or finding the k-th-from-end node are the canonical problems. Expect at least one.
• Reversing a list. The three-pointer in-place reversal (prev, curr, next) is the most-asked linked-list question. Know it cold: O(n) time, O(1) space.

When it matters in practice, and the trade-offs

Linked lists shine when you do many insertions and deletions at ends or at positions you already hold, and rarely need random access: implementing stacks and queues, the collision chains in a hash table, the eviction order in an LRU cache (doubly linked list + hash map), and adjacency lists in graphs. The OS uses them for process and free-memory lists.

But be skeptical — in modern practice arrays (dynamic arrays / ArrayList / slice) usually win even for insert-heavy workloads. Two reasons: (1) memory overhead — every node pays for a pointer (8 bytes) or two, plus allocator bookkeeping, so a linked list can use 2–3× the memory of a packed array. (2) cache locality — arrays sit contiguously and stream through the CPU cache; linked-list nodes are scattered, so each hop is a likely cache miss. A cache miss costs ~100× a cache hit, so an O(n) array scan often beats an O(n) linked scan by a large constant factor. The correct interview answer is nuanced: choose a linked list for guaranteed O(1) splicing at known nodes and pointer stability; choose an array when you need indexing, iteration speed, or compactness.

Key takeaways

• A linked list is nodes scattered in memory chained by pointers; access and search are O(n) (no random access), but insert/delete at the head or a known node is O(1) — the opposite trade-off from arrays.
• The O(1) splice assumes you already hold the node; finding it by value first still costs O(n), and singly linked deletion needs the predecessor.
• Master the interview staples: sentinel/dummy head to kill edge cases, three-pointer in-place reversal, and Floyd's fast/slow pointers for cycles and midpoints.
• In real systems, arrays often beat linked lists despite worse Big-O because of cache locality and lower memory overhead — reach for a linked list only when you truly need cheap splicing or stable node references.