Linked Lists
Master linked list implementations — singly linked, doubly linked, and circular lists with insertion, deletion, reversal, and detection algorithms.
Singly Linked List
A linked list is a linear data structure where each element (node) contains data and a pointer to the next node. Unlike arrays, linked list elements are not stored contiguously in memory — each node can be anywhere in the heap. This gives linked lists O(1) insertion/deletion at known positions (just change pointers) but O(n) access time (must traverse from head). A singly linked list node: struct Node { int data; struct Node* next; }. Key operations: insertAtHead (create node, point it to current head, update head — O(1)), insertAtTail (traverse to last node, point it to new node — O(n) unless you maintain a tail pointer), deleteNode (find node, point previous node's next to deleted node's next, free the memory — ALWAYS free deleted nodes to prevent memory leaks), search (traverse comparing data — O(n)), and reverse (use three pointers: prev, current, next — iterate through the list reassigning next pointers).
Types of Linked Lists
- Singly Linked: Each node has data + next pointer. Simplest form. Can only traverse forward. insertAtHead is O(1), access is O(n)
- Doubly Linked: Each node has data + next + prev pointers. Traverse both directions. Delete a node in O(1) if you have a pointer to it. More memory per node
- Circular Linked: Last node points back to first node (not NULL). Useful for round-robin schedulers, circular buffers. No natural end — detect cycles by comparing with head
- Circular Doubly Linked: Combination — last node's next points to first, first node's prev points to last. Used in Linux kernel's doubly-linked list implementation
- XOR Linked List: Memory-efficient doubly linked — stores XOR of prev and next addresses in one pointer. Saves 4/8 bytes per node. Tricky to implement and debug
- Skip List: Multi-level linked list with express lanes — probabilistic O(log n) search. Used in Redis and LevelDB as an alternative to balanced trees
Common Linked List Problems
- Detect Cycle: Floyd's algorithm — slow pointer moves 1 step, fast pointer moves 2 steps. If they meet, there's a cycle. O(n) time, O(1) space
- Find Middle: Two pointer technique — slow moves 1, fast moves 2. When fast reaches end, slow is at middle. Single pass, O(n) time
- Merge Two Sorted Lists: Compare heads of both lists, add smaller to result, advance that pointer. Recursive or iterative. O(n+m) time
- Reverse in Groups of K: Reverse first K nodes, recursively reverse remaining list. Keep track of connections between groups
- Remove Nth Node From End: Two pointers separated by N nodes — when the fast pointer reaches end, slow is at the node to remove
- Intersection Point: Find the meeting point of two singly linked lists — use length difference or two-pointer technique