A simple doubt which striked me while reading OS

This is a discussion on A simple doubt which striked me while reading OS within the C Programming forums, part of the General Programming Boards category; Hello, while i was reading Operating System Concepts by Abraham Silberchatz i was confused because in file systems chapter in ...

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    225

    A simple doubt which striked me while reading OS

    Hello,
    while i was reading Operating System Concepts by Abraham Silberchatz i was confused because in file systems chapter in directory implementation it was written that the simplest method of implementing directory is to use a linear list, however its real disadvantage is that finding a file requires a linear search. Then it's written that a binary search can also be done on list if it's kept in sorted order.
    I am confused as to can we do a binary search on linked list??is it possible? i mean in array we can directly access the element at specified location but in linked list there is no such provision.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You are confusing a LINEAR LIST with a LINKED LIST. You can't, as you say, use binary search on a linked list. A linear list is the same as a vector or array, and you most certainly can use a binary search in a linear list.

    There are also implementations that use Binary Search Trees.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    People like him are how we ended up with FAT16.

  4. #4
    Hacker MeTh0Dz's Avatar
    Join Date
    Oct 2008
    Posts
    111
    Quote Originally Posted by master5001 View Post
    People like him are how we ended up with FAT16.
    This quote is awesome.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 02-02-2009, 07:27 AM
  2. simple file reading
    By l2u in forum C++ Programming
    Replies: 10
    Last Post: 06-09-2008, 08:10 AM
  3. Replies: 2
    Last Post: 01-28-2008, 03:07 AM
  4. Reading game port with a simple compiler like BuilderX?
    By MaxxMan-X in forum Game Programming
    Replies: 7
    Last Post: 02-27-2005, 11:15 AM
  5. a simple OS
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 06-06-2004, 11:47 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21