What is a Linked List?
A linked list is a linear data structure where elements are stored in nodes. Each node holds a value and a pointer (reference) to the next node in the sequence. The first node is called the head, and the last node points to null.
Unlike arrays, linked lists do not require contiguous memory. This makes insertions and deletions at the head O(1), since you only need to update a pointer. The tradeoff is that you lose O(1) random access. To reach the kth element, you must traverse k nodes from the head.
Linked List Operations & Time Complexity
| Operation | Time | Description |
|---|---|---|
| Prepend | O(1) | Create a new node, point it to the current head, update head. |
| Append | O(n) | Traverse to the last node, set its next pointer to the new node. |
| Insert at index | O(n) | Traverse to the node before the target index, rewire pointers. |
| Delete by value | O(n) | Find the node, update the previous node's next pointer to skip it. |
| Search | O(n) | Walk from head to tail comparing values. |
| Reverse | O(n) | Iteratively reverse pointers using three variables: prev, curr, next. |
| Access by index | O(n) | No random access. Must traverse from the head. |
Reversal (the classic interview question)
Reversing a singly linked list in place is one of the most common interview problems. The algorithm uses three pointers: prev, curr, and next. At each step, save the next node, point the current node backward to prev, then advance all three pointers. After the loop, prev is the new head. O(n) time, O(1) space.
Deletion edge cases
When deleting from a linked list, handle three cases: deleting the head (update head pointer), deleting a middle node (update previous node's next pointer), and deleting the tail (set the second-to-last node's next to null). Using a dummy head node simplifies the logic by eliminating the head-deletion special case.
Linked List vs Array
| Feature | Linked List | Array |
|---|---|---|
| Access by index | O(n) | O(1) |
| Insert at head | O(1) | O(n) |
| Insert at tail | O(n)* | O(1) amortized |
| Delete at head | O(1) | O(n) |
| Search | O(n) | O(n) unsorted, O(log n) sorted |
| Memory | Extra per node (pointer) | Contiguous, cache-friendly |
*O(1) if you maintain a tail pointer.
Common Interview Questions Using Linked Lists
Linked lists test pointer manipulation and edge case awareness:
- •Reverse a linked list — Iterative (three pointers) or recursive. The most fundamental linked list problem.
- •Detect a cycle — Floyd's tortoise and hare. Slow pointer moves 1 step, fast moves 2. If they meet, there's a cycle.
- •Find the middle node — Fast/slow pointer technique. When fast reaches the end, slow is at the middle.
- •Merge two sorted lists — Compare heads, pick the smaller, advance that pointer. Repeat. O(n + m) time.
- •Remove nth node from end — Two pointers, n nodes apart. When the lead pointer hits the end, the other is at the target.
- •Palindrome linked list — Find middle, reverse second half, compare both halves node by node.
Types of Linked Lists
- •Singly linked list — Each node points to the next. Simple, minimal memory. Most common in interviews.
- •Doubly linked list — Each node points to both next and previous. Allows O(1) deletion of a known node and backward traversal.
- •Circular linked list — The last node points back to the head instead of null. Used in round-robin schedulers and circular buffers.
Frequently Asked Questions
What is a linked list?add
A linked list is a linear data structure where each element (node) contains a value and a pointer to the next node. Unlike arrays, linked lists do not store elements in contiguous memory, which makes insertions and deletions at the head O(1) but random access O(n).
What is the difference between a singly and doubly linked list?add
A singly linked list has nodes that point only to the next node. A doubly linked list has nodes that point to both the next and previous nodes, which allows O(1) deletion of a given node and backward traversal, at the cost of extra memory per node.
What is the time complexity of linked list operations?add
Prepend (insert at head) is O(1). Append (insert at tail) is O(n) for a singly linked list without a tail pointer, O(1) with one. Search and delete by value are O(n) since you must traverse the list. Reversing a linked list is O(n) time and O(1) space.
Why are linked lists important for coding interviews?add
Linked lists test pointer manipulation, edge case handling (empty list, single node, head/tail operations), and in-place algorithms. Classic problems include reversing a linked list, detecting cycles (Floyd's algorithm), merging sorted lists, and finding the middle node with the fast/slow pointer technique.
When should I use a linked list instead of an array?add
Use a linked list when you need frequent insertions and deletions at the beginning or middle of a collection and don't need random access. Arrays are better when you need index-based access, cache-friendly iteration, or a fixed-size collection. In practice, arrays are used far more often, but linked list problems are common in interviews.