---
title: "Linked list file system; block size impact"
subject: "Operating System"
chapter: 5
key: "semester_6/operating_system:fs-linked-list-block-size"
source: https://www.bctengineer.com/q/semester_6/operating_system/fs-linked-list-block-size
site: BCT Engineering
---

# Linked list file system; block size impact

Operating System · Chapter 5: File Systems

- Asked in: 2069 Bhadra, 4+6 marks
- Video: [File Allocation Methods: Contiguous, Linked & Indexed Explained!](https://www.youtube.com/watch?v=K-BAelpzNC8) — CodeLucky
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/operating_system/fs-linked-list-block-size
- Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-5

## Question

How can file system be implemented using linked list? Explain impact of block size selection on data rate and disk space utilization with necessary diagram and illustration.

## Short answer

Linked list stores next-block pointer in each block, no external fragmentation but slow random access. Larger blocks improve data rate (less seek/rotation overhead) but reduce space utilization due to internal fragmentation; e.g.,1 KB block yields 100% utilization and109 KB/s, 64 KB block3.1% and6.5 MB/s; compromise around4 KB.

## Answer

#### File system using a linked list
In linked-list allocation each file is a chain of disk blocks. One word of each block holds a pointer (the number of the next block); the rest is data. The directory entry stores the file name and the address of the first block.
```text
 dir: A -> 4
 block 4 : [data..|-> 7]
 block 7 : [data..|-> 2]
 block 2 : [data..|-> end]
```
- Any free block can be used, so there is **no external fragmentation**.
- Sequential reading is easy; the file can grow by taking any free block.
- Random access is slow (to reach block *n* read *n* blocks) and a block's data size becomes (block size - pointer size).
- Variation: a **FAT** keeps all next-pointers in a table in memory, which fixes random access speed.

#### Impact of block size
Block (cluster) size is a trade-off between data rate and space utilization.
- **Data rate:** time to read a block = seek + rotational delay + transfer time. Seek and rotation are fixed per access, so large blocks give a higher data rate.
- **Disk space utilization:** most files are small. If the block is larger than the file, space is wasted in the last block (internal fragmentation).

Illustration (Tanenbaum): average seek 5 ms, rotational delay 4.17 ms, transfer rate 100 MB/s, median file size 2 KB:

| Block size | Access time | Data rate | Space utilization |
|---|---|---|---|
| 1 KB | 9.18 ms | 109 KB/s | 100% |
| 2 KB | 9.19 ms | 218 KB/s | 100% |
| 4 KB | 9.21 ms | 434 KB/s | 50% |
| 16 KB | 9.33 ms | 1.7 MB/s | 12.5% |
| 64 KB | 9.83 ms | 6.5 MB/s | 3.1% |

```text
 data rate   ^            .---- rises with block size
             |        .-'
             |    .-'
             | .-'
 utilization |'-._
             |    '-._.__ falls with block size
             +----------------> block size
```
So a small block wastes less space but gives poor speed, and a large block is fast but wastes space. A compromise of 4 KB (or 2 to 8 KB) is common.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In linked-list allocation, what happens to usable block data size?
   A. It becomes block size minus pointer size
   B. It doubles
   C. Unchanged
   D. Zero
   Answer: A. The first bytes of each block hold the next-block pointer. (Key point: Linked list pointer)

2. Why is random access slow with linked lists?
   A. To reach block n you must read n blocks in the chain
   B. Blocks must be contiguous
   C. Directory is huge
   D. Pointers are lost
   Answer: A. The chain must be followed from the first block. (Key point: Access cost)

3. How does increasing block size affect data rate and utilization?
   A. Data rate rises, utilization falls
   B. Both rise
   C. Data rate falls, utilization rises
   D. Both fall
   Answer: A. Seek and rotation are per access, so bigger blocks transfer more per access but waste more in the last block. (Key point: Block size trade-off)

4. For median file size 2 KB, what is utilization with 4 KB blocks?
   A. 100%
   B. 50%
   C. 12.5%
   D. 3.1%
   Answer: B. A 2 KB file uses half of a 4 KB block. (Key point: Tanenbaum table)

## Related in Operating System

- [File system layout; i-node vs linked list](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afs-layout-inode-vs-linked-list) — Operating System, chapter 5
- [File system layers; linked list vs index](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afs-layers-linked-list-vs-index) — Operating System, chapter 5
- [File allocation methods; free space management](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afile-allocation-free-space-methods) — Operating System, chapter 5, asked 2×
- [File system layout; free block management](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Afs-layout-free-blocks) — Operating System, chapter 5
- [Page size impact; internal, external fragmentation](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-size-impact-fragmentation) — Operating System, chapter 4
- [Optimal replacement; fragmentation, utilization](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Aoptimal-fragmentation-utilization) — Operating System, chapter 4

## Related in other subjects

- [Digital data acquisition system block diagram](https://www.bctengineer.com/question.md?key=semester_4%2Finstrumentation_i%3Adigital-data-acquisition-system) — Instrumentation I, chapter 6
- [PCM block diagram; T1 signaling rate and frame](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Apcm-block-t1-rate-frame) — Communication Systems, chapter 5
- [Data acquisition block diagram and DCS advantages](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Adata-acquisition-advantages) — Digital Control System, chapter 1
- [Block diagram of digital communication system](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ablock-diagram-digital-comm) — Data Communication, chapter 1, asked 8×