Linked Lists Explained: Structure, Operations, and When Arrays Win

Linked lists let you insert and delete elements in O(1) time at a known position, but they pay a real cost in cache performance. Here is what they are, how they work in code, and when you should reach for an array instead.

An array stores its elements in a single contiguous block of memory. Element zero lives at address X, element one at X+stride, and so on. That predictability is exactly what makes arrays fast for random access and sequential reads. A linked list takes the opposite approach: each element, called a node, holds its value and a pointer to the next node. The nodes can live anywhere on the heap. There is no guaranteed contiguity, which changes the performance profile dramatically.

The Node Structure

Every linked list is built from nodes. In a singly linked list each node carries a value and one pointer to the next node. When that pointer is null (or None in Python), you have reached the tail.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None   # points to the next Node, or None

class SinglyLinkedList:
    def __init__(self):
        self.head = None   # the first node

A doubly linked list adds a second pointer, prev, pointing backward to the preceding node. This costs an extra pointer per node in memory but makes bidirectional traversal and O(1) deletion (when you already hold a reference to the node) straightforward without having to track a trailing pointer.

class DNode:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None

Core Operations and Their Complexity

Inserting a new node at the head of a singly linked list is O(1). You create the node, set its next to the current head, and update the head pointer. No elements need to shift, unlike an array prepend that costs O(n).

def insert_head(self, value):
    new_node = Node(value)
    new_node.next = self.head
    self.head = new_node

Deleting a node at a known position is also O(1) in a doubly linked list, because you can wire up prev and next pointers without scanning the list. In a singly linked list you need the preceding node first, which requires O(n) traversal unless you keep a trailing pointer during a previous scan.

Traversal is always O(n). There is no way to jump to index 7 directly. You start at the head and follow next pointers one by one:

def traverse(self):
    current = self.head
    while current is not None:
        print(current.value)
        current = current.next

The Cache Penalty Nobody Mentions

Even though traversal is O(n) for both arrays and linked lists, the constant factor is very different. Modern CPUs depend on cache lines. When you read an array element, the CPU prefetches the surrounding memory into L1/L2 cache, so the next several elements arrive almost free. With a linked list, each current.next dereference chases a pointer to an arbitrary heap address. That address is unlikely to be in cache, so you pay a full cache-miss penalty for nearly every node. On a list of a million nodes you will feel this.

This cache-miss overhead is the main reason linked lists lose in benchmarks against arrays even when their algorithmic complexity looks the same. If you are traversing a list frequently without inserting or deleting, a cache-friendly array or slice will usually beat it in wall-clock time. You can learn more about how complexity alone does not tell the full story in our article on time complexity vs space complexity.

When to Use a Linked List vs an Array

Reach for a linked list when:

• You need frequent insertions or deletions at the head or at a known interior position and you already hold a pointer to that location.
• You are building a queue with O(1) enqueue at the tail and O(1) dequeue at the head without the resizing overhead of a dynamic array.
• The size of the collection is highly variable and you want to avoid the memory copying that comes with array resizing.

Reach for an array when:

• You need random access by index (O(1) for arrays, O(n) for linked lists).
• You are doing sequential reads where CPU prefetching gives arrays a large real-world advantage.
• Memory overhead matters: each node in a linked list stores at least one pointer (8 bytes on 64-bit systems) in addition to the actual value.

If you are comparing linked lists to other foundational structures, our overview of common data structures puts them in context alongside stacks, queues, and hash tables.

Circular Linked Lists

A circular linked list is a variant where the tail node does not point to null; it points back to the head. This creates a ring. Circular lists are used in operating systems for round-robin scheduling (every process gets a turn in rotation), in music-player repeat queues, and in any situation where you want to cycle indefinitely through a sequence. Detection of a cycle in a linked list using Floyd's two-pointer algorithm is a common interview problem that follows directly from this idea.

Understanding big-O complexity for these operations, including why O(1) insertion with pointer overhead can still lose to O(n) array copies in practice, is covered in our big-O notation guide.