Linked Lists

Head
 |
[10] → [20] → [30] → [40] → None

Each box = Node(value, next_pointer)
Head points to the first node.
Last node's next = None (sentinel).

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None   # pointer to the next node

class LinkedList:
    def __init__(self):
        self.head = None   # empty list
        self.size = 0

    def __len__(self):
        return self.size

    def __repr__(self):
        nodes, cur = [], self.head
        while cur:
            nodes.append(str(cur.value))
            cur = cur.next
        return ' → '.join(nodes) + ' → None'

# Usage
ll = LinkedList()
print(ll)   # → None

def traverse(self):
    current = self.head
    while current is not None:
        print(current.value)
        current = current.next

def search(self, target):
    current = self.head
    index = 0
    while current:
        if current.value == target:
            return index
        current = current.next
        index += 1
    return -1   # not found

def prepend(self, value):
    """Insert at head — O(1)"""
    new_node = Node(value)
    new_node.next = self.head   # new node points to old head
    self.head = new_node        # head moves to new node
    self.size += 1

def append(self, value):
    """Insert at tail — O(n): must walk to the end"""
    new_node = Node(value)
    if self.head is None:
        self.head = new_node
    else:
        current = self.head
        while current.next:       # walk to last node
            current = current.next
        current.next = new_node   # link last node to new
    self.size += 1

def insert_after(self, target, value):
    """Insert after a value — O(n)"""
    current = self.head
    while current:
        if current.value == target:
            new_node = Node(value)
            new_node.next = current.next
            current.next = new_node
            self.size += 1
            return
        current = current.next

def delete(self, value):
    """Remove first occurrence of value — O(n)"""
    if self.head is None:
        return

    # Special case: deleting the head
    if self.head.value == value:
        self.head = self.head.next
        self.size -= 1
        return

    # Walk until prev.next holds the target node
    prev, current = None, self.head
    while current:
        if current.value == value:
            prev.next = current.next   # bypass the node
            self.size -= 1
            return
        prev, current = current, current.next