Course contentsShow
← Computer Science
Lesson 1400 of 2,87232. File SystemsFree lesson

File Allocation Methods: Linked

Understand linked allocation using pointers to chain blocks together and its random access limitations.

File Allocation Methods: Linked

You'll learn how linked allocation chains file blocks together using pointers, and why this makes random access slow.

The Core Idea

In linked allocation, each disk block stores both data and a pointer to the next block in the file. Think of it like a scavenger hunt: each clue (block) contains part of your treasure (file data) plus directions to the next clue's location. The directory entry for the file stores only the address of the first block; from there, you follow the chain.

Unlike contiguous allocation (where all blocks sit together), linked allocation lets blocks scatter anywhere on disk. When you need a new block, grab any free one and link it to the chain—no more external fragmentation!

How It Works

When the OS reads the directory, it finds the starting block address. To read the file sequentially:

  1. Read block N, extract data
  2. Follow pointer to block N+1
  3. Repeat until you hit a null pointer (end-of-file marker)

Each block dedicates a small portion (e.g., 4 bytes) to store the next block's address, slightly reducing usable space per block.

The Random Access Problem

Here's the catch: to read byte 1,000,000 in your file, you can't jump directly there. You must start at the beginning and follow every single pointer in the chain until you reach the block containing that byte. It's like needing the 100th clue in a scavenger hunt—you have to follow all 99 clues before it!

This makes linked allocation terrible for random access patterns (databases, multimedia) but acceptable for sequential reading (log files).

Key Takeaway: Linked allocation eliminates external fragmentation by chaining blocks with pointers, but requires traversing the entire chain for random access, making it inefficient for non-sequential operations.