Linked Lists

Linked Lists | Algoryva

First, the naive way

Adding at the front of a Python list

Suppose you constantly add items to the *front* of a sequence, such as an undo history. A Python list stores items in side-by-side slots, so a new first item forces every existing item to shift one slot right.

The shift is invisible in the code (a.insert(0, x)) but real: with 100,000 items, each insertion moves 100,000 items.

python

def build_front_insert(n):
    a = []
    for i in range(n):
        a.insert(0, i)       # shifts every existing item
    return a

print(build_front_insert(5))   # [4, 3, 2, 1, 0]

Cost: O(n) per insertion at the front, so O(n²) to build n items. A node-based list does the same in O(1) each.

Implementation

Build, walk, insert and delete

Two helpers (from_list, to_list) make experiments easy: convert a Python list into nodes and back.

python

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

def from_list(a):
    head = None
    for x in reversed(a):
        head = Node(x, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def push_front(head, v):
    return Node(v, head)

def delete_value(head, target):
    dummy = Node(0, head)
    prev = dummy
    while prev.next:
        if prev.next.val == target:
            prev.next = prev.next.next
            break
        prev = prev.next
    return dummy.next

h = from_list([1, 2, 3])
h = push_front(h, 0)
print(to_list(h))   # [0, 1, 2, 3]
h = delete_value(h, 2)
print(to_list(h))   # [0, 1, 3]
h = delete_value(h, 0)
print(to_list(h))   # [1, 3]

Reading the code

›from_list builds from the back: the last node is created first, and each earlier node points at the one built before it.
›push_front is a single line: the new node's next is the old head. That is the O(1) insertion the naive list could not do.
›delete_value uses a dummy node placed before the head. With it, deleting the first node is no different from deleting any other (prev.next = prev.next.next), so no special case is needed.
›return dummy.next returns the (possibly new) head.

Worked by hand

Reversal traced by hand

List 1 → 2 → 3 → 4. Start with prev = None, cur = 1. Each round does three things: remember cur.next, point cur.next at prev, move both forward.

round	cur	saved next	after flipping	prev becomes
1	1	2	1 → None	1
2	2	3	2 → 1	2
3	3	4	3 → 2	3
4	4	None	4 → 3	4

1
Why save next first
Once cur.next is overwritten, the link to the rest of the list is gone. Saving it in a variable is what lets the walk continue.
2
The result
When cur becomes None, prev is the last node we processed (4) and is the new head: 4 → 3 → 2 → 1.

Implementation

Reverse in code

Three pointers, one loop, O(1) extra space.

Plan in plain steps

pseudocode

prev = None
while cur exists:
    nxt = cur.next      # 1. remember the rest
    cur.next = prev     # 2. flip this arrow
    prev = cur          # 3. advance both
    cur = nxt
return prev

python

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

def from_list(a):
    head = None
    for x in reversed(a):
        head = Node(x, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

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

print(to_list(reverse(from_list([1, 2, 3, 4]))))   # [4, 3, 2, 1]
print(to_list(reverse(from_list([7]))))   # [7]
print(to_list(reverse(None)))   # []

Reading the code

›head is reused as the “current” pointer to save a variable; after the loop it is None.
›The four lines inside the loop are the only part that matters: save, flip, advance prev, advance cur.
›An empty list returns None immediately (prev is still None), and a single node ends up pointing at None, which it already did.

Implementation

Slow and fast pointers: the middle and cycles

Two pointers walk the same list at different speeds: slow one step at a time, fast two. When fast reaches the end, slow is halfway. And if the list has a cycle, fast eventually laps slow and they meet, like two runners on a circular track.

python

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

def from_list(a):
    head = None
    for x in reversed(a):
        head = Node(x, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.val

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

print(middle(from_list([1, 2, 3, 4, 5])))   # 3
print(middle(from_list([1, 2, 3, 4])))   # 3

a = Node(1)
b = Node(2)
c = Node(3)
a.next, b.next = b, c
print(has_cycle(a))   # False
c.next = b
print(has_cycle(a))   # True

Reading the code

›The loop condition fast and fast.next stops before fast.next.next would fail on None.
›For an even-length list there are two middles; this loop returns the second one (3 in [1, 2, 3, 4]).
›slow is fast compares *identity* (the same node object), not equal values.
›Without a cycle, fast hits None and the loop ends. With a cycle, fast gains one node on slow each round, so they must meet. Memory use is O(1), unlike remembering visited nodes in a set.

Implementation

Merging two sorted lists with a dummy node

Walk both lists, always appending the smaller front node to the result. A dummy head node means the first appended node needs no special handling.

python

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

def from_list(a):
    head = None
    for x in reversed(a):
        head = Node(x, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def merge(a, b):
    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(merge(from_list([1, 3, 5]), from_list([2, 4, 6]))))   # [1, 2, 3, 4, 5, 6]
print(to_list(merge(from_list([]), from_list([1, 2]))))   # [1, 2]

Reading the code

›No new nodes are created: the existing nodes are relinked, so extra space is O(1).
›When one list runs out, tail.next = a or b attaches the rest of the other, which is already sorted.
›The line tail.next, a = a, a.next evaluates the right side first, so a.next is read before a changes.

Worked problem

Remove the n-th node from the end

The problem

Given a linked list and n, remove the n-th node counting from the end, in a single pass, and return the head.

We do not know the length, so we cannot just count to a position.
Use two pointers n steps apart. When the front one reaches the end, the back one is exactly at the node *before* the one to remove.
A dummy head handles removal of the first node without a special case.

python

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

def from_list(a):
    head = None
    for x in reversed(a):
        head = Node(x, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def remove_nth_from_end(head, n):
    dummy = Node(0, head)
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

print(to_list(remove_nth_from_end(from_list([1, 2, 3, 4, 5]), 2)))   # [1, 2, 3, 5]
print(to_list(remove_nth_from_end(from_list([1]), 1)))   # []

Takeaway. Keeping two pointers a fixed distance apart turns “measure from the end” into one pass. The same trick appears in many problems; and the dummy node removed the head-deletion special case.

Worked problem

Is the list a palindrome?

The problem

Return True if the list reads the same forwards and backwards, using O(1) extra space.

Find the middle with slow and fast pointers.
Reverse the second half in place.
Walk the first half and the reversed second half together, comparing values.

python

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

def from_list(a):
    head = None
    for x in reversed(a):
        head = Node(x, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

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

def is_palindrome(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    half = reverse(slow)
    while half:
        if head.val != half.val:
            return False
        head, half = head.next, half.next
    return True

print(is_palindrome(from_list([1, 2, 3, 2, 1])))   # True
print(is_palindrome(from_list([1, 2, 3, 4])))   # False

Takeaway. Three small tools (middle, reverse, two-pointer comparison) compose into a new algorithm. Notice that this version leaves the list's second half reversed; restore it if the caller still needs the original.

Wrap-up

Remember this

A linked list stores order in pointers: cheap insertion and removal at a known spot, expensive access by index.
Always save next before changing it, and decide what to return as the new head.
A dummy node before the head removes special cases for inserting and deleting the first node.
Slow and fast pointers find the middle and detect cycles in O(n) time and O(1) space.
Linked lists suit many insertions at the ends, but arrays win when you need indexing or search.

Cheat sheet

Node: val + next; head is the first node, last next is None
Insert at head: Node(v, head) → O(1)
Delete after node: node.next = node.next.next → O(1)
Reverse: save next, flip, advance prev, advance cur
Middle / cycle: slow 1 step, fast 2 steps
Dummy node: put one before the head to remove head special cases

Top traps to avoid

Flipping cur.next before saving the old next.
Accessing fast.next.next without checking fast and fast.next.
Returning the wrong head after reversing or deleting.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What is the cost of inserting a new node at the head of a singly linked list?
2.In reverse, why must nxt = head.next come before head.next = prev?
3.What does middle(from_list([1, 2, 3, 4])) return with the lesson's loop?
4.“Detect a cycle in a linked list using O(1) extra memory” points to:
5.What does a dummy node before the head buy you?
6.Getting the 1,000th item of a linked list costs about:
7.Reverse the list 1 -> 2 -> 3 in place (standard pointer loop), then print the values in order. What is printed?
8.A list 1 -> 2 -> 3 -> 2 loops back to the node with value 2. Does Floyd's fast/slow pointer method detect the cycle?
9.In the list 1 -> 2 -> 3 -> 4 -> 5, with slow and fast both starting at the head (fast moves two steps), what value does slow end on?
10.Remove the 2nd node from the end of 1 -> 2 -> 3 -> 4 -> 5 using a dummy head and two pointers. What is the list afterwards?
11.Why is reaching the k-th element of a singly linked list O(k)?
12.Why use a dummy head node when deleting from a linked list?
13.Reverse 1 -> 2 in place and print the head's value. What is printed?
14.What is the classic bug when reversing a linked list?
15.Inserting a new node at the head of a singly linked list: what is the time?

Linked Lists

After this lesson you will be able to

Builds on

Unlocks

A treasure hunt

Adding at the front of a Python list

Links instead of positions

Anatomy of a singly linked list

Build, walk, insert and delete

Reading the code

Reversing a list, one pointer at a time

Reversal traced by hand

Reverse in code

Reading the code

Slow and fast pointers: the middle and cycles

Reading the code

Merging two sorted lists with a dummy node

Reading the code

Costs, and the trade against arrays

Edge cases

Mistakes to avoid

How to spot a linked-list problem

Remove the n-th node from the end

Is the list a palindrome?

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up3 problems

Core4 problems

Application4 problems

Challenge1 problem