Singly, doubly and circular linked lists

Linked nodes hold values and links. Singly linked lists have next; doubly linked lists add prev. A circular list ends by revisiting its start rather than encountering None. Sentinel nodes simplify boundaries but are not user data.

Insertion after a known node changes two links. Deleting a singly linked node generally requires its predecessor; knowing only the target is not always sufficient. Doubly linked deletion is O(1) when neighbours are known. Head and tail consistency belong to every operation's invariant.

Memory overhead includes pointers, allocation metadata and fragmentation; locality often loses to arrays. Floyd's two-speed traversal detects cycles. When reversing links, save the old next before overwriting it or the rest of the chain is lost.

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

def reverse(head):
    prev = None
    while head is not None:
        nxt = head.next
        head.next = prev
        prev, head = head, nxt
    return prev
head = reverse(Node(1, Node(2, Node(3))))
assert (head.value, head.next.value) == (3, 2)