JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Linked Lists

An [[dsa-array|array]] keeps everything in one solid block. A **linked list** scatters its items across memory and threads them together with [[linked-list|pointers]]. That one change flips the cost of inserting and deleting — and it's a perfect first look at how a [[data-structure|data structure]] makes trade-offs.

A treasure hunt, not a bookshelf

Picture an array as a row of numbered lockers, all side by side. To find locker #5 you just walk straight to it. A linked list is more like a treasure hunt: each clue tells you only where the *next* clue is. The item itself is called a node, and each node holds a value plus a pointer — the address of the next node.

Because nodes don't have to sit next to each other in memory, the list can grow one node at a time without ever copying everything to a bigger block — something a fixed array can't do.

head -> [1|.] -> [2|.] -> [3|/]    (/ = nullptr)
        |          ^
        value      pointer to next node
A singly linked list of three nodes. Each box is a node: a value and a "next" pointer.

A node in C++

A node is just a tiny struct: one value, and one pointer to the next node of the same type. The whole list is identified by a single `head` pointer to its first node; the last node points at `nullptr` to mark the end.

struct Node {
    int v;            // the value
    Node* next;       // pointer to the next node (or nullptr)
};

// Build  1 -> 2 -> 3  by hand:
Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head->next->next = new Node{3, nullptr};
A self-referential struct: Node holds a Node*. That's what makes the chain possible.

To walk the list, you start at `head` and follow `next` until you hit `nullptr`. This is called traversal, and it touches every node once — so visiting all of them is O(n).

for (Node* cur = head; cur != nullptr; cur = cur->next) {
    std::cout << cur->v << ' ';   // prints: 1 2 3
}
Traversal: hop from node to node by following the next pointer.

Where linked lists win — and where they lose

Here's the trade-off in one breath. Once you already hold a pointer to a spot, inserting or deleting there is O(1): you just re-wire two pointers, no shifting. But finding that spot first means traversing from the head — O(n). Compare an array, where indexing is O(1) but inserting in the middle is O(n) because everything after must shift.

  1. Insert at the front: make a new node, point its next at the old head, then move head to it. O(1).
  2. Delete a node you have a pointer to: point the previous node's next past it. O(1) — then free it.
  3. Access the k-th item by position: there is no shortcut — walk k nodes from the head. O(n).

Singly vs doubly linked

The list above is singly linked: each node knows only its successor, so you can only travel forward. A doubly linked list adds a `prev` pointer to every node, so you can walk backward too — and you can delete a node knowing only that node (you can reach its predecessor). The price is one extra pointer of memory per node.

      .---.     .---.     .---.
null<-|prev|<-->|prev|<-->|prev|->null
      | 1 |     | 2 |     | 3 |
      |next|<-->|next|<-->|next|
      '---'     '---'     '---'
A doubly linked list: each node points both forward (next) and backward (prev).

In real C++ you'd usually reach for `std::list` (doubly linked) or `std::forward_list` (singly linked) instead of hand-rolling nodes — but writing one yourself, once, is how the pointer dance finally clicks. We'll build on this when we hand-roll stacks and queues next.