Even in the 16-bit days, game consoles were basically just small, embedded computers running realtime software, and the data structures we used are the same ones you'd find anywhere in computer science: arrays, matrices, heaps, trees. Not many linked lists because they're so slow (indirect lookups have a long latency).

The difference is that before the STL, and with performance so critical, we usually had to write the structures and algorithms ourselves!

Even in the 16-bit days, game consoles were basically just small, embedded computers running realtime software, and the data structures we used are the same ones you'd find anywhere in computer science: arrays, matrices, heaps, trees. Not many linked lists because they're so slow (indirect lookups have a long latency).

The difference is that before the STL, and with performance so critical, we usually had to write the structures and algorithms ourselves!

David Braben did a fun lecture at the 2011 GDC where he talked about all the crazy tricks he used to fit Elite onto a BBC Micro in 1984. You can watch it for free at the GDC Vault.