What Is a Linked List? Data Structure Explained

A linked list is a linear data structure where each element, called a node, stores its value plus a pointer to the next node in the sequence. Unlike an array, the nodes don’t need to sit in contiguous memory — they can be scattered anywhere, connected only by these pointers. That single structural difference is the source of everything a linked list is good and bad at.

Nodes and pointers

The simplest form, a singly linked list, defines each node as a value and a reference to the next node:

struct Node {
  value: T
  next: Node | null
}

A list is just a reference to its first node, called the head. Walking the list means following next pointers one at a time until you hit null:

head -> [3] -> [7] -> [1] -> null

A doubly linked list adds a prev pointer to each node as well, letting you traverse backward as easily as forward — at the cost of one extra pointer per node to store and keep consistent.

Why linked lists trade away random access

Because nodes aren’t stored contiguously, there’s no way to compute the memory address of the nth element directly the way you can with an array (base_address + n * element_size). Reaching the nth node requires walking the list from the head, one next pointer at a time — an O(n) operation. Contrast that with an array’s O(1) random access by index, and it’s clear why linked lists aren’t the default choice for data you need to look up by position.

Where linked lists win: insertion and removal

The payoff shows up on the other side of the ledger. Inserting or removing a node in the middle of a linked list, given a reference to the node next to the insertion point, is O(1) — you just rewire a couple of pointers. An array, by contrast, has to shift every element after the insertion point to keep things contiguous, making that an O(n) operation.

Operation	Array	Linked list
Access by index	O(1)	O(n)
Insert/remove at known position	O(n) (shifts elements)	O(1) (rewires pointers)
Insert/remove at the head	O(n)	O(1)
Memory layout	Contiguous	Scattered, extra pointer overhead per node
Cache locality	Good	Poor

That last row matters more in practice than the O(n) vs O(1) numbers suggest. Modern CPUs are heavily optimized for sequential memory access — reading an array walks through cache-friendly contiguous memory, while chasing pointers across a linked list tends to jump around in memory, causing more cache misses. For this reason, arrays (or array-backed structures like dynamic arrays) often outperform linked lists in practice even for operations where the linked list has the better theoretical complexity, unless the list is large or insertions/removals dominate.

Common variants

• Singly linked list — forward traversal only, minimal memory overhead per node.
• Doubly linked list — bidirectional traversal, used when you need to walk backward or remove a node in O(1) given only a reference to it (rather than to its predecessor).
• Circular linked list — the last node points back to the head instead of to null, useful for round-robin scheduling or any cyclic buffer-like use case.

Where linked lists show up in practice

Despite arrays being more common as a general-purpose default, linked lists underpin several structures you likely use indirectly:

• Queues and deques used in task schedulers and message-passing systems are often implemented with a doubly linked list, since it gives O(1) push and pop at both ends.
• LRU cache implementations frequently combine a doubly linked list with a hash table — the hash table gives O(1) lookup, and the linked list gives O(1) reordering to track recency without shifting anything.
• Language runtime internals, like some implementations of linked hash maps that need to preserve insertion order.

If you’re studying data structures more broadly, it’s worth pairing linked lists with hash tables and binary search trees — together they cover most of the tradeoffs between lookup speed, ordering, and insertion cost that show up in real systems. And understanding why an operation is O(1) or O(n) leans directly on Big O notation, which is the vocabulary this entire comparison is written in.

Choosing between an array and a linked list

In practice, default to an array (or your language’s dynamic array type) unless you have a specific reason not to. Reach for a linked list when insertions and removals dominate over random access, when you need guaranteed O(1) operations at both ends, or when you’re implementing a structure — like an LRU cache or a queue — that’s naturally built on one. Most general-purpose “I just need a list of things” use cases are better served by an array’s simplicity and cache-friendly performance.

The takeaway

A linked list stores elements as nodes connected by pointers rather than packed into contiguous memory, which flips the array’s performance profile: slow random access, but cheap insertion and removal once you have a reference to the right spot. That tradeoff — plus poorer cache locality in practice — is why arrays remain the default general-purpose choice, while linked lists earn their place in structures purpose-built around frequent insertion and removal, like queues and LRU caches.