To keep track of a bunch of items, there is a simple solution: with each entry in the list, store a pointer to the next entry. If there is no next item, store null/nil/None and so on, and keep a pointer to the first item. This is called a singly linked list, where each item is connected with a single link to the next, as shown in the following diagram—but you already knew that:
What are the real use cases for a linked list though? Doesn't everyone just use a dynamic array for everything?
Consider a transaction log, a typical append-only structure. Any new command (such as a SQL statement) is simply appended to the existing chain and is eventually written to a persistent storage. Thus, the initial requirements are simple:
- Append a command to an existing list
- Replay every command from the beginning to the end—in that order
In other words, its a...