linked allocation

Picture a treasure hunt where each clue tells you where the next clue is hidden. You start at clue one, it points to a spot across the park, that spot holds clue two and a pointer to clue three, and so on until the last clue says the hunt is over. Linked allocation stores a file the same way: the file's blocks can sit anywhere on the disk, and each block contains, alongside its data, a pointer to the next block of the file.

The file's directory entry (or inode) only needs to remember two things: the address of the first block and, often, the last block. To read the whole file you start at the first block, use its trailing pointer to find the second, and follow the chain to the end (a special end marker, like -1, finishes it). Growing a file is wonderfully easy: grab any free block, write the data, and patch the previous last block to point at it — no need for a contiguous run of free space, so external fragmentation simply does not happen.

The catch is the price you pay for that flexibility. Reading the 500th block means walking through the first 499 to find it, so random access is slow — linked allocation is really only good for sequential reading. Worse, the pointers are mixed in with the data, so a useful data block is no longer a clean power-of-two size, and if a single pointer is corrupted the rest of the file is lost. These weaknesses are exactly why the file-allocation table (FAT) was invented: it pulls all the pointers out of the data blocks and gathers them into one table.