Data Structures #3: The Linked List - A Scavenger Hunt in Memory

In our previous posts, we explored the Array (a rigid, sequential train) and the Hash Table (a magical index). Today, we dive into a data structure that breaks the rules of contiguous memory: the Linked List.

If an array is like a train where every carriage is physically bolted to the next in a straight line, a Linked List is like a Scavenger Hunt. Imagine you are in a large building looking for clues. You find the first clue in Room 101. It doesn't just give you a message; it gives you the room number for the next clue (Room 305). When you get to 305, you find the location of the next one (Room 210). The clues are scattered all over the building, but the sequence remains perfectly intact because each one "points" to the next.

The Memory Problem: Why Linked Lists Exist

To truly appreciate a linked list, we need to understand how memory works. Imagine your computer's memory as a giant grid of slots.

Say we want to declare an array of size 4 (requiring 4 consecutive slots). However, what if our memory is fragmented? We might have 10 empty slots total, but they are scattered among other running programs, meaning there are no 4 contiguous memory slots available.

We cannot allocate our array. An array internally requires contiguous memory locations because it relies on simple math: if you know the address of the first element, you instantly know the address of the second element right next to it.

Notice, however, that we still have more than enough raw space available. If we can somehow store the address of the next element within our current element, we can utilize this fragmented space. This is the core idea behind a linked list.

Under the Hood: Nodes and the Heap

The array we discussed above is static; we must know the required space upfront. In the real world, we often deal with dynamic data where we don't know the required space in advance. Linked lists solve this by allocating memory at runtime (dynamically), usually pulling from a pool of memory called the Heap.

Each space allocated in memory for a linked list is known as a Node. The fundamental structure of a node contains two things:

• Data: The actual value you want to store (an integer, a string, or an object).
• Next (The Pointer): The literal memory address of the next node in the sequence.

[Data | Pointer] -> [Data | Pointer] -> [Data | Null]

This gives linked lists a unique advantage: they can grow and shrink dynamically. You simply find a single free spot anywhere in memory for a new node and update the "Next" pointer of the previous node to connect the chain.

Performance: Access, Search, Insertion, and Deletion

Because linked lists break the rules of contiguous memory, their performance characteristics are the exact opposite of those of an array.

• Access (O(n)): In an array, we jump to any index instantly. In a linked list, there is no formula. If you want the 500th element, you must start at the "Head" (the first node) and follow the pointers one by one until you reach your destination.

• Search (O(n)): Just like access, to find a specific value, you have to iterate through the nodes one by one until you find a match or hit the end of the list (Null).

• Insertion (O(1) or O(n)): If you want to insert a node at the very beginning (the Head), it takes O(1) time. You just create the node and point it to the current Head.

  • If you want to insert a node in the middle, the actual pointer swap takes O(1) time (no shifting required). However, finding that specific spot takes O(n) time.

• Deletion (O(1) or O(n)): Deleting the Head is O(1).

  • Deleting a node in the middle takes O(1) to perform the bypass (you tell the previous node to "skip" the deleted node and point to the one after it), but again, finding it takes O(n).

Language Implementations: Pointers vs. References

C++: The Manual Approach

C++ allows you to see the "metal" by using actual pointers and manual memory management.

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

int main() {
    // Dynamically allocating nodes on the heap using 'new'
    Node* head = new Node(10);
    head->next = new Node(20);
    
    std::cout << "First: " << head->data << ", Second: " << head->next->data << std::endl;
    
    // Clean up memory
    delete head->next;
    delete head;
    return 0;
}

Internals: You are responsible for delete-ing nodes to prevent memory leaks. The next variable stores a literal 64-bit memory address.

Java: The LinkedList Class

Java provides a built-in LinkedList, which is actually a Doubly Linked List (each node points to the next and the previous).

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("First");
        list.add("Second");
        
        System.out.println(list.get(0)); // O(n) under the hood!
    }
}

Internals: Java uses object references. The Garbage Collector handles the deallocation of nodes once they are no longer reachable.

Python & JavaScript: Custom Implementations

Neither Python nor JavaScript has a dedicated primitive "Linked List" type because their standard arrays are heavily abstracted and flexible. Engineers often build them manually for specific algorithmic needs.

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

# Usage
head = Node(1)
head.next = Node(2)

Famous Algorithms & Tricks

1. Reversing a Linked List: A classic interview favorite. It involves iterating through the list and flipping the pointers backward. You must maintain three pointers (previous, current, next) to avoid losing the rest of the chain as you break and reverse the links.

2. Cycle Detection (Floyd’s Tortoise and Hare): How do you know if a list accidentally points back to a previous node, creating an infinite loop? You send two pointers down the list:

   • A Slow pointer (Tortoise) that moves one node at a time.
   • A Fast pointer (Hare) that moves two nodes at a time. If there is no cycle, the fast pointer will eventually hit Null. If there is a cycle, the fast pointer will lap the slow pointer, and eventually, the two pointers will point to the exact same node.

3. The Sentinel Node: A "dummy" node placed at the beginning of the list to simplify edge cases, such as deleting the actual head of the list without needing separate logic for it.

Conclusion: Flexibility Over Raw Speed

Linked lists are the "Lego bricks" of data structures. They are used to build Stacks, Queues, and even complex Graphs.

In the real world, you see linked lists in:

• Image Viewers: "Next" and "Previous" buttons navigate a doubly linked list of files.
• Music Playlists: Songs linked in a specific sequence
• Undo/Redo Functionality: Every action is a node in a chain, allowing you to move backwards and forward through history dynamically without shifting a massive array.

While the Array is built for raw access speed and cache efficiency, the Linked List is built for fluidity and optimised memory utilisation. Knowing when to choose one over the other is what separates a coder from an engineer.