Question

Consider a linear list based directory implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks. Consider a given directory \texttt{foo. Which of the following operations will necessarily require a full scan of \texttt{foo} for successful completion?}

• A. Creation of a new file in \texttt{foo}
• B. Deletion of an existing file from \texttt{foo}
• C. Renaming of an existing file in \texttt{foo}
• D. Opening of an existing file in \texttt{foo}

Hint:

In linear directory implementations, any operation that must ensure file-name uniqueness requires a complete directory scan.

Answer 1

The Correct Option is A, C

Step 1: Understand linear list–based directory structure.
In a linear list–based directory, file entries are stored sequentially without any indexing or hashing mechanism.

As a result, operations that must verify a condition against all file names may require traversing the entire directory.

---

Step 2: Analyze creation of a new file.
When creating a new file in directory foo, the system must ensure that no existing file has the same name.

Since the directory is maintained as a linear list, this uniqueness check requires comparing the new name with every existing entry.

Hence, a full directory scan is necessary.

---

Step 3: Analyze renaming of an existing file.
Renaming a file also requires verifying that the new name does not conflict with any other file name in the directory.

This again involves checking the new name against all directory entries, which necessitates a full scan.

---

Step 4: Eliminate other operations.

Option (B) — Deletion:
Deletion requires locating the file, but once it is found, the operation can be completed without scanning the remaining entries.

Option (D) — Opening a file:
Opening a file only requires searching until the matching entry is found. A complete traversal of the directory is not mandatory.

---

Final Conclusion:
The operations that necessarily require a full scan of directory foo are:

• Creation of a new file
• Renaming of an existing file