Skip to content
Tutorials Center
My learning

Topics

Lesson 159 of 171 ยท Data Structures and Algorithms

Data Structures in C++

Build classic data structures in modern C++ - a growable array, a stack, a ring-buffer queue, a linked list with unique_ptr nodes and a binary search tree.

A data structure is a way of arranging data in memory so that the operations you care about are fast. A growable array makes "give me element 500" instant. A stack makes "undo the last thing" trivial. A queue serves requests in arrival order. A linked list splices elements in and out without moving the others, and a binary search tree keeps everything sorted while you insert.

The standard library already ships production-quality versions of all of these, and in real code you should use them. But building each one yourself, once, is how you learn what the library is doing for you: why push_back is "amortized O(1)", why a std::list iterator survives an insertion while a std::vector iterator does not, why a tree built from sorted input becomes slow. It's also exactly what technical interviews ask for. In this lesson you'll write five class templates with modern C++: a dynamic array, a stack, a circular queue, a singly linked list whose nodes are owned by std::unique_ptr, and a binary search tree. Each section ends with the STL type you'd use in practice.

You should be comfortable with class templates, std::unique_ptr and move semantics. For the complexity notation used below, see The Standard Template Library.

Big-O in one minute

Every data structure is a trade-off, and Big-O notation is how we describe it. O(1) means "the same cost no matter how many elements", O(log n) means "one more step each time the size doubles", and O(n) means "cost grows in proportion to the size". Here is what you'll build, and what each operation costs:

Structure Access by position Search Insert / remove at front Insert / remove at back Insert in the middle
Dynamic array O(1) O(n) O(n) O(1) amortized O(n)
Stack top only, O(1) โ€” โ€” O(1) โ€”
Ring-buffer queue front/back, O(1) โ€” remove O(1) insert O(1) โ€”
Singly linked list O(n) O(n) O(1) insert O(1) with a tail pointer, remove O(n) O(1) once you have the node
Binary search tree โ€” O(log n) average, O(n) worst โ€” โ€” O(log n) average

Big-O ignores constant factors, and on modern hardware the constant factors are often decisive: walking a linked list jumps around memory, while walking an array streams through it. Keep that in mind when you read the "use the STL instead" notes.

A dynamic array

A dynamic array stores its elements in one contiguous block of heap memory and remembers two numbers: the size (how many elements are in use) and the capacity (how many fit in the block). When you append and the block is full, it allocates a bigger block, moves the elements across and frees the old one.

The growth factor is the important design decision. If you grew by one slot each time, appending n elements would copy 1 + 2 + 3 + โ€ฆ + n elements, which is O(nยฒ). If you double the capacity, the copies add up to less than 2n in total, so each append costs O(1) on average. That's what "amortized O(1)" means: a few appends are expensive, but they're rare enough that the average stays constant.

C++ A growable array that doubles its capacity

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Ten appends caused five allocations and only 15 element moves (0 + 1 + 2 + 4 + 8). Double the number of elements and you add just one more allocation. Notice the design choices:

  • std::unique_ptr<T[]> owns the block, so the class follows the rule of zero: no destructor to write, no leaks, and moving a DynamicArray just moves the pointer. Because unique_ptr can't be copied, DynamicArray is move-only. A full version would add a copy constructor that allocates a new block and copies the elements.
  • push_back takes its parameter by value and moves it in. Callers who pass a temporary pay one move; callers who pass an lvalue pay one copy, which they would have paid anyway.
  • operator[] is unchecked and at() is checked, mirroring the standard containers.

This simplified version has one real limitation: std::make_unique<T[]>(n) default-constructs all n slots up front, so T must be default-constructible, and pop_back leaves the old object alive in its slot until it's overwritten. std::vector avoids both by allocating raw, uninitialized memory and constructing each element in place only when it's added (with std::construct_at), then destroying it the moment it's removed. That's also why vector::reserve can make room without creating any objects. Writing that correctly, including exception safety when a constructor throws halfway through a growth, is the hard part of a real vector. It's covered in std::vector in Depth.

In practice: use std::vector. It's the default container in C++ for good reason: contiguous, cache-friendly and heavily optimized. If you know the final size, call reserve(n) first and no reallocation happens at all.

A stack

A stack is last in, first out (LIFO): you can only add to, look at or remove the top. That tiny interface is exactly what you need for undo history, matching brackets, evaluating expressions and walking a tree without recursion.

You don't need new memory management to build one: a stack is a thin wrapper around a dynamic array, using its back as the top. That's precisely what std::stack does, too.

C++
template <typename T>
class Stack {
public:
    void push(T value) { items_.push_back(std::move(value)); }
    void pop() { items_.pop_back(); }               // precondition: !empty()
    T& top() { return items_.back(); }              // precondition: !empty()
    bool empty() const { return items_.empty(); }
    std::size_t size() const { return items_.size(); }

private:
    std::vector<T> items_;
};

Why does pop() return void instead of the removed value? If it returned T by value and copying that value threw an exception, the element would already be gone from the stack and lost forever. Splitting "look" (top) from "remove" (pop) avoids that. In modern code, where moves rarely throw, a try_pop() that returns std::optional<T> is a convenient extra, and it also makes the empty case impossible to ignore.

A classic use is checking whether brackets are balanced. Read the text left to right; push every opening bracket; on a closing bracket, the top of the stack must be its partner.

C++ Balanced brackets with a hand-made stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Each character is pushed and popped at most once, so the whole check is O(n) for a line of n characters. Try your own lines in the Input box.

In practice: use std::stack<T> (from <stack>), or simply a std::vector<T> with push_back, back and pop_back. See Container Adapters.

A queue as a ring buffer

A queue is first in, first out (FIFO): add at the back, remove from the front. Building it on a plain array has a problem: removing from the front of an array means shifting every remaining element left, which is O(n).

The fix is a ring buffer (circular buffer). Keep a fixed array, an index head_ of the front element and a count_ of elements. The back is at (head_ + count_) % capacity. Removing just moves head_ forward; adding writes at the back position. When an index runs off the end, % wraps it to 0, so the array behaves as if its ends were glued together. Both operations are O(1) and nothing ever moves.

TEXT
capacity 5, after push A B C D, pop, pop, push E F:
index:   0   1   2   3   4
        [F] [ ] [C] [D] [E]          head_ = 2, count_ = 4
                 ^ front     the back wrapped around to index 0

Fixed-capacity ring buffers are everywhere in systems code: audio buffers, network packet queues, logging, and producerโ€“consumer pipelines, because they never allocate after construction.

C++ A fixed-capacity circular queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The used test in show() computes how far slot i is from the head, going forward around the ring: slots less than count_ steps away are occupied. Notice how E and F keep the arrival order even though F physically sits at index 0, before C.

A ring buffer must decide what to do when it's full: reject the new element (as here), overwrite the oldest (common for logs and sensor data), or grow. A growable version allocates a bigger array and copies the elements in queue order, starting from head_, so the front lands at index 0 again.

In practice: use std::queue<T> (built on std::deque by default) for an unbounded FIFO queue, or std::deque directly when you need both ends. Write your own ring buffer when you need a fixed memory budget and zero allocations.

A singly linked list with unique_ptr

A linked list stores each element in its own node, and each node points to the next one. Nodes can live anywhere in memory, so inserting or removing a node only rewires a pointer or two: no other element moves, and iterators to other nodes stay valid. The price is that there's no way to jump to the 500th element; you must follow 500 pointers.

Ownership is the interesting part in modern C++. Each node owns the next node, which makes std::unique_ptr<Node> the natural type for next, and the list owns the first node through head_. Destroying the head would destroy the whole chain automatically. A raw Node* is still the right type for tail_, because it only observes a node that's already owned by its predecessor.

C++ Linked list: push, remove, reverse and iterate

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

A few techniques here are worth studying:

  • push_front in one line. std::make_unique<Node>(std::move(value), std::move(head_)) builds the new node with the old head as its next, and the result becomes the new head. (Creating an aggregate like Node with parentheses works since C++20.)
  • The pointer-to-link trick in remove_first. Instead of special-casing "the node to remove is the head", link points at whichever unique_ptr currently points to the node: head_ at first, then some node's next. Unlinking is then the same single assignment in every case. When *link = std::move((*link)->next) runs, the unique_ptr releases the next node first and then deletes the old one, so nothing dangles.
  • In-place reversal walks the list once and turns every next pointer around, using three pointers: previous, the current head_ and next. It's O(n) time and O(1) extra memory, and a favorite interview question.
  • The destructor is a loop. Without it, destroying head_ would destroy its next, which destroys its next, and so on: one nested destructor call per node. A million nested calls can overflow the call stack and crash the program. The loop frees one node per iteration instead. Any structure made of chained unique_ptrs needs this.
  • The iterator needs only *, prefix ++ and == for a range-based for loop to work.

tail_ makes push_back O(1), but removing the last node is still O(n), because you need the node before it and there's no backward pointer. A doubly linked list adds a prev pointer to each node to fix that, at the cost of more memory per node. With prev pointers, ownership gets trickier: two nodes point at each other, so only one direction can be the owning unique_ptr; the other must be a raw observer pointer.

Linked lists are slower than they look. Every node is a separate heap allocation, and walking the list jumps to a new memory location at each step, which defeats the CPU cache. For most workloads, even with insertions in the middle, a std::vector beats a list until the elements are large or the list is long. Measure before choosing a list for speed. See Writing Fast C++.

In practice: use std::forward_list (singly linked) or std::list (doubly linked, with O(1) splice). See std::deque, std::list and std::forward_list.

A binary search tree

A binary search tree (BST) is a tree in which every node has at most two children and obeys one rule: everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. That rule lets you find a value the way you'd guess a number between 1 and 100: compare with the root, then go left or right, discarding a whole subtree at every step.

Inserting the keys 50, 30, 70, 20, 40, 60, 80 in that order builds this tree:

TEXT
            50
          /    \
        30      70
       /  \    /  \
     20   40  60   80

To insert, you walk down exactly as if searching and attach the new node where you fall off the tree. An in-order traversal (left subtree, node, right subtree) visits the values in sorted order, which is how std::set iterates.

Erasing has three cases:

  1. The node is a leaf: just remove it.
  2. The node has one child: replace the node with that child.
  3. The node has two children: find its in-order successor (the smallest value in its right subtree, reached by going right once and then left as far as possible), copy that value into the node, and remove the successor, which has at most one child.

The cost of every operation is the tree's height. For a tree built from random keys, the height stays close to logโ‚‚ n, so operations are O(log n). But a plain BST does nothing to keep itself balanced.

C++ Binary search tree with insert, erase and traversal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The sideways printout puts the root on the left and the right subtree above it; tilt your head to the left to see the tree. After erase(30), node 30 had two children, so its successor 35 (the leftmost node of its right subtree) took its place.

The last two lines show the BST's weakness. Inserting already-sorted keys sends every new key to the right of the previous one, and the "tree" becomes a linked list 1,000 nodes tall: every search is O(n). The same keys in random order give a height of 22: about twice the ideal logโ‚‚ 1000 โ‰ˆ 10, and 45 times better than the sorted case. Real libraries solve this with self-balancing trees, such as red-black trees (used by std::map and std::set) or AVL trees, which perform small rotations after insertions and erasures to keep the height O(log n) in every case.

Two more design notes:

  • Iterative where it matters. insert, contains and erase loop down the tree with the same pointer-to-link trick as the linked list. The recursive helpers (height, in_order) are fine for balanced trees, but on the degenerate 1,000-node tree they recurse 1,000 levels deep. That's still safe, but a million sorted keys would risk a stack overflow, and so would the default recursive destruction of the unique_ptr children. Production trees keep themselves balanced, which is the real fix.
  • The concept std::totally_ordered T documents and enforces that keys can be compared with < and ==. BinarySearchTree<std::vector<int>> works (vectors compare lexicographically); a type without comparisons fails with a short, readable error. See Concepts and Constraints.

In practice: use std::set or std::map for an ordered collection with guaranteed O(log n) operations, or a sorted std::vector with std::ranges::lower_bound when the data rarely changes. See std::set and std::map.

When to use the STL instead

Almost always. Your own implementations are valuable for learning, for interviews and for the rare case with special requirements, such as a fixed memory budget, an intrusive list, or a lock-free queue. For everything else, the standard containers are tested, exception-safe, allocator-aware and fast.

You need Use
A sequence you append to and index std::vector
A fixed-size sequence std::array
LIFO std::stack or a std::vector
FIFO, or fast insertion at both ends std::queue, std::deque
The largest (or smallest) element first std::priority_queue
Splicing nodes, stable iterators std::list, std::forward_list
Sorted unique keys, range queries std::set, std::map
Fast lookup by key, no ordering std::unordered_set, std::unordered_map

The next program uses the standard versions of everything you built, so you can compare the interfaces:

C++ The standard library versions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A dynamic array doubles its capacity when full, starting from 1. How many reallocations happen while you push 17 elements?

    Capacity goes 0 -> 1 -> 2 -> 4 -> 8 -> 16 -> 32, so six allocations. Doubling keeps the number of reallocations logarithmic, which is why push_back is amortized O(1).
  2. 2. In a ring buffer with capacity 8, head_ = 6 and count_ = 3. At which index will the next push be written?

    The back position is (head_ + count_) % capacity = (6 + 3) % 8 = 1. The elements sit at indexes 6, 7 and 0.
  3. 3. Why does the linked list's destructor free nodes in a loop instead of letting head_ destroy the chain?

    A unique_ptr chain destroys itself recursively, one nested destructor call per node. With a million nodes that can exhaust the stack. The loop frees one node per iteration with constant stack depth.
  4. 4. You insert 1, 2, 3, 4, 5 in that order into a plain (unbalanced) binary search tree. What is its height?

    Each key is larger than all previous keys, so it becomes the right child of the last node. The tree degenerates into a chain of height 5, and searches become O(n).
  5. 5. In the BST, you erase a node that has two children. Which value replaces it?

    The in-order successor (go right once, then left as far as possible) is the next larger value, so putting it in the node keeps the BST ordering. The predecessor (largest value in the left subtree) works too.

Summary

  • A dynamic array keeps a size and a capacity; doubling the capacity makes appends amortized O(1). std::unique_ptr<T[]> gives you leak-free ownership with the rule of zero; std::vector goes further with uninitialized storage.
  • A stack is a dynamic array used at one end; pop() returns void so a failed copy can't lose an element, and std::optional makes a safe try_pop.
  • A ring buffer queue wraps its indexes with %, so push and pop are O(1) with no shifting and no allocation.
  • A singly linked list owns its nodes through std::unique_ptr and observes the tail through a raw pointer. The pointer-to-link trick removes special cases; a looping destructor prevents stack overflow on long lists.
  • A binary search tree finds, inserts and erases in O(height). Random input keeps it near logโ‚‚ n; sorted input degenerates it into a list, which is why std::set and std::map use self-balancing red-black trees.
  • Build these to understand them; use the standard containers in real code.

Next: Searching and Sorting Algorithms, where you'll implement binary search and six classic sorting algorithms and time them against std::sort.