If you’re prepping for technical interviews and feel a bit rusty on linked lists, this post is for you. I’ll cover just enough to help you survive common interview questions. We will not go into too much detail.
What is a linked list?
A linked list is a linear data structure where each element (commonly known as “Node”) is stored in a separate object. A node will typically contain:
- Value
- Reference to the next node
An Node will typically look something like this:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = nextCommon variants of linked lists are:
- Singly Linked List: each node points to the next
- Double Linked List: Nodes have both next and prev pointers
- Circular Linked List: The last node points to head
When to use:
- When you need dynamic memory allocation (no fixed size)
- When insertions/deletions in the middle are frequent and you want O(1) if you have a pointer.
When NOT to use:
- When you need fast random access (arrays are better for O(1) access by index).
Big-O notes:
Unless you’re given a pointer to the location, you will almost always have to traverse the linked list.
- Access by index: O(n) (you must traverse)
- Search by value: O(n)
- Insert at head: O(1)
- Insert at tail (if no tail pointer): O(n)
- Delete given a pointer: O(1)
- Delete by value: O(n)
Know these patterns before your interview:
- Reverse a linked list
- Detect a cycle in circular linked list
- Find middle node
- Merge two lists
- Remove N-th node from the end
Mental models that will help you
Always think pointers (not indexes). In many cases you will need 2 pointers.
How to practice
I do not recommend using LeetCode for this. It’s easy enough to write your own class and unit tests for Linked Lists and you will be much more familiar with the edge cases at the end of that exercise.
Good luck!
