Linked List

A linked list is a linear data structure made of nodes. Each node stores a value and a pointer or reference to the next node (and, in a doubly linked list, to the previous one). Unlike an array, nodes need not sit next to each other in memory.

Why it matters

Inserting or removing a node is O(1) once you hold a reference to its position, because only a couple of links change and nothing has to be shifted. The cost is access: reaching the nth element means walking from the head, which is O(n), and there is no fast indexing. Scattered nodes also use the CPU cache poorly, so in practice arrays or dynamic arrays are often faster even for workloads where linked lists look better on paper. Linked lists remain useful for queues, undo history and as building blocks for other structures.

Example

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

head = Node(1, Node(2, Node(3)))
node = head
while node:
    print(node.value)   # 1, 2, 3
    node = node.next

Common mistakes

• Losing the head reference and leaking the rest of the list.
• Forgetting to handle the empty list and single-node cases.
• Choosing a linked list for random access.

Related

• Array
• Pointer
• Queue
• Data structure

This page is general information written by our editorial team and updated when documentation changes. Servers and providers differ, so test changes safely first. See our editorial policy and disclaimer.