Arrays and linked lists

01Arrays

An array stores elements contiguously, making indexed access fast and cache-friendly. Fixed arrays have a fixed size; dynamic arrays such as std::vector grow by allocating a larger region and moving/copying elements.

int fixed[4] = {10, 20, 30, 40};
std::vector<int> dynamic{10, 20, 30};
dynamic.push_back(40);

02What a node is

A linked-list node stores a value plus a link to another node. The nodes do not have to be contiguous in memory. This makes insertion/removal easy when you already have the correct link, but random indexing requires walking through nodes.

struct Node {
    int value;
    Node* next;
};

Node third{30, nullptr};
Node second{20, &third};
Node first{10, &second};

03Trade-offs