Choosing the Right Structure

Ask what the data must do

Don't start from "which structure?" Start from "what operations do I need to be fast?" Reading by position? Adding at one end? Looking up by name? Each structure is fast at some things and slow at others, by design. Match the structure to your *hottest* operation.

It also helps to ask: is the size fixed or will it grow? Do I care about the order items arrive in, or just whether something is present? A two-minute think here saves you from rewriting a slow O(n) loop into a fast one later. Run your problem down the checklist below.

1. Need to read/write by index (the 5th item)? -> array (or std::vector).
2. Need Last-In-First-Out (undo, call stack, backtracking)? -> stack.
3. Need First-In-First-Out (fair scheduling, BFS)? -> queue.
4. Need fast lookup/insert/delete by key (a name -> a value)? -> hash table.
5. Need both ordering AND fast lookup? -> a tree (preview below).

The cost cheat-sheet

Here is the whole rung on one card. "Average" matters for the hash table — its worst case is O(n), but with decent hashing you rarely see it. Memorize the *shape* of this table, not the exact cells; the shape is what guides your choice.

structure      access     search     insert     delete
-----------    -------    -------    --------   --------
array          O(1)       O(n)       O(n)*      O(n)*
linked list    O(n)       O(n)       O(1)**     O(1)**
stack          O(1) top   --         O(1) push  O(1) pop
queue          O(1) ends  --         O(1) enq   O(1) deq
hash table     --         O(1) avg   O(1) avg   O(1) avg

*  array insert/delete is O(1) only at the very end
** linked list O(1) only once you HOLD a pointer to the spot

Worked decisions

Let's run the questions on real problems. "Count how often each word appears in a book." You need to look up a word and bump its count — fast lookup by key — so a hash table (`std::unordered_map<std::string,int>`) wins.

"Process print jobs in the order they were submitted." Arrival order, served from the front — that's a queue. "Implement Undo." The most recent action reverses first — a stack. "Store 256 fixed pixel values you'll read by index constantly." Pure indexing — an array.

And "a list where I'm always inserting and deleting in the middle, never indexing"? That's the rare sweet spot for a linked list — once you hold a pointer to the spot, the edit is O(1).

When linear isn't enough: a tree preview

There's one combination none of these four nails: keep items sorted AND look them up fast. A hash table is fast but unordered; a sorted array keeps order but inserts in O(n). The answer is a structure with branches instead of a single line — a tree, and specifically the binary search tree, which gives O(log n) ordered lookup and insert.

         (8)
        /   \
      (3)    (10)
      / \       \
    (1) (6)     (14)

ordered + fast: each step halves the search -> O(log n)

That's the next rung. For now, the win is a habit: before you write code, name the operations you need, then pick the structure whose costs match. The structure is a decision, not a default.