Linked Lists

Arrays feel natural because they map onto how we think about lists — item 1, item 2, item 3, sitting right next to each other in memory. A linked list throws that assumption out. Instead of sitting next to each other, elements are scattered in memory and simply point to the next one. That one design choice changes almost everything about how the structure performs.

What a Linked List Actually Is

A linked list is a chain of nodes. Each node holds two things:

• The actual data
• A pointer/reference to the next node in the chain The list itself just keeps track of the head (the first node). To get to any other node, you walk the chain one pointer at a time — there's no way to jump straight to "node number 7" the way you can with array[7].

Arrays vs. Linked Lists: The Real Trade-off

The pattern is consistent: arrays win at reading, linked lists win at inserting and deleting — especially at the front, or when you already have a reference to the node you're modifying.

The Three Common Variants

• Singly Linked List — each node points only to the next node. Simple and memory-light, but you can only traverse forward.
• Doubly Linked List — each node points to both the next and previous node. Uses more memory per node, but lets you traverse in either direction and delete a node in O(1) once you have a reference to it, without needing to walk from the head to find its predecessor.
• Circular Linked List — the last node points back to the first instead of pointing to nothing, forming a loop. Useful for anything that cycles continuously, like round-robin task scheduling.

A Simple Singly Linked List (Python)

python
Copy
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    def push_front(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
 
    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
 
    def to_list(self):
        result = []
        current = self.head
        while current:
            result.append(current.data)
            current = current.next
        return result
 
 
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.push_front(0)
print(ll.to_list())  # [0, 1, 2]

Why Bother, When Arrays Already Exist?

The honest answer: for most everyday tasks, you probably won't reach for a linked list directly — languages give you dynamic arrays (like Python lists) that already handle resizing well. Linked lists earn their keep in more specific situations:

• Frequent insertions/deletions, especially at the front or middle, where shifting array elements would be expensive.
• Unknown or highly variable size, where you don't want to pay for pre-allocated array capacity.
• Building other structures. Stacks, queues, and hash table collision-chains are all commonly implemented using linked lists under the hood.
• No need for random access. If you only ever process items in sequence, you lose nothing by giving up O(1) indexing.

Where They Show Up in Practice

• Browser history and undo chains, where doubly linked lists let you move both forward and backward.
• Music/video playlists, where "next" and "previous" are core operations.
• Memory management systems, which often track free memory blocks as a linked list.
• Implementing a hash table's collision handling, via chaining (each bucket is itself a small linked list).

The Takeaway

A linked list trades away instant access to any element in exchange for cheap insertion and deletion anywhere in the chain. It's not a replacement for arrays — it's a different set of trade-offs, and recognizing which one your problem actually needs is most of the skill.