Introduction to Linked Lists

Welcome to the world of Abstract Data Types (ADTs)! In this chapter, we are diving into one of the most fundamental structures in computer science: the Linked List. While you might be comfortable using arrays to store data, linked lists offer a more flexible, "go-with-the-flow" approach. Think of a linked list like a digital scavenger hunt—each item doesn't just hold its own information, but also a map leading to the next item in the chain.

Because this topic is part of B.4 Abstract data types (HL only), we will focus on how these lists are structured, how we manipulate them, and why they are often preferred over static structures like arrays.

What is a Linked List?

A Linked List is a linear data structure where elements are not stored in adjacent memory locations. Instead, each element is a separate object called a Node.

The Anatomy of a Node

Every node in a linked list consists of two essential parts:

  • Data: The actual information you want to store (an integer, a string, an object, etc.).
  • Pointer (or Reference): A link that points to the memory address of the next node in the sequence.

Did you know? The very first node in the list is called the Head. If the head is empty, the entire list is empty. The very last node points to \(Null\) (or \(None\) in Python), which tells the computer, "Stop here! There are no more items."

Linked Lists vs. Arrays

To understand why we use linked lists, it helps to compare them to arrays:

1. Memory Allocation: Arrays are static (usually fixed in size), meaning you have to decide how big they are before you use them. Linked lists are dynamic; they can grow and shrink while the program is running.

2. Insertion and Deletion: If you want to put a new item at the beginning of an array, you have to "shove" every other item one space to the right. In a linked list, you just change where the pointers are "pointing." It’s much faster!

3. Access Speed: In an array, you can jump straight to the 100th item. In a linked list, you have to start at the Head and follow the pointers one by one until you reach the 100th node. This is called linear search.

Key Takeaway: Use arrays when you need fast access to items; use linked lists when you need to add or remove items frequently without knowing the final size of the list.

Common Types of Linked Lists

While the standard (singly) linked list is most common, there are variations you should recognize:

  • Singly Linked List: Each node points only to the next node. You can only move forward.
  • Doubly Linked List: Each node has two pointers—one pointing forward and one pointing backward. This allows you to traverse the list in both directions.
  • Circular Linked List: The last node doesn't point to \(Null\); instead, it points back to the Head, creating a loop.

Basic Operations

Don't worry if the logic seems tricky at first! Let’s break down how we actually move things around in a linked list.

1. Traversal (Searching)

To find an item or print the list, we start at the \(Head\) and use a temporary "pointer" variable to move through the list:
Current = Head
While Current is not Null:
    Check Data in Current Node
    Move Current to Current.Next

2. Insertion at the Beginning

This is very efficient (\(O(1)\) time complexity).
1. Create a new node.
2. Point the new node's "Next" to the current \(Head\).
3. Update the \(Head\) to be the new node.

3. Deletion

To delete a node, you essentially "bypass" it. If you want to delete Node B (which is between Node A and Node C), you simply tell Node A to point directly to Node C. Node B is then left floating and is eventually cleaned up by the computer's memory management.

Logical Representation (Thinking like a Programmer)

In your Paper 2 exam, you might be asked to describe the steps to insert or delete items in either Java or Python. Even though the syntax differs, the logic is identical.

Common Mistake: Forgetting to handle the "Empty List" case. Always check if \(Head\) is \(Null\) before trying to do something with the list, or your program might crash!

Summary and Quick Review

  • A Linked List is a collection of nodes stored non-contiguously in memory.
  • A Node = Data + Pointer.
  • The Head is the starting point; \(Null\) marks the end.
  • Pros: Dynamic size, easy insertion/deletion.
  • Cons: No random access (must traverse linearly), uses extra memory for pointers.

Note: Linked lists are often used as the underlying structure for other ADTs like Stacks and Queues. To learn more about those, check out the next chapter!