1
$\begingroup$

I'm reading here that linked allocation uses a linked list, where each block has a pointer to the next block. For sequential access, this would take moving through the blocks one by one. Would it not better to use a doubly linked list so that this time could be cut in half?

Algorithmic analysis

I understand that sequential access remains ( O(n) ) worst case time for both singly linked list and doubly linked list. But non-asymptotically the time spent does become half.

$\endgroup$
2
  • 3
    $\begingroup$ "But non-asymptotically the time spent does become half." - why? $\endgroup$
    – user114966
    Commented Jan 26, 2021 at 18:42
  • $\begingroup$ Oh wait. Yea I was thinking it must take $n/2$ nodes to get to the target node at worst but no. Since the location is not known, that's not true. $\endgroup$ Commented Jan 27, 2021 at 4:40

2 Answers 2

3
$\begingroup$

Singly and doubly linked lists have the identical (terrible) linear access time. Using doubly linked lists would not help performance. The only benefit you'd get is that reading file backwards is more efficient.

No modern file system uses linked allocation anymore. Most use ranges of consecutive blocks, so called extents. Extents are usually more space-efficient and support random access. Neither Singly or doubly linked lists support random access. In practice these days the metadata for a file is read in at once (with all its extents), this is fast. Reading all nodes of the linked lists would mean reading several blocks, one after the other. This is slow, obviously.

$\endgroup$
1
$\begingroup$

The solution that is usually used is not to use a linked list. Most common is that the OS tries to allocate as many sequential blocks as possible, and record ranges of consecutive blocks. Often only one range is used.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.