DSA · Chapter 13 of 40
Linked Lists
A linked list stores each element in a node that holds a value and a reference to the next node. Unlike an array, nodes are not contiguous, so there is no O(1) index access — you must walk from the head.
The benefit is O(1) insertion and deletion once you hold a reference to the node, which makes linked lists useful for queues, LRU caches and adjacency lists.
Costs
Access/search O(n), insert or delete at the head O(1), insert or delete after a known node O(1).
Head pointer
The list is only reachable through the head, so losing it loses the whole list. Many bugs come from reassigning head carelessly.
Example 1 (python)
class Node:
def __init__(self, val):
self.val = val
self.next = None
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
cur = head
while cur:
print(cur.val, end=' ')
cur = cur.nextOutput
1 2 3Traversal walks node by node until None.
Example 2 (python)
# insert at head is O(1)
new = Node(0)
new.next = head
head = new
print(head.val, head.next.val)Output
0 1No shifting is needed, unlike an array.
Key points
- Nodes hold a value and a pointer to the next node.
- No random access — searching is O(n).
- Insert/delete at a known position is O(1).
- Always guard against None while traversing.
💡 Note: Draw the pointers on paper before writing linked-list code.