Directory Implementation

Directories need to be fast to search, insert, and delete, with a minimum of wasted disk space.

Linear List

·         A linear list is the simplest and easiest directory structure to set up, but it does have some drawbacks.

·         Finding a file ( or verifying one does not already exist upon creation ) requires a linear search.

·         Deletions can be done by moving all entries, flagging an entry as deleted, or by moving the last entry into the newly vacant position.

·         Sorting the list makes searches faster, at the expense of more complex insertions and deletions.

·         A linked list makes insertions and deletions into a sorted list easier, with overhead for the links.

·         More complex data structures, such as B-trees, could also be considered.

Hash Table

·         A hash table can also be used to speed up searches.

·         Hash tables are generally implemented in addition to a linear or other structure