Singly versus doubly linked lists

Understand the idea

A singly linked node stores next; a doubly linked node also stores previous. Backward links enable local removal when the node is known, but every operation must repair both directions.

Work through an example

Removing B from A↔B↔C requires A.next=C and C.prev=A. A singly linked list generally needs A as well as B to bypass B.

Time and space complexity

Known-node doubly linked removal O(1); locating it O(n); both structures use O(n) memory.

Why it works

For adjacent live nodes, x.next.prev is x and x.prev.next is x when those links exist.

Common mistakes

• Updating only one direction leaves a broken structure.
• Tail removal in a singly linked list needs its predecessor.

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)