Link-a-List

In C you have ‘arrays’ — finite-length data structures for storing sequences of information.

Problem is, you have to declare their length[footnote]You can do some fancy memory allocation stuff, but it’s all rather ‘meh’.[/footnote]. If you set the length to 10 but end up wanting 15 items, you’re screwed. Conversely, if you set it to 1000 but only use 15 items, you’re wasting space. Lots of space.

One solution is a ‘linked list’ — a variable-length data structure. Each item in the data structure is a ‘node’ containing two properties: the information stored and the address of the next item in the list (or ‘NULL’ if there isn’t one). To add an item to the list, simply update the address of the previously-last item to this new one and voila!

There are some efficiency trade-offs, such as the time to access an item, searching, etc., but that’s where other data structures come in…