Linked List

A data structure that stores elements as nodes connected by pointers.

#How does it work?

A linked list stores elements not side by side in memory but as nodes connected by pointers. Each node holds a value and the address of the next node (next).

head points to the first node, and the last node's next pointer is null. To reach an element you start at head and follow next pointers one by one.

The big difference from an array: inserting or removing in the middle doesn't shift other elements, only a few pointers change. In exchange, you can't jump straight to the i-th element.

#Try it yourself

$ linked_list --interactive

Type a value and insert it at the head, the tail or an index; watch removal and search visit the nodes one by one.

Elements: 4/8VisitingNewRemovingFound / read

#Basic operations

insertHead(x)
Adds a node at the front: the new node points to the old head, and head becomes the new node.
insertTail(x)
Walks to the last node and links the new node after it. With a tail pointer it is O(1).
insertAt(i, x)
Walks to node i - 1 and links the new node in between.
remove(x)
Finds the node with value x and unlinks it by pointing the previous node's next to the following node.
search(x)
Starts at head and checks the nodes one by one.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class Node:
    value: int
    next: Node | None = None


class LinkedList:
    def __init__(self) -> None:
        self.head: Node | None = None

    def push_front(self, value: int) -> None:
        # O(1): the new node simply points at the old head.
        self.head = Node(value, self.head)

    def push_back(self, value: int) -> None:
        # O(n): walk to the last node (a tail pointer would make this O(1)).
        node = Node(value)
        if self.head is None:
            self.head = node
            return
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = node

    def index_of(self, value: int) -> int:
        cur, i = self.head, 0
        while cur is not None:
            if cur.value == value:
                return i
            cur, i = cur.next, i + 1
        return -1

    def remove(self, value: int) -> None:
        # Unlinks the first node with this value: the previous node skips over it.
        if self.head is None:
            return
        if self.head.value == value:
            self.head = self.head.next
            return
        prev = self.head
        while prev.next is not None and prev.next.value != value:
            prev = prev.next
        if prev.next is not None:
            prev.next = prev.next.next

    def __str__(self) -> str:
        values, cur = [], self.head
        while cur is not None:
            values.append(str(cur.value))
            cur = cur.next
        return " ".join(values)


items = LinkedList()
items.push_front(2)
items.push_front(1)
items.push_back(3)
print(items)               # 1 2 3
print(items.index_of(2))   # 1
items.remove(2)
print(items)               # 1 3

#Complexity

OperationTime
Insert / remove at headO(1)
Insert at tail (with tail pointer)O(1)
Insert at tail (without tail)O(n)
Access the i-th elementO(n)
SearchO(n)
Insert/remove after a known nodeO(1)

A linked list shines at insertion and removal: once you reach the right node, only pointers change. Its weakness is access: a[i] is O(1) in an array but needs i hops in a linked list. Nodes are also scattered in memory, so cache use is worse than with arrays.

#When to use it?

Use it when you often insert or remove at the front or middle and don't need random access: LRU caches (doubly linked list + hash table), free-memory lists in operating systems, and stack and queue implementations. For most everyday work, dynamic arrays (ArrayList, Python list) are faster.

#Practice

Log in to answer questions and save your progress.

Easy

1/3

What does each node of a singly linked list hold?

  • 1A value and the next node's address
  • 2Only a value
  • 3A value and its index
  • 4The length of the list

Medium

1/1

In head → 4 → 7 → 2 → null, which pointer changes when 7 is removed?

  • 14's next points to 2
  • 2head points to 7
  • 32's next points to 4
  • 4None, elements are shifted

Hard

1/1

When is a linked list a better choice than an array?

  • 1When you often insert/remove at the front or middle and don't need random access
  • 2When elements are often accessed by index
  • 3When you need binary search
  • 4When cache efficiency matters

#Up next

Lessons that build on this one: