Contiguous vs Linked vs Indexed: Key Differences and Usage

In operating systems, contiguous allocation stores files in consecutive blocks, linked allocation stores file blocks scattered with pointers linking them, and indexed allocation uses an index block to keep track of all file block locations. Each method balances speed, simplicity, and space efficiency differently.

Quick Comparison

Here is a quick overview comparing contiguous, linked, and indexed allocation methods based on key factors.

Factor	Contiguous Allocation	Linked Allocation	Indexed Allocation
Storage Layout	Blocks stored consecutively	Blocks scattered, linked by pointers	Blocks scattered, tracked by index block
Access Speed	Fast sequential and direct access	Slow direct access, fast sequential	Fast direct and sequential access
Space Efficiency	May waste space due to fragmentation	No external fragmentation	No external fragmentation, some overhead for index block
File Size Limit	Limited by contiguous free space	Can grow easily	Can grow easily
Complexity	Simple to implement	Simple but pointer overhead	More complex due to index management
Reliability	If one block lost, file corrupted	If pointer lost, rest of file lost	Index block loss affects file access

Key Differences

Contiguous allocation stores all file blocks next to each other on disk. This makes reading files very fast because the disk head moves minimally. However, it can cause wasted space (fragmentation) and limits file size to available consecutive blocks.

Linked allocation stores file blocks anywhere on disk and links them with pointers. This avoids fragmentation and allows files to grow easily, but direct access is slow because you must follow pointers from the start to reach a block.

Indexed allocation uses a special index block that holds pointers to all file blocks. This allows fast direct access without needing consecutive blocks. It avoids fragmentation but requires extra space for the index and more complex management.

Code Comparison

Example of reading a file stored with contiguous allocation by accessing blocks directly.

javascript

class ContiguousFile {
    constructor(startBlock, length, disk) {
        this.startBlock = startBlock;
        this.length = length;
        this.disk = disk; // array representing disk blocks
    }

    read() {
        let data = '';
        for (let i = this.startBlock; i < this.startBlock + this.length; i++) {
            data += this.disk[i];
        }
        return data;
    }
}

// Disk blocks example
const disk = ['A', 'B', 'C', 'D', 'E', 'F', 'G'];
const file = new ContiguousFile(2, 3, disk); // blocks C, D, E
console.log(file.read());

Output

CDE

Linked Allocation Equivalent

Example of reading a file stored with linked allocation by following pointers from block to block.

javascript

class LinkedFile {
    constructor(startBlock, disk) {
        this.startBlock = startBlock;
        this.disk = disk; // object with block data and next pointer
    }

    read() {
        let data = '';
        let current = this.startBlock;
        while (current !== null) {
            data += this.disk[current].data;
            current = this.disk[current].next;
        }
        return data;
    }
}

// Disk blocks example
const disk = {
    0: { data: 'C', next: 1 },
    1: { data: 'D', next: 2 },
    2: { data: 'E', next: null }
};
const file = new LinkedFile(0, disk);
console.log(file.read());

Output

CDE

When to Use Which

Choose contiguous allocation when you need fast access and files are mostly fixed size, like in simple systems or embedded devices.

Choose linked allocation when files grow unpredictably and you want to avoid fragmentation, but can tolerate slower direct access, such as in simple file systems.

Choose indexed allocation when you want fast direct access and flexible file sizes without fragmentation, common in modern file systems like UNIX's inode system.

Key Takeaways

Contiguous allocation offers fast access but risks fragmentation and limits file size.

Linked allocation avoids fragmentation and allows easy file growth but slows direct access.

Indexed allocation balances fast access and flexibility with some overhead for index blocks.

Choose allocation method based on file size variability, access speed needs, and fragmentation tolerance.