Data structures

Data is any information a program works with: a book’s title, a price, a list of songs. While the program runs, data lives in the computer’s memory. Picture memory as one very long row of numbered boxes. Each box holds a small piece of a value, and its number is its address, so the computer can go straight to box 5 000 without looking at the others.

Data

The information a program works with: numbers, text, lists of them.

Memory

Where a running program keeps its data: a long row of numbered boxes.

Byte

One box of memory: 8 bits, enough for a number from 0 to 255.

Address

A box’s number, which lets the computer reach it directly.

A data structure is a way of arranging data in memory, together with the operations you can do on it: read a value, find one, add one, remove one. The arrangement decides how much work each operation takes. No structure is best at everything; each one makes some operations cheap by making others dearer.

Think of a hundred books. You could keep them on a shelf in a row, in a pile on the floor, or as index cards in a box with one drawer per letter. Same books, three layouts, and very different work depending on what you want to do.

Almost everything you do with a collection of data is one of four operations. When you meet a new structure, ask how much work each one takes.

This course writes its structures in C++, a language that lets you see how data sits in memory. You write C++ as text, a compiler turns it into instructions the machine runs, and then it runs. Here the compiler (Clang) works inside this page: press Run.

1#include <iostream>2
3int main() {4  std::cout << "Hello, shelf\n";5  std::cout << "2 + 3 = " << 2 + 3 << "\n";6  return 0;7}

• #include <iostream> brings in the part of the standard library (the code that comes with C++) that prints.
• int main() is where every program starts. The { } braces hold its steps, each ending in ;.
• std::cout << x prints x. "\n" starts a new line. std:: says the name comes from the standard library.
• return 0; tells whoever started the program that it finished well.

Compiler

A program that turns code you write into instructions the machine runs.

`main`

The function every C++ program starts in.

`std::cout`

The standard output: << sends values to it to be printed.

Standard library

Ready-made code that comes with C++, under the name std.

A variable is a named box for a value. In C++ you say its type when you make it, and the type never changes: it tells the compiler how many bytes the value takes and what you can do with it.

1#include <string>2
3int pages = 412;               // a whole number4double price = 9.99;           // a number with a fraction5bool inStock = true;           // true or false6char grade = 'A';              // one character, in ' '7std::string title = "Dune";    // text, in " "8
9pages = pages + 1;             // now 41310// pages = "many";             // error: a string is not an int

1 copies = 3;2 weight = 0.45;3 onLoan = false;4 author = "Austen";

if runs some lines only when a condition is true. for repeats lines: for (int i = 0; i < 3; i++) starts i at 0, runs while i < 3, and adds one (i++) after each turn. A function is named steps you can call: it says the type it returns, then its parameters (the values it is given).

1#include <iostream>2
3int twice(int n) {        // returns an int, is given an int4  return n * 2;5}6
7int main() {8  for (int i = 0; i < 3; i++) {9    if (i == 1) {         // == compares; = would store10      std::cout << "one!\n";11    } else {12      std::cout << twice(i) << "\n";13    }14  }15}

Variable

A named box for a value, with a type that never changes.

Type

What kind of value a variable holds: int, double, bool, std::string…

Function

Named steps, given parameters, that may return a value.

Parameter

A value a function is given when it is called.

A shelf is a row of values, each at a numbered position from 0. In C++ a row of strings is a std::vector<std::string>; the next module shows what it is inside. To find a title you look at position 0, then 1, then 2, until you find it or run out of shelf. This is linear search: with n books, the worst case is n looks.

1#include <string>2#include <vector>3
4int indexOfTitle(const std::vector<std::string>& shelf,5                 const std::string& title) {6  for (int i = 0; i < shelf.size(); i++) {7    if (shelf[i] == title) return i;8  }9  return -1;10}11
12// indexOfTitle({"Emma", "Dune", "Beloved"}, "Dune") is 1

Measuring work by counting steps is the habit this course is built on. Write a search that also says how many books it looked at. To return two numbers at once, it returns a struct: a type you make yourself that groups named values (its members), here index and looks. Result{2, 3} makes one, and r.index reads a member.

1#include <string>2#include <vector>3
4struct Result {5  int index;6  int looks;7};8
9Result searchShelf(const std::vector<std::string>& shelf,10                   const std::string& title) {11  int looks = 0;12  // TODO: look at each book, counting the looks13  return Result{-1, looks};14}

If you mostly look books up by their ISBN (the number printed on the back), a row is the wrong layout. A map is a card box: it files each value under a key. std::unordered_map<std::string, Book> files books under string keys, and catalogue["222"] jumps to the book without looking at the others. How it manages that is the subject of the hash tables module.

std::vector<Book> books = {  {"111", "Emma"},  {"222", "Dune"}};for (const Book& b : books) {  if (b.isbn == "222") std::cout << b.title;}

std::unordered_map<std::string, Book> catalogue = {  {"111", {"111", "Emma"}},  {"222", {"222", "Dune"}}};std::cout << catalogue["222"].title;

for (const Book& b : books) is a range-for: it visits each value of a collection in turn, without counting positions yourself.

C++ shows you memory more directly than most languages. Each type has a fixed size in bytes, and a variable is its bytes: there is no hidden wrapper around an int.

• A std::vector<int> keeps its numbers themselves side by side: 4 bytes each, no gaps.
• A std::vector<Book> keeps the books themselves in a row, not links to books stored elsewhere.
• Copying a vector copies every value in it. That is why functions take const std::vector<…>&: they look at the caller’s vector instead.

• Data lives in memory: numbered boxes, each reachable directly by its address.
• A data structure is a layout plus operations; the layout decides what each operation costs.
• Ask four questions of any structure: how dear are read, search, insert and delete?
• A C++ program starts in main, prints with std::cout, and gives every variable a type.
• Linear search looks at every value in the worst case.
• Rearranging data (a map instead of a row) can turn a search into a direct look-up, at the cost of building it.
• C++ keeps values themselves side by side, and values side by side are faster to read, thanks to the cache.

An array keeps its values in contiguous memory: one slot after another, with no gaps, like seats in a cinema row. Every slot is the same size, because every value has the same type. The slots are numbered from 0, and a slot’s number is its index.

1int lengths[4] = {200, 185, 240, 210};   // a C array2lengths[2] = 245;                         // write slot 23int first = lengths[0];                   // read slot 0: 200

Array

Values of one type in a numbered row of same-sized slots.

Contiguous

Side by side in memory, with no gaps.

Index

A slot’s number, counted from 0.

Size

How many values the array holds.

Because the slots are the same size and side by side, the computer works out where any index lives with one small sum, then jumps there. It never walks along the row. Reading lengths[3] takes the same time as reading lengths[0], however long the array is. We call that constant time.

1address of slot i = start + i × slot size2
3lengths[0]  →  1000 + 0 × 4  =  10004lengths[3]  →  1000 + 3 × 4  =  1012

A C array does not remember how long it is, and nothing stops you reading past its end: you get whatever bytes sit there, or a crash. std::array<int, 4> (from <array>) is the same four slots in the same memory, wrapped so it knows its size() and works with the standard library. Its size is fixed when you write the code. sizeof(x) says how many bytes x takes, and &x gives its address.

1#include <array>2#include <iostream>3
4int main() {5  int c[4] = {200, 185, 240, 210};6  std::array<int, 4> a = {200, 185, 240, 210};7
8  std::cout << "sizeof(int) = " << sizeof(int) << "\n";9  std::cout << "sizeof(c)   = " << sizeof(c) << "\n";10  std::cout << "sizeof(a)   = " << sizeof(a) << "\n";11  std::cout << "a.size()    = " << a.size() << "\n";12
13  for (int i = 0; i < a.size(); i++) {14    std::cout << "a[" << i << "] is at " << &a[i] << "\n";15  }16}

A std::vector<int> (from <vector>) is an array that can grow; the slides after this show how. Passing one to a function copies it, every value, unless you ask otherwise. A reference, written & after the type, is another name for the caller’s variable: no copy, and changes show in the caller. A const reference, const std::vector<int>&, is a reference you promise not to change through.

1void addOne(std::vector<int> v) { v.push_back(1); }   // a copy2void addTwo(std::vector<int>& v) { v.push_back(2); }  // the same one3
4int total(const std::vector<int>& v) {                // looks only5  int sum = 0;6  for (int x : v) sum += x;7  return sum;8}9
10std::vector<int> nums = {5};11addOne(nums);   // nums is still {5}: the copy got the 112addTwo(nums);   // nums is {5, 2}

1int longest( lengths) {2  int best = 0;3  for (int x : lengths) if (x > best) best = x;4  return best;5}6
7void addSong( lengths, int seconds) {8  lengths.push_back(seconds);9}

`std::vector<T>`

An array of Ts that can grow at the end.

Reference (`T&`)

Another name for an existing variable: no copy.

`const T&`

A reference you can only read through: the usual way to pass big values.

Pass by value

The function gets its own copy of the argument.

The slots must stay side by side, so to insert a song at index 1, every song from index 1 onwards moves one slot to the right first, starting from the end so nothing is overwritten. Inserting near the front of a long array means moving almost every value.

1void insertAt(std::vector<std::string>& items, int index,2              const std::string& value) {3  items.push_back("");4  for (int i = items.size() - 1; i > index; i--) {5    items[i] = items[i - 1];6  }7  items[index] = value;8}

Removing is the mirror image: everything after the gap moves one slot to the left, then the vector gets one shorter: items.pop_back() drops the last slot.

1#include <string>2#include <vector>3
4std::string removeAt(std::vector<std::string>& items, int index) {5  std::string removed = items[index];6  // TODO: move each later value one slot left,7  // then drop the last slot8  return removed;9}

Memory next to an array is often taken by something else, so an array cannot always grow where it is. A dynamic array, which is what std::vector is, asks for a block of memory from the heap (memory a program asks for while it runs) with more slots than it needs: its capacity. While there is room, push_back just fills the next slot. When it is full, it asks for a new block of twice the capacity, copies every value over, and gives the old block back.

1#include <iostream>2#include <vector>3
4int main() {5  std::vector<int> v;6  for (int i = 1; i <= 20; i++) {7    v.push_back(i);8    std::cout << "size " << v.size()9              << ", capacity " << v.capacity() << "\n";10  }11}

Copying is slow, but it happens rarely, and each time the vector doubles, the next copy is twice as far away. After 9 pushes, 1 + 2 + 4 + 8 = 15 copies were made: fewer than 2 per push. Averaged over many pushes, each push costs a small, fixed amount. That kind of average over a whole run is called amortised cost, and the next module makes it precise.

A struct can hold functions too, called member functions: a.push(5) calls push on a, and inside it the names capacity, size and slots mean a’s members. Here a fixed row is pretended with a vector made at its full size, std::vector<int>(n); you only ever write inside it. copies counts the values copied, so the tests can check the doubling.

1#include <vector>2
3struct DynamicArray {4  int capacity = 1;5  int size = 0;6  int copies = 0;7  std::vector<int> slots = std::vector<int>(1);8
9  void push(int value) {10    // TODO: grow when full11    slots[size] = value;12    size++;13  }14
15  int get(int index) const { return slots[index]; }16};

Every std::vector operation’s cost follows from the slots. Working at the end is cheap; working at the front or in the middle moves everything after it. Positions in a vector are given as iterators: v.begin() is the first slot, v.begin() + 2 the third, v.end() just past the last. Big O, in the right column, is the short way to write the cost: O(1) is a fixed amount of work, O(n) work that grows with the size n. The next module explains it properly.

1std::vector<std::string> tasks = {"cook", "eat"};2tasks.insert(tasks.begin(), "shop");3tasks.push_back("wash up");4tasks.erase(tasks.begin());5std::cout << tasks[0] << " " << tasks.size();

A seating plan, a spreadsheet or a game board is a grid: rows and columns. In C++ a grid is often a vector of rows, each row a vector, so grid[row][col] reads one cell. This is a 2D array (two dimensions). std::vector<char> row(4, '.') makes 4 slots holding ., and seats(3, row) makes 3 copies of that row.

1#include <iostream>2#include <vector>3
4int main() {5  int rows = 3, cols = 4;6  std::vector<std::vector<char>> seats(7      rows, std::vector<char>(cols, '.'));8  seats[1][2] = 'X';                 // row 1, column 2 is booked9  for (const auto& row : seats) {10    for (char seat : row) std::cout << seat << ' ';11    std::cout << "\n";12  }13
14  // The same grid in one flat vector: index = row × cols + col15  std::vector<char> flat(rows * cols, '.');16  flat[1 * cols + 2] = 'X';17  for (char seat : flat) std::cout << seat;18  std::cout << "\n";19}

• An array is same-sized slots side by side, numbered from 0; sizeof shows the bytes.
• Reading or writing by index is one sum, start + i × size: constant time.
• C arrays and std::array have a fixed size; std::vector can grow.
• Pass a vector as const std::vector<T>& to read it, std::vector<T>& to change it; plain std::vector<T> copies it.
• Inserting or removing in the middle shifts every later value; at the front, all of them.
• A vector keeps spare capacity and doubles it when full, so push_back is cheap on average.
• A grid is a vector of rows, or one flat vector indexed by row × cols + col.

Timing code with a stopwatch tells you about your computer, today. A faster laptop halves the time; the code is the same. To compare ways of doing something, count the steps instead: the simple operations, such as one comparison or one addition, that the code performs. Then ask how that count changes as the input gets bigger. The input’s size is called n: the number of books, songs or tasks.

1int total(const std::vector<int>& prices) {2  int sum = 0;                    // 1 step3  for (int p : prices) {4    sum += p;                     // 1 step, n times5  }6  return sum;                     // 1 step7}

1for (const std::string& a : guests) {2  for (const std::string& b : guests) {3    greet(a, b);4  }5}

Exact counts like 3n + 5 are fiddly, and the details depend on what you call a step. Big O notation keeps only the part that matters when n gets large. Two rules get you there: drop the constants (3n becomes n) and keep only the biggest term (n² + n becomes n²). So 3n + 5 steps is written O(n), said "order n".

n

The size of the input: how many values there are.

Big O

How the work grows with n, ignoring constants and smaller terms.

O(1), constant

The same work whatever n is.

O(n), linear

Work that grows in step with n.

15n + 100        is  O()22n² + 3n + 1    is  O()342              is  O()

Five shapes cover most code you will meet. log n (the logarithm) is how many times you can halve n before reaching 1: about 10 for a thousand, 20 for a million.

1#include <cmath>2#include <iostream>3
4int main() {5  for (long long n : {10, 100, 1000, 10000}) {6    long long logN = std::round(std::log2(n));7    std::cout << "n=" << n << "  log n=" << logN8              << "  n log n=" << n * logN9              << "  n²=" << n * n << "\n";10  }11}

Looking a word up in a paper dictionary, you open it in the middle, see whether your word comes before or after, and throw away the wrong half. Each look halves what is left, so even a million words need only about 20 looks. On a sorted array this is binary search.

1int binarySearch(const std::vector<int>& sorted, int target) {2  int low = 0;3  int high = sorted.size() - 1;4  while (low <= high) {5    int mid = low + (high - low) / 2;6    if (sorted[mid] == target) return mid;7    if (sorted[mid] < target) low = mid + 1;8    else high = mid - 1;9  }10  return -1;11}

Checking a guest list for a name written twice, the obvious way compares every guest with every other: O(n²). Sorting first puts equal names next to each other, so one pass comparing neighbours is enough. A good sort costs O(n log n), and the pass O(n), so the whole thing is O(n log n): far less for big lists.

for (int i = 0; i < a.size(); i++)  for (int j = i + 1; j < a.size(); j++)    if (a[i] == a[j]) return true;return false;

std::vector<int> s = a;          // a copystd::sort(s.begin(), s.end());for (int i = 1; i < s.size(); i++)  if (s[i] == s[i - 1]) return true;return false;

1#include <algorithm>2#include <vector>3
4bool hasDuplicate(std::vector<int> nums) {5  // TODO: sort nums, then compare each value with the one before6  return false;7}

The same code can be fast or slow depending on the input. Linear search finds the first book in one look (the best case), needs every look when the book is last or missing (the worst case), and about n / 2 looks when the book is somewhere at random (the average case). Big O is usually quoted for the worst case, because that is the promise you can rely on.

Big O also measures space: the extra memory an operation needs as n grows, beyond the input itself. Reversing a playlist into a new array needs O(n) extra space. Reversing it in place, by swapping the ends and moving inwards, needs only a couple of variables: O(1) extra space.

1void reverseInPlace(std::vector<int>& a) {2  int left = 0;3  int right = a.size() - ;4  while (left  right) {5    int kept = a[left];6    a[left] = a[right];7    a[right] = kept;8    left;9    right;10  }11}

A vector’s push_back is usually one step, and occasionally a copy of everything. Its worst single push is O(n). But copies only happen when the capacity doubles, so over n pushes the copies add up to 1 + 2 + 4 + … which is less than 2n. Total work for n pushes is under 3n: O(n) for all of them, so O(1) amortised per push. This is the promise the C++ standard makes for std::vector::push_back.

• Measure work in steps as a function of the input size n, not in seconds.
• Big O drops constants and smaller terms: 3n + 5 is O(n).
• O(1) < O(log n) < O(n) < O(n log n) < O(n²); nested loops multiply.
• Halving the problem each step gives O(log n), as in binary search.
• Quote the worst case unless you say otherwise; space has a Big O too.
• Amortised cost averages over any run of operations: doubling makes push_back O(1) amortised.

A string is text: a sequence of characters (letters, digits, spaces, punctuation) in order. A std::string (from <string>) is laid out much like a std::vector<char>: the characters sit side by side, each has an index from 0, size() says how many there are, and reading one by index is instant.

1std::string title = "Dune";2
3std::cout << title.size();     // 44std::cout << title[0];         // D5std::cout << title.back();     // e: the last character6for (char ch : title) {7  std::cout << ch << ' ';      // D u n e8}

String

Text: a sequence of characters, written in double quotes.

Character (`char`)

One letter, digit, space or symbol: one byte in C++.

Substring

A piece of a string: une is a substring of Dune.

Unlike in many languages, a C++ string is mutable: you can change its characters where they are. s[0] = 'E' overwrites one byte; s += "!" adds to the end; s.insert and s.erase work like a vector’s. And like every C++ value, assigning a string copies it: two variables never share one string by accident.

1std::string name = "emma";2name[0] = 'E';                // "Emma": changed in place3name += " Woodhouse";         // "Emma Woodhouse"4
5std::string copy = name;      // a second string, same text6copy[0] = 'J';7std::cout << name << " / " << copy;   // Emma … / Jmma …

A std::string grows like a vector: it keeps spare capacity and doubles it when full. So s += piece only copies the piece, and is cheap amortised. s = s + piece is different: s + piece builds a whole new string, copying everything so far, before it replaces s. Doing that n times copies 1 + 2 + 3 + … characters: O(n²).

std::string receipt;for (const std::string& line : lines) {  receipt = receipt + line + "\n";}

std::string receipt;receipt.reserve(lines.size() * 40);  // a guessfor (const std::string& line : lines) {  receipt += line;  receipt += '\n';}

1#include <iostream>2#include <string>3
4int main() {5  std::string s;6  int last = -1;7  for (int i = 0; i < 200; i++) {8    s += 'a';9    if (s.capacity() != last) {10      last = s.capacity();11      std::cout << "size " << s.size()12                << ": capacity " << last << "\n";13    }14  }15}

1std::vector<std::string> items = {"bread", "milk", "eggs"};2std::string out;3for (const std::string& item : items) out += item + ", ";4std::cout << out;

With n characters in the string (and m in the one you search for), the costs follow from the layout. s.find(t) returns the index where t first appears, or the special value std::string::npos when it is not there. s.substr(i, len) copies len characters from index i.

1std::string csv = "tea,,scones";2int at = csv.find(',');3std::cout << at << " " << csv.substr(0, at)4          << " " << csv.find(',', at + 1);

A std::string_view (from <string_view>) is a window onto characters that live somewhere else: just a pointer to the first one and a length. Making one copies no text, and taking a piece of it, v.substr(i, len), is O(1): it only moves the window. It is the cheapest way to pass text you only read.

1#include <string_view>2
3int countSpaces(std::string_view text) {   // works for any text4  int spaces = 0;5  for (char c : text) if (c == ' ') spaces++;6  return spaces;7}8
9std::string line = "two words";10countSpaces(line);              // no copy11countSpaces("a b c");           // no std::string made at all

Build the reversed text in a new string, reading the original from its last index down to 0.

1#include <string>2
3std::string reverse(const std::string& s) {4  std::string out;5  // TODO: from the last character back to the first6  return out;7}

A palindrome reads the same both ways: "level", "Was it a car or a cat I saw". To check one, you do not need to build the reversed string. Keep two indexes, one at each end, compare those characters, and step both inwards. This is the two-pointer technique: O(n) time and O(1) extra space. (Here "pointer" just means an index; C++’s own pointers come in the linked lists module.)

1#include <cctype>2#include <string>3
4bool isPalindrome(const std::string& s) {5  std::string letters;6  for (unsigned char c : s) {7    if (std::isalnum(c)) letters += std::tolower(c);8  }9  int left = 0;10  int right = letters.size() - 1;11  // TODO: compare and move inwards12  return false;13}

A char is one byte, so there are only 256 possible values. To count how often each appears, keep an array of 256 counts and use the byte itself as the index: counts[c]++. One pass over the string, each update one sum, so the whole count is O(n), with a fixed 1 KB of memory however long the text.

1#include <array>2#include <iostream>3#include <string>4
5int main() {6  std::string word = "mississippi";7  std::array<int, 256> counts{};       // {} starts them all at 08
9  for (unsigned char c : word) counts[c]++;10
11  for (int c = 0; c < 256; c++) {12    if (counts[c] > 0) {13      std::cout << char(c) << ": " << counts[c] << "\n";14    }15  }16}

1#include <array>2#include <string>3
4bool isAnagram(const std::string& a, const std::string& b) {5  if (a.size() != b.size()) return false;6  std::array<int, 256> counts{};7  // TODO: add 1 for each of a's letters, take 1 for b's8  return true;9}

Computers store characters as numbers. Every character has a number in Unicode, its code point: A is 65, é is 233, 😀 is 128 512. A byte only holds 0 to 255, so a std::string stores text in UTF-8: plain English letters take 1 byte each, é takes 2, most emoji take 4. size() and s[i] count bytes, not characters.

1#include <iostream>2#include <string>3
4int main() {5  std::string s = "hé😀";6  std::cout << "size: " << s.size() << "\n";   // 7 = 1 + 2 + 47  for (unsigned char b : s) std::cout << int(b) << ' ';8  std::cout << "\n";9}

• A std::string is characters side by side, like a vector of char: s[i] and size() are O(1).
• C++ strings are mutable and copied on assignment; char& in a loop changes them in place.
• Build long strings with += (and reserve), never s = s + piece.
• std::string_view looks at text without copying, but does not own it.
• Two pointers from both ends check a palindrome in O(n) time and O(1) space.
• A byte has 256 values, so an array of 256 counts tallies characters in O(n).
• Strings hold UTF-8 bytes: size() counts bytes, and é and emoji take several.

Think of a treasure hunt: each clue tells you where the next one is hidden. You cannot jump to the fifth clue; you follow them from the first. A linked list works the same way. Each value lives in a node, a small struct that also holds a pointer: the address of the next node. The first node is the head; the last one is the tail, and its pointer is nullptr: nothing comes after.

Node

One value plus a pointer to the next node.

Pointer

A variable that holds the address of another value.

Head

The first node: where every walk along the list starts.

Tail

The last node, whose next is nullptr.

int* p is a pointer to an int: a variable whose value is an address. &x gives the address of x, and *p (dereferencing) means "the value at that address", to read or to change. nullptr is the pointer that points at nothing; dereferencing it is undefined behaviour (on most computers a crash; in this page it may quietly read garbage), so check first.

1#include <iostream>2
3int main() {4  int pages = 412;5  int* p = &pages;              // p holds the address of pages6  std::cout << "pages is at " << p << "\n";7  std::cout << "*p is " << *p << "\n";8
9  *p = 500;                     // change pages through p10  std::cout << "pages is now " << pages << "\n";11
12  int* nothing = nullptr;13  if (nothing == nullptr) std::cout << "nothing points nowhere\n";14  std::cout << "a pointer takes " << sizeof(p) << " bytes here\n";15}

1int a = 1;2int* p = &a;3int b = *p;4*p = 2;5std::cout << a << " " << b;

`T*`

A pointer to a T: holds a T’s address.

`&x`

The address of x.

`*p`

The value p points at (dereferencing).

`nullptr`

A pointer to nothing.

A node is a struct with a value and a next, which points at another node or is nullptr. The struct can mention itself (Node*), because a pointer’s size does not depend on what it points at. With a pointer to a struct, p->value reads a member: it is short for (*p).value.

1struct Node {2  std::string value;3  Node* next;4};5
6Node outro{"Outro", nullptr};7Node waves{"Waves", &outro};8Node intro{"Intro", &waves};9Node* head = &intro;

Visiting every node in order is called traversal. Keep a pointer to the node you are on, start it at the head, and after each node move it to next. When it becomes nullptr, you have fallen off the end.

1std::vector<std::string> toVector(const Node* head) {2  std::vector<std::string> values;3  const Node* node = head;4  while (node != nullptr) {5    values.push_back(node->value);6    node = node->next;7  }8  return values;9}

1int count(const Node* head) {2  int n = 0;3  const Node* node = ;4  while (node != ) {5    n++;6    node = nodenext;7  }8  return n;9}

A variable made inside a function lives on the stack and vanishes when the function ends. A list must outlive that, so its nodes go on the heap: new Node{…} asks the heap for room and returns a pointer, and the node stays until delete gives the memory back. Forget the delete and the memory is lost while the program runs: a memory leak. Use a pointer after its delete and it is dangling: it points at memory that may now hold something else.

1Node* makeList() {2  Node* outro = new Node{"Outro", nullptr};3  Node* intro = new Node{"Intro", outro};4  return intro;                // both nodes outlive the function5}6
7Node* head = makeList();8// … use the list …9delete head->next;             // free Outro10delete head;                   // free Intro11head = nullptr;                // so nobody uses it again

Stack

Where a function’s own variables live; they vanish when it returns.

Heap

Memory a program asks for with new, kept until it is freed.

Memory leak

Heap memory nobody frees, and nobody can reach any more.

Dangling pointer

A pointer to memory that has been freed.

A class is a struct whose members are private unless you say public: only its own member functions can touch them, so nobody can break its rules from outside. A constructor (named like the class) runs when one is made; a destructor (~ and the name) runs when it goes away, automatically. Code that frees things in a destructor can never forget to: this is called RAII.

1#include <iostream>2#include <string>3
4class Playlist {5public:6  Playlist(const std::string& n) : name(n) {   // constructor7    std::cout << "made " << name << "\n";8  }9  ~Playlist() { std::cout << "gone " << name << "\n"; }10
11  void add(int seconds) { total += seconds; }12  int length() const { return total; }13
14private:15  std::string name;16  int total = 0;17};18
19int main() {20  Playlist trip("Road trip");21  trip.add(200);22  trip.add(185);23  std::cout << trip.length() << "\n";24  { Playlist quick("Short"); }      // gone at its }25  std::cout << "end of main\n";26}

Class

A struct whose members are private by default.

Constructor

Runs when a value of the class is made, to set it up.

Destructor

~Name(): runs when the value goes away, to clean up.

RAII

Tying a resource (memory, a file) to a value, freed by its destructor.

std::unique_ptr<Node> (from <memory>) is a pointer with a destructor: when it goes away, it deletes its node. Exactly one unique_ptr owns each node, so it cannot be copied, only moved: std::move(a) hands the node over and leaves a empty. std::make_unique<Node>(…) makes a node on the heap, and .get() gives a plain pointer for looking, without owning.

1#include <memory>2
3struct Node {4  std::string value;5  std::unique_ptr<Node> next;              // owns the next node6  Node(const std::string& v) : value(v) {}7};8
9auto head = std::make_unique<Node>("Intro");10head->next = std::make_unique<Node>("Waves");11Node* second = head->next.get();           // looks, does not own12
13std::unique_ptr<Node> other = std::move(head);  // head is now empty14// No delete anywhere: when other goes, Intro goes, then Waves.

To prepend (add at the front), make a node whose next is the old head, and make it the head. Nothing moves, whatever the length: O(1). Compare inserting at the front of a vector, which moves every value.

To append (add at the end), you need the last node. Walking there is O(n), so a list class also keeps a tail pointer, and appending becomes: point the old tail at the new node, then move tail to it. O(1) again. The head owns the first node, each node owns the next, and tail is a plain Node*: it only looks.

To remove a node you make the node before it skip over it: previous->next = std::move(previous->next->next). The removed node has lost its owner, so its unique_ptr deletes it on the spot. Finding the node is O(n); the unlinking itself is O(1), with no shifting at all.