Linear List

• The simplest method of implementing a directory is to use a linear list of file names with pointers to the data blocks.
• This method is simple to program but time-consuming to execute.
  • To create a new file, we must first search the directory to be sure that no existing file has the same name. Then, we add a new entry at the end of the directory.
  • To delete a file, we search the directory for the named file, then release the space allocated to it.
• The real disadvantage of a linear list of directory entries is that finding a file requires a linear search.
• Directory information is used frequently, and users will notice if access to it is slow. In fact, many OSs implement a software cache to store the most recently used directory information.
• A sorted list allows a binary search and decreases the average search time. However, the requirement that the list be kept sorted may complicate creating and deleting files, since we may have to move substantial amounts of directory information to maintain a sorted directory.