Sentinel nodes and edge cases

Understand the idea

A sentinel is a dummy node that removes special cases around the head. It does not represent user data. Returning sentinel.next gives the real result.

Work through an example

Deleting value 1 from 1→2 uses dummy→1→2; the same predecessor.next bypass rule works for the first or any later node.

Time and space complexity

O(1) dummy storage; traversal remains O(n).

Why it works

The sentinel precedes the current real list, including the empty list.

Common mistakes

• Returning the dummy includes fake data.
• A sentinel simplifies boundaries but does not remove all None checks.

Chapter lab · Python implementation

A linked list stores values in nodes connected by references. The lab reverses links while retaining the next unread node. Draw references as arrows: changing a link does not move a node in memory. Ordered traversal is cheap; locating an arbitrary position still requires walking from a known node.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

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

def reverse(head):
    previous=None
    current=head
    while current is not None:
        following=current.next
        current.next=previous
        previous,current=current,following
    return previous

def values(head):
    output=[]
    while head is not None:
        output.append(head.value)
        head=head.next
    return output

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

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

head=Node(1,Node(2,Node(3)))
assert values(reverse(head))==[3,2,1]
assert reverse(None) is None
assert not has_cycle(Node(1))
a=Node(1); b=Node(2,a); a.next=b; assert has_cycle(a)