Linked Lists
A linked list is a dynamic data structure made of nodes, where each node stores a value and a pointer to the next node. The nodes are not stored in contiguous memory, allowing fast insertions and deletions, but requiring sequential traversal to access elements.
Types of linked lists
1. Singly linked list
Each node holds a value and a pointer to the next node. Since nodes are linked in one direction, operations like inserting at the head or deleting after a known node take O(1) time. Singly linked lists are simple, memory-efficient, and commonly used in queues, stacks, adjacency lists in graphs, and problems involving fast/slow pointer techniques (detecting cycles, finding the middle, removing Nth from end).
2. Doubly linked list
Each node stores a value, a pointer to the next, and a pointer to the previous node. This enables efficient bidirectional traversal and makes deletions or insertions easier because you don’t need to search for the previous node first. Doubly linked lists are the backbone of LRU cache, navigation systems (back/forward), playlist management, and any structure where moving both directions matters.
3. Circular linked list
In a circular list, the tail doesn’t point to null; it loops back to the head. This means traversal can continue indefinitely until a stopping condition is applied. Circular linked lists are useful in round-robin scheduling, multiplayer turn rotation, buffering/streaming scenarios, and implementing queues where end-to-end wrapping avoids extra pointer checks. They eliminate the need for special-case logic at the tail.
Common linked list patterns
Common linked list operations
1. Insert a node at the head
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
# Create a new node and point it to current head
new_node = ListNode(val)
new_node.next = head
return new_node # new head2. Remove first occurrence of a value
def remove_first(head, target):
dummy = ListNode(0, head)
prev, curr = dummy, head
# Traverse until we find the node to remove
while curr:
if curr.val == target:
prev.next = curr.next # unlink
break
prev, curr = curr, curr.next
return dummy.next # new head (may change)3. Traverse a linked list
def traverse(head):
curr = head
while curr:
print(curr.val)
curr = curr.next
Calculating memory usage
The memory usage of a linked list is slightly more complex than an array. In addition to the data we are storing in each node, we are also storing the pointers between nodes: a singly-linked list has one pointer for every node and a doubly-linked list has two pointers. Typically a memory pointer today is an 8-byte memory address (for software running on 64-bit machines).
Question: What is the memory usage of a doubly-linked list that contains one million 32-bit integers?
Answer: 10^6 * (32 bits + 64 bits * 2) = 10^6 * 20 bytes = 20 MB
Common edge cases & pitfalls in linked lists
-
Empty list / single-node list: Handle
head == nulland one-element operations (insert/remove/reverse) without dereferencingnull. -
Head/tail updates: After insert/remove at the front or back, correctly set the new head/tail and ensure the tail’s
next = null. -
Losing references: Always store next before rewiring pointers; otherwise nodes become unreachable (memory leak in C++).
-
Null-pointer access: Guard
curr.nextandprev.nextchecks; verifycurr != nullbefore dereferencing. -
Iteration while modifying: When inserting/removing during traversal, carefully move pointers to avoid skipping nodes or infinite loops.
Quiz
- Why are linked lists slow for random access?
a) They store values in descending order
b) They require contiguous memory
c) You must traverse nodes sequentially
d) They only store strings
- What is the time complexity of inserting a node after a given node?
a) O(log n)
b) O(1)
c) O(n)
d) O(n²)
- What happens if you reverse a linked list but forget to set the new tail’s next pointer to null?
a) Nothing happens
b) The list becomes sorted
c) You may create a cycle
d) The list prints in reverse automatically