What is linked list allocation of disk space?

An allocation method defines how a file will be stored within the disk.

The operating system uses the file or disk space allocation method to store our files in an efficient manner that allows for the utilization of disk space and fast access to the file.

Linked list allocation

Within the scope of linked list allocation, each individual file is considered to be a linked list of file blocks. Each file block contains some data and a pointer to the next file block.

The file blocks can be dispersed throughout the disk space. This means we can avoid fragmentation within our disk, as in the case of contiguous allocation. This is a much more efficient approach, and it prevents the unnecessary waste of space.

Inside the disk

The directory contains a pointer to the first and last blocks of the file. Using these, we can traverse the entire linked list to retrieve our data.

Let’s look at an example:

In the above example, we consider a file: edpresso. This file is stored within our disk. According to the directory, the first block of the file can be found at the physical address 1.

Once we arrive at the starting file block, we simply follow the pointers to retrieve the data.

By following the pointers, we obtain the following sequence of physical addresses:

1 → 7 → 11 → 12 → 3 → 19

Extracting the data within the file blocks: Concise shots of dev knowledge.

Advantages

Linked list allocation avoids external fragmentation. This means that memory blocks are not wasted, as in the case of contiguous allocation.

It is also very easy to increase the size of our file. We simply need to add another file block to our linked list. Thus, as long as memory blocks are available, the file can grow.

Finally, linked list allocation puts less load on the directory as it only needs to contain the starting and ending pointers of the file.

Disadvantages

Linked list allocation does not allow for random or direct memory access. If we want to access a specific file block, we will have to traverse the entire linked list until we find the relevant block.

The pointers that are stored within the linked list also incur some extra overhead.