Linked Lists

When storing data, it's often impossible to pre-allocate storage space. Often you won't know how much data there will be. You will end up either having wasted, unused storage space or you'll underestimate and run out of space. Using linked lists can create a storage structure that is flexible, extensible and scalable.

The key to a linked list is that each item in the list has a pointer to the next item in the list (somewhat similar to a binary tree). Linked lists are often used in stacks and queues, and most famously form the basic of MS-DOS and pre-NTFS Windows file systems! If your memory stick is formatted as FAT32, it relies on a linked list to work!

Getting an idea of how it works - two personal examples

1. When I taught English I often taught To Kill a Mockingbird to year 10. An important part of that was finding quotations related to a number of themes, such as prejudice, misleading appearances and courage. In class I'd have to be able to link related quotes quickly, e.g. "There's a good example of prejudice on page 67 and the next is 96, and compare that with a similar line on page 126."

How I did this was to write a list of important themes (e.g. prejudice) on the inside front cover and beside each one would be the first occurrence of that theme (e.g. 67). By looking up Prejudice and turning to page 67, I'd see the quote and beside it would be a little arrow pointing forward to the page number of the next occurrence (e.g. 96). Flip to page 96 and there's another arrow and the number 126.

That's an example of a singly-linked list - each node (page) contains a pointer to the next one. It can stretch on endlessly.

In fact, often I'd find a quote (e.g. on page 96 and want to know what the previous quote was. So often quotes had not only a forward link to the next quote (=> 126) but also a backward link to the previous quote (<=67). Such a doubly-linked list lets you travel in either direction from a given starting point.

Perhaps when you found the last quote in the book you'd want a link back around to the first quote again: this would be a circular (singly- or doubly- ) linked list.

Example 2

I have a book about Iron Chef. Each chapter has a list of episodes from the different seasons. When searching for episodes, it was painful searching for page where the next season's episodes began. So, at the end of the season 1 list (e.g. on page 34) I'd write the page number of the start of the season 2 list (e.g. page 56). On page 56 there would be a link forward to the next season's page (e.g. 78) and a link back to the previous season's list. At the end of the last season was a link to the start of the first season, making it a doubly-linked circular list. In this way I could instantly leap from one point to the continuation point - backwards or forwards.

A FAT EXAMPLE

For many years, most operating systems used linked lists to map the locations of files on disk. Both MS-DOS and CP/M used FATs (File Allocation Tables) to manage the lists of filenames and their locations on disk. Even Windows used a FAT up to Windows Me when the NTFS appeared, however 'universal devices' such as portable memory keys still use FAT32 so any computer can read their contents.

Very simply, a FAT works like this.

A filename is stored in a list (e.g. fred.doc) along with the location where the first chunk (cluster) of the file is to be found. Remember that disks are divided into clusters (groups of sectors) and a file can have its parts scattered widely over a disk. The FAT keeps track of which clusters are being used and which ones are free, so when a file is saved the FAT is looked up to find unused disk locations where parts of the file can be stored.

Tip: defragmentation is the process in which the scattered clusters of a file are gathered together and re-stored one after the other to speed up disk access.

When fred.doc has to be loaded, its name is looked up in the filename table. This returns its cluster where its first file part resides. The operating system then grabs the contents of that cluster. The OS then looks up the FAT: the FAT lists every cluster on the disk in numerical order. Beside the cluster number is a magic value. That value can be one of several possible entries. The value might mark the sector as empty (available for use), bad (do not use it), reserved (used by the system), or it might contain the number of another cluster. If the file extends over several cluster, this number points to the cluster that has the next part of the file. The OS spins the disk heads to that location, reads the cluster and returns to the FAT to check the entry for that cluster. If it contains yet another cluster number, the OS fetches the disk contents. If the FAT contains another special marker ("last cluster") the OS knows that the file fetching is finished.

By using a linked list, the OS can use disk space efficiently and manage files of nearly any length. It's a simple yet remarkably effective way to store data.

A simplified version of how a linked list can work in an OS's FAT.