Data Structures & Algorithms

Array:     [10] [20] [30] [40]  ← All in a row, numbered boxes

Linked:    [10|→] → [20|→] → [30|→] → [40|X]
           Each box points to the next
           X means "end" (null/None)

# Step 1: Create a Node class
class Node:
    def __init__(self, data):
        self.data = data    # The value we store
        self.next = None    # Pointer to next node (starts as nothing)

# Step 2: Create the Linked List class
class LinkedList:
    def __init__(self):
        self.head = None    # Points to first node
    
    # Add to the END - O(n) because we traverse entire list
    def append(self, data):
        new_node = Node(data)
        
        # If list is empty, new node becomes head
        if not self.head:
            self.head = new_node
            return
        
        # Otherwise, travel to the end
        current = self.head
        while current.next:      # Keep going until no next
            current = current.next
        current.next = new_node  # Link last node to new node
    
    # Add to the BEGINNING - O(1) Super fast!
    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head  # New node points to old head
        self.head = new_node       # New node becomes new head
    
    # Print all values
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" → ".join(elements))

# Let's use it!
my_list = LinkedList()
my_list.append(10)
my_list.append(20)
my_list.append(30)
my_list.display()  # Output: 10 → 20 → 30

my_list.prepend(5)
my_list.display()  # Output: 5 → 10 → 20 → 30

Before:  HEAD → [10] → [20] → [30] → X

Step 1: Create new node [5]
Step 2: Point [5] → HEAD (which is [10])
Step 3: Update HEAD → [5]

After:   HEAD → [5] → [10] → [20] → [30] → X

Only 3 operations! Always O(1)!

def delete(self, data):
    # Special case: deleting head
    if self.head and self.head.data == data:
        self.head = self.head.next  # Skip the head
        return
    
    # Find the node BEFORE the one to delete
    current = self.head
    while current.next:
        if current.next.data == data:
            current.next = current.next.next  # Skip over it!
            return
        current = current.next

Before:  [10] → [20] → [30] → X
Delete 20:
         [10] → [30] → X  (20 is skipped!)

class DoublyNode:
    def __init__(self, data):
        self.data = data
        self.prev = None  # Points backward
        self.next = None  # Points forward

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None  # Also track the end!
    
    def append(self, data):
        new_node = DoublyNode(data)
        if not self.head:
            self.head = self.tail = new_node
            return
        
        new_node.prev = self.tail  # New node points back to old tail
        self.tail.next = new_node  # Old tail points forward to new
        self.tail = new_node       # Update tail

Singly Linked List:
  HEAD → [10] → [20] → [30] → NULL

Circular Linked List:
  HEAD → [10] → [20] → [30] ┐
           └─────────────────┘
  Last node points back to HEAD!

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

class CircularLinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head  # Points to itself!
            return
        
        # Traverse to last node
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head  # Complete the circle
    
    def display(self):
        if not self.head:
            return
        current = self.head
        while True:
            print(current.data, end=" → ")
            current = current.next
            if current == self.head:  # Back to start
                break
        print("(back to head)")

cll = CircularLinkedList()
cll.append(10)
cll.append(20)
cll.append(30)
cll.display()  # 10 → 20 → 30 → (back to head)

  ┌───────────────────────────────┐
  │                               │
  └─ [←|10|→] ↔ [←|20|→] ↔ [←|30|→] ┘

  • Last node's NEXT → First node
  • First node's PREV → Last node
  • Traversal in BOTH directions, continuously

# Reversing a Singly Linked List (Classic Question)
def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

# Finding Middle of a Linked List (Slow/Fast Pointer)
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow