Structures defined by how you add and remove. Linked lists trade index access for O(1) splicing; stacks are last-in-first-out; queues are first-in-first-out. Plus the fast & slow pointer pattern.
A linked list stores each element in a node that points to the next, so the elements are not contiguous in memory. This flips the array’s trade-offs: there is no O(1) indexing (you must walk from the head, O(n)), but inserting or deleting at a known node is O(1) because you just re-point, with no shifting. They shine when you splice frequently and rarely random-access.
class Node:
def __init__(self, val, nxt=None):
self.val = val
self.next = nxt
# build 1 -> 2 -> 3
head = Node(1, Node(2, Node(3)))
# traverse — O(n), no random access
node = head
while node:
print(node.val)
node = node.next
# insert 9 after head — O(1), just re-point, NO shifting
head.next = Node(9, head.next) # 1 -> 9 -> 2 -> 3
# array insert in the middle is O(n); linked-list insert at a node is O(1).Reversing a singly linked list in place is a canonical exercise because it drills the core skill of pointer manipulation: walk the list re-pointing each node backward while carefully holding the next node so you do not lose the rest. It is O(n) time and O(1) space, and the three-pointer dance (prev, curr, next) recurs across many linked-list problems.
def reverse(head):
prev = None
curr = head
while curr:
nxt = curr.next # 1. save the rest before we overwrite
curr.next = prev # 2. re-point this node backward
prev = curr # 3. advance prev
curr = nxt # 4. advance curr
return prev # new head
# 1->2->3 becomes 3->2->1
# O(n) time, O(1) space. Master the prev/curr/nxt pattern — it's everywhere.Running two pointers at different speeds through a linked list solves a family of problems elegantly. A slow pointer moving one step and a fast pointer moving two will meet if there is a cycle (Floyd’s algorithm) and put slow at the middle when fast reaches the end — both in O(n) time and O(1) space, with no extra data structure.
# detect a cycle: if fast ever meets slow, there's a loop — O(n) time, O(1) space
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # +1
fast = fast.next.next # +2
if slow is fast: # they meet -> cycle
return True
return False
# find the middle node: when fast hits the end, slow is at the middle
def middle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
return slowA stack only allows adding and removing at one end — the top — giving last-in-first-out order, with O(1) push and pop. It models anything nested or needing reversal: matching brackets, undo history, the call stack itself. In Python a plain list is a stack (append/pop). Recognizing "this problem needs the most recent unmatched thing" signals a stack.
stack = []
stack.append(1) # push — O(1)
stack.append(2)
stack.pop() # pop the top (2) — O(1) -> LIFO
# classic use: are the brackets balanced?
def valid_parens(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for c in s:
if c in "([{":
stack.append(c)
elif c in pairs:
if not stack or stack.pop() != pairs[c]: # top must match
return False
return not stack # all opened were closed
valid_parens("([]{})") # True ; valid_parens("(]") -> FalseA queue adds at one end and removes from the other — first-in-first-out — which is exactly the order you process things in breadth-first search and scheduling. Use collections.deque, which gives O(1) at both ends (a list’s pop(0) is O(n)). A deque is a double-ended queue, the flexible tool behind queues, sliding-window problems, and more.
from collections import deque
q = deque()
q.append(1) # enqueue at the back — O(1)
q.append(2)
q.popleft() # dequeue from the front (1) — O(1) -> FIFO
# a deque also does both ends — used for sliding windows, BFS, etc.
dq = deque([1, 2, 3])
dq.appendleft(0) # O(1) at the front
dq.pop() # O(1) at the back
# WARNING: don't use list.pop(0) as a queue — it's O(n) (shifts everything).
# deque.popleft() is O(1). BFS (graphs lesson) relies on this.