08. Linked Lists

What you'll learn

• 1Build singly, doubly, and circular linked lists
• 2Distinguish reference assignment from copy
• 3Use the dummy-head trick to simplify edge cases

Overview

Linked lists rarely outperform Python lists for competitive programming, but they're a great vehicle for learning pointer manipulation — which is the core skill for trees, graphs, and many advanced data structures.

Core Concepts

1. Node class

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

2. Singly linked list

class SinglyList:
    def __init__(self):
        self.head = None

    def push_front(self, val):
        self.head = Node(val, self.head)

    def push_back(self, val):
        if not self.head:
            self.head = Node(val)
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = Node(val)

    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.val
            cur = cur.next

3. Dummy head trick

Insert/delete at the head needs a special case (modifying self.head). Use a dummy node so every position is treated the same.

dummy = Node(0)
dummy.next = head
cur = dummy
while cur.next and cur.next.val != target:
    cur = cur.next
if cur.next:
    cur.next = cur.next.next   # delete
head = dummy.next

4. Doubly linked list

Each node has both .prev and .next. Insertion and deletion at an arbitrary position is O(1) when you already hold a reference to the node.

5. Circular list

The last node's .next points back to head. Useful for round-robin schedulers and Josephus-style problems.

Examples

Example 1 — src/01_singly.py

Full singly-linked list with push/pop/find.

Example 2 — src/02_doubly.py

Doubly-linked list with O(1) insert/delete given a node ref.

Example 3 — src/03_reverse.py

Reverse a singly linked list iteratively and recursively — the canonical interview problem.

Example 4 — src/04_circular_josephus.py

Josephus problem with a circular linked list.

Common Mistakes

1. Losing the head reference: `head = head.next` in a loop drops earlier nodes.
2. Forgetting to set the new tail's `.next = None` after operations.
3. Confusing `cur.next = something` (modifies the list) with `cur = cur.next` (just moves the cursor).
4. Not using a dummy head — leads to messy special-case code for the first node.
5. Building a linked list in pure Python for a BOJ problem that just needs a list / deque.

Recap

• Linked lists are about pointer manipulation, not raw performance.
• Dummy head + cur cursor pattern simplifies edge cases.
• Doubly = O(1) delete-by-node. Circular = wraparound.

Try It

1. Reverse a linked list iteratively.
2. Detect a cycle with Floyd's tortoise & hare.