Linked Lists

#Topic: Complete Implementation of Singly Linked List
# Time  : append O(1), prepend O(1), delete O(n), search O(n)
#Space: O(n) -- Number of nodes

from __future__ import annotations
from typing import Any


class Node:
    """Node of a linked list."""

    def __init__(self, data: Any) -> None:
        self.data = data
        self.next: Node | None = None


class SinglyLinkedList:
    """Singly linked list."""

    def __init__(self) -> None:
        self.head: Node | None = None
        self.tail: Node | None = None
        self._size: int = 0

    def append(self, data: Any) -> None:
        """Add a node at the very end -- O(1) (using the tail pointer)."""
        new_node = Node(data)
        if self.tail is None:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self._size += 1

    def prepend(self, data: Any) -> None:
        """Add a node at the very front -- O(1)."""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        if self.tail is None:
            self.tail = new_node
        self._size += 1

    def delete(self, data: Any) -> bool:
        """Delete the first node whose value is data -- O(n).

        Returns:
            True if deleted, False if not found."""
        if self.head is None:
            return False

        #When the head node is the target for deletion
        if self.head.data == data:
            self.head = self.head.next
            if self.head is None:
                self.tail = None
            self._size -= 1
            return True

        #Searching for a middle or end node
        prev = self.head
        cur  = self.head.next
        while cur is not None:
            if cur.data == data:
                prev.next = cur.next
                if cur.next is None:    #Deleting the tail
                    self.tail = prev
                self._size -= 1
                return True
            prev = cur
            cur  = cur.next
        return False

    def search(self, data: Any) -> int:
        """Returns the index of the node with the value 'data' -- O(n). Returns -1 if not found."""
        idx = 0
        cur = self.head
        while cur is not None:
            if cur.data == data:
                return idx
            cur = cur.next
            idx += 1
        return -1

    def get(self, index: int) -> Any:
        """Lookup value by index -- O(n)."""
        if index < 0 or index >= self._size:
            raise IndexError(f"Index {index} out of range (size: {self._size})")
        cur = self.head
        for _ in range(index):
            cur = cur.next  # type: ignore[union-attr]
        return cur.data  # type: ignore[union-attr]

    def size(self) -> int:
        """List size -- O(1)."""
        return self._size

    def display(self) -> str:
        """Represent the list as a string."""
        parts = []
        cur = self.head
        while cur is not None:
            parts.append(str(cur.data))
            cur = cur.next
        return " -> ".join(parts) + " -> None"


if __name__ == "__main__":
    print("=" * 55)
    print("Singly Linked List Demo")
    print("=" * 55)

    ll = SinglyLinkedList()

    # append
    for v in [1, 2, 3, 4, 5]:
        ll.append(v)
        print(f"append({v}): {ll.display()}")

    print()
    # prepend
    ll.prepend(0)
    print(f"prepend(0): {ll.display()}")

    print()
    # search
    for v in [0, 3, 9]:
        idx = ll.search(v)
        print(f"search({v}) -> Index {idx}")

    print()
    # get
    for i in [0, 3, 5]:
        print(f"get({i}) -> {ll.get(i)}")

    print()
    # delete
    for v in [0, 3, 5, 99]:
        deleted = ll.delete(v)
        print(f"delete({v}) -> {'Success' if deleted else 'None'}: {ll.display()}")

    print()
    print(f"Final size: {ll.size()}")

#Topic: Doubly Linked List
# Time  : insert/delete O(1) at known node, search O(n)
#Space: O(n) -- number of nodes (each node prev+next overhead)

from __future__ import annotations
from typing import Any


class DNode:
    """Doubly linked list node -- holds prev and next pointers."""

    def __init__(self, data: Any) -> None:
        self.data = data
        self.prev: DNode | None = None
        self.next: DNode | None = None


class DoublyLinkedList:
    """Doubly linked list."""

    def __init__(self) -> None:
        self.head: DNode | None = None
        self.tail: DNode | None = None
        self._size: int = 0

    def append(self, data: Any) -> None:
        """Add to the very end -- O(1)."""
        new_node = DNode(data)
        if self.tail is None:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self._size += 1

    def prepend(self, data: Any) -> None:
        """Add to the very front -- O(1)."""
        new_node = DNode(data)
        if self.head is None:
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self._size += 1

    def insert_after(self, node: DNode, data: Any) -> None:
        """Insert after a specific node -- O(1)."""
        new_node = DNode(data)
        new_node.prev = node
        new_node.next = node.next

        if node.next is not None:
            node.next.prev = new_node
        else:
            self.tail = new_node   #Node was tail

        node.next = new_node
        self._size += 1

    def delete_node(self, node: DNode) -> None:
        """Direct node deletion -- O(1) (when there is a reference to the node)."""
        if node.prev is not None:
            node.prev.next = node.next
        else:
            self.head = node.next   #Delete head

        if node.next is not None:
            node.next.prev = node.prev
        else:
            self.tail = node.prev   #Deleting the tail

        self._size -= 1

    def delete_by_value(self, data: Any) -> bool:
        """Delete by value -- O(n)."""
        cur = self.head
        while cur is not None:
            if cur.data == data:
                self.delete_node(cur)
                return True
            cur = cur.next
        return False

    def display_forward(self) -> str:
        """Print from front to back."""
        parts = []
        cur = self.head
        while cur is not None:
            parts.append(str(cur.data))
            cur = cur.next
        return " <-> ".join(parts)

    def display_backward(self) -> str:
        """Print from back to front."""
        parts = []
        cur = self.tail
        while cur is not None:
            parts.append(str(cur.data))
            cur = cur.prev
        return " <-> ".join(parts)

    def size(self) -> int:
        return self._size


if __name__ == "__main__":
    print("=" * 55)
    print("Doubly linked list demo")
    print("=" * 55)

    dll = DoublyLinkedList()

    for v in [1, 2, 3, 4, 5]:
        dll.append(v)

    print("Initial:", dll.display_forward())
    print("Reverse:", dll.display_backward())

    print()
    dll.prepend(0)
    print("prepend(0):", dll.display_forward())

    #Insert after a specific node
    cur = dll.head
    while cur and cur.data != 3:
        cur = cur.next
    if cur:
        dll.insert_after(cur, 99)
        print("insert_after(3, 99):", dll.display_forward())

    print()
    for v in [0, 3, 99, 5]:
        dll.delete_by_value(v)
        print(f"delete({v}): {dll.display_forward()}")

    print()
    print(f"Final size: {dll.size()}")
    print("Check reverse:", dll.display_backward())

#Topic: Circular Linked List
# Time  : append O(1), delete O(n), traverse O(n)
#Space: O(n) -- Number of nodes

from __future__ import annotations
from typing import Any


class CNode:
    """Circular linked list node."""

    def __init__(self, data: Any) -> None:
        self.data = data
        self.next: CNode | None = None


class CircularLinkedList:
    """Circular Singly Linked List.

    The next of the last node points to the head.

    Structure:
      head
       |
      [1] -> [2] -> [3] -> [4]
       ^                    |
       +--------------------+"""

    def __init__(self) -> None:
        self.head: CNode | None = None
        self._size: int = 0

    def append(self, data: Any) -> None:
        """Add a node at the end -- O(n) (traverse from head without tail)."""
        new_node = CNode(data)
        if self.head is None:
            self.head = new_node
            new_node.next = self.head   #Points to itself
        else:
            #Find the last node
            tail = self.head
            while tail.next is not self.head:
                tail = tail.next  # type: ignore[assignment]
            tail.next = new_node
            new_node.next = self.head
        self._size += 1

    def prepend(self, data: Any) -> None:
        """Add a node at the very front -- O(n) (need to traverse because the tail has to be updated)."""
        new_node = CNode(data)
        if self.head is None:
            self.head = new_node
            new_node.next = self.head
        else:
            tail = self.head
            while tail.next is not self.head:
                tail = tail.next  # type: ignore[assignment]
            new_node.next = self.head
            tail.next = new_node
            self.head = new_node
        self._size += 1

    def delete(self, data: Any) -> bool:
        """Delete the first node with the value data -- O(n)."""
        if self.head is None:
            return False

        #Special handling for deleting head
        if self.head.data == data:
            if self._size == 1:
                self.head = None
            else:
                #tail's next to new head
                tail = self.head
                while tail.next is not self.head:
                    tail = tail.next  # type: ignore[assignment]
                tail.next = self.head.next
                self.head = self.head.next
            self._size -= 1
            return True

        prev = self.head
        cur  = self.head.next
        while cur is not self.head:
            if cur.data == data:  # type: ignore[union-attr]
                prev.next = cur.next  # type: ignore[union-attr]
                self._size -= 1
                return True
            prev = cur  # type: ignore[assignment]
            cur  = cur.next  # type: ignore[union-attr]
        return False

    def display(self, max_steps: int = 20) -> str:
        """Represent the list as a string (up to max_steps items)."""
        if self.head is None:
            return "Empty"
        parts = []
        cur = self.head
        steps = 0
        while steps < max_steps:
            parts.append(str(cur.data))
            cur = cur.next  # type: ignore[assignment]
            steps += 1
            if cur is self.head:
                break
        return " -> ".join(parts) + " -> (head)"

    def josephus(self, k: int) -> list[Any]:
        """Josephus Problem: Return the order of removal every k-th -- O(n*k)."""
        if self.head is None:
            return []
        order = []
        cur = self.head
        while self._size > 0:
            for _ in range(k - 1):
                cur = cur.next  # type: ignore[assignment]
            order.append(cur.data)
            next_cur = cur.next
            self.delete(cur.data)
            cur = next_cur if self.head else None
        return order

    def size(self) -> int:
        return self._size


if __name__ == "__main__":
    print("=" * 55)
    print("Circular Linked List Demo")
    print("=" * 55)

    cll = CircularLinkedList()

    for v in [1, 2, 3, 4, 5]:
        cll.append(v)
        print(f"append({v}): {cll.display()}")

    print()
    cll.prepend(0)
    print(f"prepend(0): {cll.display()}")

    print()
    for v in [0, 3, 5]:
        deleted = cll.delete(v)
        print(f"delete({v}) -> {'Success' if deleted else 'None'}: {cll.display()}")

    print()
    print("=" * 55)
    print("Josephus Problem (n=6, k=2)")
    print("=" * 55)
    cll2 = CircularLinkedList()
    for v in range(1, 7):
        cll2.append(v)
    order = cll2.josephus(2)
    print("Removal order:", order)

#Topic: Major Linked List Problems -- Reversal, Cycle Detection, Middle Node
# Time  : reverse O(n), cycle O(n), middle O(n)
# Space : reverse O(1), cycle O(1), middle O(1)

from __future__ import annotations
from typing import Any


class Node:
    def __init__(self, data: Any) -> None:
        self.data = data
        self.next: Node | None = None


def build_list(values: list[Any]) -> Node | None:
    """Create a linked list from a list (helper function)."""
    if not values:
        return None
    head = Node(values[0])
    cur = head
    for v in values[1:]:
        cur.next = Node(v)
        cur = cur.next
    return head


def to_list(head: Node | None) -> list[Any]:
    """Convert a linked list to a Python list (helper function)."""
    result = []
    cur = head
    while cur is not None:
        result.append(cur.data)
        cur = cur.next
    return result


# ------------------------------------------------------------------
#1. Linked List Reversal (Reverse)
# ------------------------------------------------------------------
def reverse_iterative(head: Node | None) -> Node | None:
    """Iterative reversal -- Time O(n), Space O(1).

    Using 3 pointers:
      prev: previous node
      cur : current node
      nxt : next node (temporary storage)"""
    prev: Node | None = None
    cur = head
    while cur is not None:
        nxt = cur.next      #1. Store the next node
        cur.next = prev     #2. Reverse direction
        prev = cur          #3. Move prev forward
        cur = nxt           #4. Move cur forward
    return prev             #New head


def reverse_recursive(head: Node | None) -> Node | None:
    """Recursive reversal -- Time O(n), Space O(n) call stack.

    Base case: Node is absent or a single node."""
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head   #Previous node points to current
    head.next = None        #Current becomes the last node
    return new_head


# ------------------------------------------------------------------
#2. Cycle Detection -- Floyd's Tortoise and Hare
# ------------------------------------------------------------------
def has_cycle(head: Node | None) -> bool:
    """Returns whether a cycle exists -- Time O(n), Space O(1).

    Slow pointer (1 step) vs fast pointer (2 steps):
    If there is a cycle, the two pointers will definitely meet."""
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next          # type: ignore[union-attr]
        fast = fast.next.next
        if slow is fast:
            return True
    return False


def find_cycle_start(head: Node | None) -> Node | None:
    """Return the start node of the cycle -- Time O(n), Space O(1).

    Floyd's algorithm step 2:
    Step 1: Find the meeting point using slow/fast pointers
    Step 2: Move one pointer to the head and move both 1 step at a time
           -> The meeting point is the start of the cycle"""
    slow = head
    fast = head

    #Step 1: Find a meeting point
    while fast is not None and fast.next is not None:
        slow = slow.next          # type: ignore[union-attr]
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None   #No cycle

    #Step 2: Move head and meeting point simultaneously
    slow = head
    while slow is not fast:
        slow = slow.next  # type: ignore[union-attr]
        fast = fast.next  # type: ignore[union-attr]
    return slow


# ------------------------------------------------------------------
#3. Find the middle node (Fast & Slow Pointer)
# ------------------------------------------------------------------
def find_middle(head: Node | None) -> Node | None:
    """Return the middle node of a linked list -- Time O(n), Space O(1).

    Slow (1 step) / fast (2 steps) pointer:
    When the fast pointer reaches the end, the slow pointer is at the middle."""
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next          # type: ignore[union-attr]
        fast = fast.next.next
    return slow


if __name__ == "__main__":
    print("=" * 55)
    print("Linked List Reversal")
    print("=" * 55)

    test_cases = [[1, 2, 3, 4, 5], [1], [], [1, 2]]
    for vals in test_cases:
        head = build_list(vals)
        rev_iter = reverse_iterative(build_list(vals))
        rev_rec  = reverse_recursive(build_list(vals))
        print(
            f"{vals} -> "
            f"Iterative: {to_list(rev_iter)} |"
            f"Recursive: {to_list(rev_rec)}"
        )

    print()
    print("=" * 55)
    print("Cycle Detection -- Floyd's Algorithm")
    print("=" * 55)

    #List without cycle
    head_no_cycle = build_list([1, 2, 3, 4, 5])
    print("No cycle:", has_cycle(head_no_cycle))  # False

    #Directly create a list with cycle
    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    n5 = Node(5)
    n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n5
    n5.next = n3   #Cycle: 5 -> 3
    print("Has cycle:", has_cycle(n1))  # True
    start = find_cycle_start(n1)
    print("Cycle start node:", start.data if start else None)  # 3

    print()
    print("=" * 55)
    print("Find middle node")
    print("=" * 55)
    for vals in [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 6], [1]]:
        head = build_list(vals)
        mid = find_middle(head)
        print(f"{vals} -> Middle: {mid.data if mid else None}")