Data structures

A static structure has its size fixed when it is created, in one contiguous block of memory. A dynamic structure grows and shrinks while the program runs, taking more memory only when it needs it.

Everything sits in one block with items of equal size, so the address of item 20 is simply the start plus twenty item-widths. It is one calculation, with nothing searched for — O(1).

When it outgrows its block it must claim a bigger one and copy everything across. That single operation is expensive, but it happens rarely, so the average cost of adding an item stays low.

When the size is genuinely fixed — twelve months, seven days, sixty-four squares — or when a very large amount of data is scanned repeatedly and both speed and predictable memory matter.

You must guess a maximum. Guess too small and it overflows or silently discards data; guess too large and most of the memory is never used — with still no guarantee the guess was enough.

By position, starting at 0. A list of four items has positions 0, 1, 2 and 3, so asking for position 4 is an error — the commonest list bug there is.

append adds at the end, insert(position, value) adds anywhere and shifts the rest along. remove(value) takes out the first match, and pop() removes the last item and gives it back.

Removing shifts everything after it down one place while the loop counter moves up, so items get skipped silently. Build a new list instead, or loop over a copy.

A list whose items are themselves lists — a grid. It is addressed [row][column], always in that order: grid[1][2] is row 1, column 2.

The outer loop gives you each row, which is itself a list; the inner loop reaches the individual values inside it. That is also why scanning a grid is O(rows × columns).

A structure that allows adding and removing at one end only, the top. The last item put in is the first taken out — last in, first out, or LIFO.

push adds an item on top; pop removes the top item and returns it; peek returns the top item without removing it; isEmpty says whether there is anything in the stack at all.

Every operation touches only the top. Nothing is shifted along and nothing is searched for, so the cost is the same whether the stack holds three items or three million.

Undo, where the most recent action must be reversed first; the call stack, since function calls unwind in reverse order; and checking that brackets match, because the most recent opening bracket must close first.

A stack that keeps growing with nothing being popped until it runs out of memory — usually a function that calls itself with no way to stop.

A structure added to at one end and taken from at the other: items join at the back and leave from the front. The first item in is the first out — first in, first out, or FIFO.

enqueue adds an item at the back; dequeue removes the item at the front and returns it; front returns the next item out without removing it; isEmpty says whether anyone is waiting.

Removing from the front of a list shifts every remaining item down one place, which is O(n) every time. A proper queue structure removes from the front in constant time.

Does the most recent item matter most, or the one that has waited longest? Most recent means a stack; longest waiting means a queue.

Print jobs, so they print in the order sent; process scheduling, where round robin takes the front process and returns it to the back; and buffering data such as keystrokes or network packets, which must be handled in arrival order.