Linked lists

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 queue (or LIFO—short for Last In First Out) structure.