07Module · Goodrich Ch. 7

Week 7 — Linked Lists

Singly, circularly, and doubly linked lists; the positional list ADT; link- vs array-based trade-offs.

Pointer-based sequences and the positional list ADT, with sorting and the move-to-front heuristic as case studies.

Theory

A linked list stores elements in nodes with explicit next (and optionally prev) pointers, giving O(1) insertion/deletion at known nodes.

Singly linked lists trade simplicity for O(n) reverse traversal; doubly linked lists pay extra memory for O(1) backward moves.

The positional list ADT exposes nodes via opaque positions — clients move and mutate without knowing internal pointers.

Key points

Sentinel head/tail nodes simplify edge cases.
Floyd's two-pointer trick detects cycles in O(n) and O(1) space.
Linked lists lose to arrays for random access (O(n) vs O(1)) and cache locality.

Code examples

Singly linked list — insert at head

class Node:
    __slots__ = "value", "next"
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def push_front(self, v):
        self.head = Node(v, self.head)
        self.size += 1

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

Reverse a singly linked list

def reverse(head):
    prev, cur = None, head
    while cur:
        cur.next, prev, cur = prev, cur, cur.next
    return prev