DSA: Linked Lists
Learn how linked lists work, how to manipulate them efficiently, and how to solve classic linked list problems.
Singly Linked List
A singly linked list is a chain of nodes where each node holds a value and a pointer to the next node. The last node points to nullptr. There is no backward link.
Core Operations
The three fundamental operations on a singly linked list are insertion, deletion, and traversal.
- Insert at head: O(1), update new node next to old head, move head
- Insert at tail: O(n), traverse to end, then link new node
- Delete a node: O(n), find the predecessor, skip the target node
- Traversal: O(n), follow next pointers from head to nullptr
Singly Linked List: Insert at Head
C++Each insertHead call prepends in O(1) by making the new node point to the current head.
Doubly Linked List
A doubly linked list adds a prev pointer to each node, enabling O(1) deletion of a known node and backward traversal without an extra pass.
Doubly Linked List Benefits
Two pointers per node doubles memory cost but unlocks backward traversal and O(1) node deletion.
- Deletion of a known node is O(1): update the neighbors prev and next directly
- Traversal in both directions without restarting from head
- Used in LRU cache, browser history, and undo-redo systems
- Extra memory per node: one additional pointer (typically 8 bytes on 64-bit systems)
Doubly Linked List: Insert at Front
C++The new node's prev is null (it becomes the head) and the old head's prev is updated to point back.
Linked List vs Array
Arrays offer O(1) random access but O(n) insertion and deletion. Linked lists offer O(1) insert/delete at a known node but O(n) lookup by index.
When to Choose Each
Choose arrays when you need fast random access. Choose linked lists when you need frequent insertions and deletions at arbitrary positions.
- Array: O(1) access by index, cache-friendly, fixed or amortized-grow memory
- Linked list: O(1) insert/delete once position is known, dynamic size, extra pointer memory
- Array search: O(n) unsorted, O(log n) sorted. Linked list search: always O(n)
- Linked list nodes are scattered in memory, less cache-friendly than arrays
| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at head | O(n) | O(1) |
| Insert at tail | O(1) amortized | O(n) or O(1) with tail ptr |
| Insert at position | O(n) | O(1) once node is found |
| Delete at position | O(n) | O(1) once node is found |
| Search | O(n) / O(log n) sorted | O(n) |
| Memory | Contiguous, cache-friendly | Scattered, extra pointer |
Finding the Middle Element
The slow-fast pointer trick (tortoise and hare) finds the middle node in a single pass. The slow pointer moves one step at a time; the fast pointer moves two. When fast reaches the end, slow is at the middle.
Slow and Fast Pointer
Move slow by 1 and fast by 2 simultaneously. When fast hits null or the last node, slow is at the middle.
- One-pass O(n) solution with O(1) extra space
- For even-length lists, slow lands at the second middle node
- This pattern is reused in cycle detection, finding the k-th from end, and palindrome checks
- Adjust the fast pointer start to land at the first or second middle as needed
Middle Node via Slow-Fast Pointers
C++Fast moves twice as fast as slow, so when fast finishes the list, slow is exactly at the midpoint.
Floyd's Cycle Detection
Floyd's algorithm detects a cycle in a linked list using two pointers. If they ever meet, a cycle exists. To find the cycle start, reset one pointer to head and advance both one step at a time until they meet again.
Floyd's Cycle Algorithm
Slow and fast pointers must meet inside the cycle if one exists, because fast gains one step per iteration relative to slow.
- Detection: if slow == fast at any point, a cycle exists
- No cycle: fast reaches nullptr
- Cycle start: reset slow to head, keep fast at meeting point, advance both by 1 until they meet
- Time: O(n), Space: O(1), no visited set needed
Floyd's Cycle Detection and Start
C++After slow and fast meet, resetting slow to head and advancing both by 1 lands them at the cycle entry.
Reversing a Linked List
Reversing a singly linked list iteratively uses three pointers. The recursive approach reverses the rest of the list first, then fixes the link for the current node.
Iterative Reversal
Walk the list with prev, curr, and next. At each step, flip the next pointer backward before advancing.
- prev: starts at nullptr, becomes the new head when done
- curr: current node being processed
- next: saved before overwriting curr next to avoid losing the rest
- Time: O(n), Space: O(1). Recursive reversal uses O(n) stack space.
Iterative Linked List Reversal
C++Three pointers walk forward while flipping each next pointer backward. O(n) time, O(1) space.
Merging Two Sorted Lists
Merge two sorted linked lists by comparing the front nodes and always attaching the smaller one to the result. This runs in O(m + n) time with no extra nodes created.
Merge via Dummy Head
A dummy head node simplifies edge cases by giving the result list a stable starting point before any real node is attached.
- Compare l1->data and l2->data; attach the smaller node to tail->next
- Advance the pointer that was consumed
- After the loop, attach whichever list still has nodes
- Time: O(m + n), Space: O(1), reuses existing nodes
Merge Two Sorted Linked Lists
C++Dummy head avoids special-casing the first node. tail always points to the last merged node.
Finding the Intersection Point
Two linked lists intersect when they share a common node (by address). The trick is to equalize how far each pointer has to travel so they reach the intersection at the same step.
Two-Pointer Intersection
Advance the pointer of the longer list by the length difference first. Then move both one step at a time until they meet.
- Calculate lengths of both lists
- Advance the longer list pointer by |len1 - len2| steps
- Move both pointers together until they point to the same node
- If they reach nullptr at the same time, no intersection exists
Intersection Point of Two Lists
C++Equalizing the distances means both pointers travel the same number of steps to reach the shared node.
Palindrome Linked List
Check if a linked list is a palindrome by finding the middle, reversing the second half, then comparing it node by node with the first half.
Palindrome Check in O(n) Time, O(1) Space
Three steps: find the middle with slow-fast pointers, reverse the second half in place, then compare both halves.
- Step 1: find the midpoint using slow-fast pointers
- Step 2: reverse the list from mid->next to the end
- Step 3: compare the original first half with the reversed second half
- Restore the list by reversing the second half again if needed
Palindrome Check
C++Reverse the second half in place and compare. O(n) time, O(1) space, no extra array needed.
Circular Linked List
In a circular linked list the last node points back to the head instead of nullptr. Traversal must stop when a pointer loops back to the head.
Circular List Properties
No null terminator means you detect the end by checking if next equals head, not by checking for null.
- Insert at head: new node next points to head, tail next points to new head
- Useful for round-robin scheduling and circular buffers
- Traversal loop condition: current != head (not current != nullptr)
- Floyd's cycle detection will always find a cycle in a circular list
Circular Linked List: Insert at End
C++The tail pointer gives O(1) tail insertion. tail->next always points to the head.
Removing Duplicates
In a sorted linked list, duplicates are adjacent, so a single pass comparing each node to the next is enough. For unsorted lists, a hash set tracks seen values.
Duplicate Removal
Sorted list: compare consecutive nodes and skip duplicates. Unsorted list: use an unordered_set to detect repeats.
- Sorted: if curr->data == curr->next->data, skip curr->next (O(n), O(1) space)
- Unsorted: store each seen value in a hash set; skip nodes whose value is already in the set
- After skipping, update pointers and free the removed node to avoid memory leaks
- Always advance to the next node only after confirming the current is kept
Remove Duplicates from Sorted List
C++Adjacent duplicates are skipped by updating the next pointer past them. O(n) time, O(1) space.
Knowledge Check
1. What is the time complexity of inserting at the head of a singly linked list?
2. Which node field does a doubly linked list have that a singly linked list does not?
3. Floyd's cycle detection algorithm uses:
4. To find the middle of a linked list in one pass, you use:
5. In the iterative reversal of a singly linked list, how many pointers are needed?
6. What is the key difference between an array and a linked list for insertion at a known position?
7. To detect the intersection point of two linked lists, you equalize list lengths by:
8. When merging two sorted linked lists, the time complexity is: