Programming · concepts · data structures

What is a linked list?

A linked list is a data structure that stores a sequence of values as a chain of nodes. Each node holds two things: a value, and a pointer (a reference) to the next node in the chain. The nodes are not laid out side by side in one block of memory the way an array's items are; instead each one simply points to where the next one lives. Follow the pointers from the first node, the head, and you can walk the whole sequence one link at a time.

How the chain is built

Think of it like a treasure hunt where each clue tells you where to find the next clue. The list keeps a reference to the head node. That node's pointer leads to the second node, whose pointer leads to the third, and so on until a node's pointer is empty (often called null or None), which marks the end of the list.

[ value | next ] -> [ value | next ] -> [ value | null ]

Because the connections are just pointers, the nodes can sit anywhere in memory. To grow the list you allocate a new node and set a pointer to it; nothing else has to move.

Singly vs doubly linked

There are two common shapes, and the difference is how many pointers each node carries:

• Singly linked list: each node points only to the next node. You can move forward through the list but not backward, and you only pay for one pointer per node.
• Doubly linked list: each node points to both the next and the previous node. That lets you walk in either direction and makes some deletions easier, at the cost of an extra pointer per node.

Linked list vs array

The clearest way to understand a linked list is next to an array, because they make opposite trade-offs. An array stores its items in one contiguous block with an index, so it can jump to any position instantly. A linked list gives that up in exchange for cheap changes at the ends.

• Random access. An array reads any element by index in O(1). A linked list has no index: to reach the tenth node you must start at the head and follow nine pointers, so access is O(n).
• Insert and delete. If you already hold a reference to the right node, a linked list can insert or remove there by rewiring a couple of pointers, an O(1) operation - no shifting of other elements. In an array, inserting or deleting in the middle means shifting the elements after it, which is O(n).
• Memory and cache. An array packs its values together, which is friendly to the CPU cache. A linked list scatters its nodes and stores an extra pointer per node, so it uses more memory per item and tends to have poorer cache locality.

Neither is "better"; they suit different jobs. If you need fast lookups by position, an array (or a dynamic array like a list or vector) usually wins. If your data changes size a lot and you mostly add or remove at the ends, a linked list can be a good fit. For a refresher on how these costs are described, see our guide to Big O notation.

The complexities, honestly

Here are the standard costs for a linked list, with the caveat that always matters:

• Access and search: O(n). There is no index, so finding a value means walking the chain from the head.
• Insertion and deletion: O(1) when you already have a reference to the node (for example, right at the head). If you first have to find the spot, that search is O(n), and the total reflects both parts.

That "when you have the node" condition is the part people often drop. Inserting at the head of a singly linked list is genuinely constant time; inserting after some value you still have to locate is not.

Where linked lists are used

Linked lists are a building block more than an everyday container. They are a natural way to implement a stack or a queue, since those only add and remove at the ends. They suit situations where the collection's size changes a great deal and you do not need fast access by position. Some structures use linked nodes internally; for example, one common way to handle collisions in a hash table is to chain colliding entries together in a small linked list per bucket.

The trade-offs

• No random access. Reaching an arbitrary position costs O(n) because you follow pointers from the head; there is no index to jump with.
• Extra memory per item. Every node stores at least one pointer (two for a doubly linked list) on top of its value.
• Weaker cache locality. Scattered nodes are less cache-friendly than a contiguous array, which can make traversal slower in practice even when the Big O is the same.
• Cheap edits at a known node. The upside: inserting or removing at a node you already hold is O(1), with no shifting of the rest of the data.

FAQ

What is the difference between a linked list and an array? An array stores items in one contiguous block with an index, so it reads any position in O(1) but shifting elements to insert or delete in the middle costs O(n). A linked list stores separate nodes joined by pointers, so it has no random access (O(n) to reach a position) but can insert or delete at a known node in O(1).

Why is accessing an element O(n)? Because a linked list has no index. To reach the nth node you start at the head and follow the pointer chain n times, so the cost grows with the position you want.

What is the difference between singly and doubly linked? In a singly linked list each node points only to the next node, so you can move forward only. In a doubly linked list each node also points to the previous node, so you can move in both directions, at the cost of one extra pointer per node.

When should I use a linked list? When the collection changes size a lot and you mostly add or remove at the ends, or as the backbone of a stack or queue. If you need fast access by position, an array is usually the better choice.

Related guides: hash tables, Big O notation, recursion.