Disadvantage of Using Linked Lists in Memory Management

Question

I'm kinda confused as to what the primary disadvantage of using a linked list would be in maintaining a list of free disk blocks. My professor said that using a bit map would help solve said problem. Why does using a bit map solve this problem?

To narrow down my questions:

1. What is the primary disadvantage of using a linked list in maintaining a list of free disk blocks?

2. Why does using a bit map solve this problem/disadvantage?

Answer 1

Hi,

What is the primary disadvantage of using a linked list in maintaining a list of free disk blocks?

• This scheme is not very efficient since to traverse the list, we must read each block requiring substantial time.
• The second disadvantage is additional memory requirement for maintaining linked list of all free disk blocks.

Why does using a bit map solve this problem/disadvantage?

• Most often the list of free disk spaces is implemented as a bit map or bit vector. Each block is represented by a single bit. 0(zero) is marked as a free block whereas 1 is for allocated block. So, no need of extra extra memory to store free disk space.

• Fast random access allocation check: Checking if a sector is free is as simple as checking the corresponding bit. so traversal is faster than LinkedList.

Other Advantage of using Bit Map:

• Fast deletion: Data need not be overwritten on delete, flipping the corresponding bit is sufficient

May this helps you. Fill free for further clarification.

Regards,

Bhavik