An array stores items in a contiguous block of memory. A linked list stores items as nodes scattered across memory, each pointing to the next node.

Structure of a Linked List

[data|next] -> [data|next] -> [data|next] -> None
   head          node 1         node 2

Each node contains:

• data — the actual value
• next — a pointer/reference to the next node

The list ends when next is None.

🔗 Interactive Linked List Visualizer

Each node has a data field and a next pointer. The head points to the first node. The last node points to None.

Practice 1

1. What is the advantage of a linked list over a Python list (array)?
2. What is the disadvantage?

Implementing a Linked List

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

class LinkedList:
    def __init__(self):
        self.head = None
    
    def insert(self, data):    # Insert at front: O(1)
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    def find(self, target):    # Traverse: O(n)
        current = self.head
        while current:
            if current.data == target:
                return current
            current = current.next
        return None
    
    def delete(self, target):  # Traverse + reconnect: O(n)
        current = self.head
        prev = None
        while current:
            if current.data == target:
                if prev: prev.next = current.next
                else: self.head = current.next
                return True
            prev, current = current, current.next
        return False

Practice 2

1. Implement a method to traverse the linked list and return the data as a Python list.
2. Implement insert_at_end(data) that adds a new node to the tail of the list.

A binary tree is a hierarchical structure where each node has at most two children: left and right.

Binary Search Tree (BST)

A BST is a binary tree where for every node:

• All values in the left subtree are less than the node
• All values in the right subtree are greater than the node

Tree traversal — In-order:

def inorder(node):
    if node:
        inorder(node.left)     # Visit left
        print(node.data)       # Visit node
        inorder(node.right)    # Visit right
# Result: sorted order!

Practice 1

1. Draw the BST that results from inserting: 5, 3, 7, 2, 4, 6, 8
2. What is the in-order traversal of this tree?

Searching in a BST

def find(node, target):
    current = node
    while current:
        if current.data == target: return True
        elif target < current.data: current = current.left
        else: current = current.right
    return False

Practice 2

1. Implement a pre-order traversal (node → left → right).
2. Write a function to count the total number of nodes in a binary tree.