File Allocation Methods in Operating Systems: Contiguous, Linked and Indexed Worked Examples
Compare contiguous, linked and indexed allocation by tracing the same file across disk blocks. Then calculate growth costs and a two-level index lookup.
KnowledgeGate Team
Exam prep & CS education

Contiguous, linked and indexed allocation map the same file with different metadata, block maps, access paths and growth rules. A 13,000-byte file uses different block maps under each method; growing it to 20,000 bytes changes the allocation metadata, and a two-level index determines the lookup path.
What file allocation must record and why the method matters
A file is a logical byte sequence; a disk block is a fixed-size physical unit. Logical blocks 0, 1, 2, and so on map to physical blocks, so file metadata must recover that mapping.
Ask: Where are the blocks? How is one found? What happens as the file grows? A bitmap or free list selects free blocks; the allocation method records ownership and access paths.
Contiguous allocation stores start block plus run length; linked allocation connects scattered blocks by pointers; indexed allocation holds data-block addresses in an index block. File Systems and I/O for GATE connects pathname resolution, open-file state, inode levels and device timing. The 13,000-byte trace isolates allocation layouts, growth updates and a two-level index lookup. The CS Fundamentals map places file allocation within the wider subject.
Compare contiguous, linked and indexed allocation before calculating
Compare the trade-offs side by side.
Method | Directory metadata | Sequential access | Random access | Growth | Main cost |
|---|---|---|---|---|---|
Contiguous | Start block + length | Direct arithmetic | Direct arithmetic | Needs adjacent space | External fragmentation |
Linked | First block, optionally last block | Follows pointers well | Slow in ordinary linked allocation | Add any free block | Pointer space |
Indexed | Index-block address | Direct lookup through index | Direct lookup through index | Add any free data block | Index metadata, possibly multiple levels |
External fragmentation means free space exists, but not as the required adjacent run. Internal waste lies inside the final allocated block. Linked and indexed allocation avoid adjacent-run constraints but retain block and metadata overhead.
A FAT-style table changes linked access and space accounting. Here, each linked data block contains one next pointer.
Worked example: store the same 13,000-byte file three ways
Let results.bin contain 13,000 bytes. Blocks are fixed-size 4,096-byte units, pointers are 4 bytes, and the target is zero-based logical data block 2, the third data block. Block numbers are illustrative; all offsets and indices are zero-based. Assume no cache, directory metadata available, and no directory-lookup or free-space-map cost.
For contiguous and indexed allocation:
ceil(13,000 / 4,096) = 4 data blocks
4 x 4,096 = 16,384 bytes of data-block capacity
16,384 - 13,000 = 3,384 unused bytes in the last data block
For contiguous allocation, the directory stores start=20, length=4, covering physical blocks 20, 21, 22, 23. Logical block 2 maps as 20 + 2 = physical block 22 and needs one data-block read.
In linked allocation, each block reserves 4 bytes for its next pointer, leaving 4,096 - 4 = 4,092 payload bytes. Therefore, ceil(13,000 / 4,092) = 4 blocks. The chain is 20 -> 41 -> 7 -> 32 -> EOF. Payload capacity is 4 x 4,092 = 16,368 bytes, leaving 16,368 - 13,000 = 3,368 unused payload bytes; four pointer fields occupy 16 bytes. Reaching logical block 2 means reading 20, 41, then target 7: three block reads.
For indexed allocation, the directory points to index block 50, containing index[0]=20, index[1]=41, index[2]=7, and index[3]=32. The file uses four data blocks plus one index block. Logical block 2 reads block 50, then data block 7: two reads, or one if the index is cached. The four live entries use 16 bytes. Block 50 is metadata, not file data.

Grow the file and expose each method's trade-off
Grow results.bin to exactly 20,000 bytes. Contiguous and indexed allocation require ceil(20,000 / 4,096) = 5 data blocks. Their last-block waste is 5 x 4,096 - 20,000 = 20,480 - 20,000 = 480 bytes.
Linked allocation also needs five blocks because ceil(20,000 / 4,092) = 5. Its 5 x 4,092 = 20,460 payload bytes leave 20,460 - 20,000 = 460 unused payload bytes. Five pointer fields reserve 20 bytes.
Contiguous allocation extends run 20-23 only if block 24 is free. Otherwise, this simplified model relocates the file to run 60-64 and sets start=60, length=5; real implementations may differ.
Linked allocation appends free block 55: change block 32 from EOF to next=55, then store EOF in block 55. Indexed allocation adds block 55 as index[4]=55 in index block 50, which does not move.
Indexed-allocation capacity and a two-level lookup numerical
For a separate example, use a 1,024-byte block and a 4-byte pointer. One index block holds 1,024 / 4 = 256 pointers. A single-level index addresses 256 data blocks, giving 256 x 1,024 = 262,144 bytes = 256 KiB of file data.
In a two-level index, the outer block has 256 pointers to inner blocks, each holding 256 data-block pointers. Maximum file data is 256 x 256 x 1,024 = 67,108,864 bytes = 64 MiB; index blocks are metadata and excluded.
Because 530,000 exceeds the single-level 262,144-byte capacity, one index block cannot address this offset.
Resolve zero-based byte offset 530,000:
Logical block number:
floor(530,000 / 1,024) = 517.In-block displacement:
530,000 mod 1,024 = 592.Outer index:
floor(517 / 256) = 2.Inner index:
517 mod 256 = 5.
The path is outer index entry 2 -> inner index entry 5 -> data block. With no cache, it costs two index-block reads plus one data-block read; with both indexes cached, only the data read remains.

Exam-style question forms and the traps that change the answer
Typical questions identify a method from metadata, count blocks, translate a logical block or byte offset, compare access under cache assumptions, update metadata after growth, or distinguish waste, fragmentation and pointer overhead. Use File Systems & Allocation MCQs for practice.
Wrong move | Correct check |
|---|---|
Use | Allocation needs |
Map contiguous logical block 2 to | Zero-based mapping gives |
Call index block | It is metadata, not file data. |
Say linked random access jumps straight to block | Without a FAT or cached chain, traverse |
Use 4,096 payload bytes in the linked model | The 4-byte pointer leaves 4,092 payload bytes. |
Call all unused bytes external fragmentation | The 3,384 last-block bytes are internal waste. |
File allocation maps logical blocks to physical blocks; disk scheduling orders pending device requests. File systems and disk scheduling in OS works a separate seek-order calculation across FCFS, SSTF, SCAN and C-SCAN. Syllabus coverage and paper patterns differ between examinations, so check what is currently in scope for the exam you are sitting.
File allocation methods: the short version and next step
Recall: contiguous = start + arithmetic + adjacent growth; linked = first block + pointer traversal + easy scattered growth; indexed = index lookup + direct access + metadata block. With no cache, logical block 2 needs 1 read in contiguous, 3 in linked and 2 in indexed allocation.
Redraw the three layouts from memory and check that logical block 2 lands on physical blocks 22, 7, and 7 for contiguous, linked and indexed allocation, then explain why linked allocation needs three reads while indexed needs two. Zero to Hero: Complete CS Course extends the same block-mapping skills into a sequenced core-CS path.
Keep learning
File Management in Operating Systems: Allocation, Directories and Worked Examples
Connect a filename to its inode, open-file state, and physical blocks. Then compare allocation methods and solve one complete block-allocation example.
File Systems and Allocation MCQs: 12 solved questions with explanations
File systems and allocation MCQs for GATE, state PSC and PSU papers: contiguous, linked and indexed allocation, Unix i-node sizing, directories, disk layout.
File Allocation Methods MCQs: 10 Solved Questions with Explanations
Practise ten questions on contiguous, linked and indexed allocation. Each answer includes the reasoning, arithmetic and a useful boundary check.
File Systems and I/O for GATE: Allocation, Inodes and Worked Examples
A file-system question becomes manageable when you trace the path from a name to an inode, blocks and device I/O. Work through allocation, offsets and timing with reproducible examples.





