Linked Lists

Introduction to Linked Lists

After mastering Arrays, it's time to look at the next major data structure: the Linked List.

Arrays are great, but they have a massive weakness: inserting or deleting items in the middle is extremely slow because you have to shift everything over. Linked Lists solve this exact problem!

1. What is a Linked List?

A Linked List is a chain of items. Each item in the chain is called a Node.

Every Node contains two important pieces of information:

1. Data: The actual value you want to store (like a number or text).
2. Next Pointer: A reference (or link) to the exact memory address of the next Node in the chain.

The first Node is called the Head. The last Node's pointer points to null (meaning the end of the line).

Real-Life Analogy

Imagine a scavenger hunt. You are given a clue (Data). At the bottom of the clue, it tells you exactly where to find the next clue (Next Pointer). You go to that location, find the next clue, and repeat until you reach the final destination!

A Linked List: Nodes scattered in memory, connected by pointers.

2. Linked Lists vs. Arrays

Why use a Linked List instead of an Array? Let's compare them!

Memory Allocation

• Arrays require a single, unbroken block of memory.
• Linked Lists can be scattered anywhere in the computer's memory. As long as Node A knows where Node B is, they don't need to sit next to each other.

Insertion and Deletion

• Arrays: O(n). Very slow. If you insert an item at the beginning, you must shift every other item down.
• Linked Lists: O(1). Lightning fast! If you want to insert a new Node, you just change two pointers to link it into the chain. No shifting required!

Accessing Data

• Arrays: O(1). Lightning fast. You can instantly open arr[5].
• Linked Lists: O(n). Very slow. To find the 5th item, you must start at the Head and follow the pointers one by one until you reach it.

3. Types of Linked Lists

There are three main variations of Linked Lists you will encounter:

1. Singly Linked List: Nodes only point forward to the next node. You cannot go backwards.
2. Doubly Linked List: Nodes have two pointers: one pointing forward, and one pointing backward to the previous node.
3. Circular Linked List: The last node's pointer doesn't point to null. Instead, it points back to the Head, creating an infinite loop!

4. Linked List Code Example

Here is how you would create a simple Singly Linked List in Python. First, we create a Node class. Then, we link them together!

# 1. Create the Node Class
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None  # Initially, it doesn't point to anything
# 2. Create individual Nodes
head = Node(10)
node2 = Node(20)
node3 = Node(30)
# 3. Link the Nodes together to form a chain!
head.next = node2
node2.next = node3
# 4. Traverse (Loop through) the Linked List
current = head
while current is not None:
    print(current.data)
    current = current.next