PART 4 · DSA AND COMPLEXITY · CHAPTER 22
Linked lists: the three classics
FreeLesson 47 of 78
Rare in DE loops, common in SDE loops. Python has no built-in linked list, so learn these three and move on.
In plain words: each node holds a value and a pointer to the next node, like a treasure hunt where each clue tells you where the next one is. You cannot jump to item 5 directly (O(n) to reach it), but you can add or remove a node anywhere in O(1) once you are standing next to it.
from dataclasses import dataclass
@dataclass
class Node:
val: int
next: "Node | None" = None
def build(vals):
head = None
for v in reversed(vals):
head = Node(v, head)
return head
def to_list(head):
out = []
while head:
out.append(head.val); head = head.next
return out
def reverse(head): # O(n) time, O(1) space
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prev
def has_cycle(head): # Floyd: slow and fast pointers
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
return True
return False
def merge(a, b): # two sorted lists
dummy = tail = Node(0)
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
return dummy.next
print(to_list(reverse(build([1, 2, 3, 4]))))
loop = build([1, 2, 3]); loop.next.next.next = loop.next
print(has_cycle(loop), has_cycle(build([1, 2, 3])))
print(to_list(merge(build([1, 4, 9]), build([2, 3, 10]))))Output
[4, 3, 2, 1] True False [1, 2, 3, 4, 9, 10]
| Operation | Python list (array) | Linked list |
|---|---|---|
| Read item i | O(1) | O(n): walk from the head |
| Insert or delete at the front | O(n): shift everything | O(1) |
| Insert or delete next to a node you hold | O(n) | O(1) |
| Memory | Compact | Extra pointer per item |
Practice before you move on
- Build a linked list from the order_ids of orders.csv and reverse it.
- Create a cycle on purpose and check that the detector finds it.