Linked Lists

Introduction to Linked Lists

Imagine you are on a scavenger hunt. You are given a starting location. When you get there, you find a prize and a note telling you exactly where to go next. You keep following these notes until you reach the final destination where there is no note left. This is exactly how a Linked List works!

In Computing, a Linked List is a linear data structure where elements are not stored in adjacent memory locations. Instead, each element "points" to the next one. This makes it very flexible compared to a standard array.

1. What Makes Up a Linked List?

A linked list is made of several building blocks called Nodes. Each node contains two essential parts:

1. Data: The actual value you want to store (e.g., a student's name, a number).
2. Pointer (or Next): A variable that stores the memory address (the "link") of the next node in the list.

There are two special markers you need to know:
• Head: A pointer that stores the address of the very first node. If the Head is empty (null), the list is empty.
• Null Pointer: The last node in the list points to Null (or None in Python). This tells the computer, "Stop here, the list has ended!"

2. Memory Allocation: Static vs. Dynamic

How does a computer set aside space for these nodes? There are two ways (important for the 2026 syllabus edition):

Static Allocation

The computer sets aside a fixed-size block of memory (usually an array) before the program runs. The "pointers" here are just the index numbers of the array.
Key Term: Free Space List. In static allocation, we need a way to track which slots in our array are empty. We often use another linked list, called a Free Space List, to link all the empty nodes together. When we need to add data, we "borrow" a node from the Free Space List.

Dynamic Allocation

The computer allocates memory "on the fly" while the program is running. When you want a new node, the computer finds a random empty spot in the memory and gives it to you. This is more flexible as the list can grow as long as the computer has available RAM.

3. Core Operations: Search, Insert, and Delete

Don't worry if these steps seem a bit mechanical; once you visualize the "links" moving, it becomes much easier!

Searching for a Value

To find an item, you must start at the Head and follow the pointers node by node. This is called traversing the list.
• Start at the Head.
• Check if the current node's data matches your search term.
• If not, move to the address stored in the Pointer.
• Repeat until you find the item or hit a Null pointer.

Note: Because you have to start from the beginning every time, searching takes \(O(n)\) time complexity.

Inserting a New Node

To insert a node (let's call it NewNode) between Node A and Node B:
1. Find the position where you want to insert.
2. Set the pointer of NewNode to point to Node B.
3. Change the pointer of Node A to point to NewNode.

Common Mistake: Always update the NewNode pointer first! If you change Node A's pointer first, you "break the chain" and lose the address of Node B forever!

Deleting a Node

To delete Node B (which is between Node A and Node C):
1. Find Node A (the node before the one you want to delete).
2. Change Node A's pointer to point directly to Node C.
3. The computer now "skips" Node B. In dynamic memory, Node B is then wiped clean to save space.

4. Linked Lists vs. Arrays

Why use a Linked List instead of a standard Python list (which acts like an array)?

• Insertion/Deletion: In an array, if you delete the first item, every other item has to "shift" one spot left. In a Linked List, you just change one pointer. It’s much faster!
• Size: Linked Lists (dynamic) can grow and shrink easily. Arrays usually have a fixed size or require expensive resizing operations.

Quick Review Table:
• Accessing an item: Arrays are faster (you can jump to any index). Linked lists are slower (must start from the Head).
• Adding/Removing: Linked lists are generally more efficient for middle-of-the-list changes.

Key Takeaways

• A Linear Linked List is a sequence of nodes connected by pointers.
• Each node contains Data and a Pointer to the next node.
• The Head points to the start; Null marks the end.
• Static allocation uses a Free Space List to manage empty slots in a fixed array.
• Searching always starts from the Head and moves linearly, giving it a worst-case time complexity of \(O(n)\).

Next Step: You might want to look at Stacks and Queues, which can actually be built using Linked Lists!