Insert, delete, and reverse

Understand the idea

Insertion connects a new node to the successor before connecting its predecessor to it. Deletion bypasses a node. Reversal must save the next unread reference before redirecting current.next.

Work through an example

The lab reverses 1→2→3 by saving 2, redirecting 1 to None, then repeating. Returning previous yields head 3, not the original head 1.

Time and space complexity

Reversal O(n) time/O(1) auxiliary space; known-predecessor insert/delete O(1).

Why it works

Previous heads the reversed prefix; current heads the unread suffix; together they contain every original node.

Common mistakes

• Redirecting current.next before saving it loses the suffix.
• Callers must use the returned head.

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)