Question

Does a computer have to scan all elements before i if I am trying to add an element at the ith position (where i can be any position) when using a doubly linked list or only a singly linked list? Or am I saying complete nonsense?

Any input would be appreciated!
Thanks in advance!

Answer 1

Actually having rethought what I said, it sounds stupid.

Instead, is the only advantage of the doubly linked list that it can scan both ways rather than just one way (when attempting to add or remove an ith element)?

Answer 2

So for example, it would be smart to scan from the direction with less objects to scan through if one knows the size of the entire LinkedList, right? However, this does not mean that it doesn't have to scan through because it still does, right? (If everything I said is correct after correcting myself as well, a confirmation would mean a lot).

Answer 3

If you're starting at a certain node in the list, and know the index of that node, yes - you could figure out whether to traverse forward or backward and save some time. This really only should make a difference if you have an extremely large list, or are needing to traverse it an extremely large number of times (or extremely quickly ;).
If you need to do that and it becomes a time critical piece of your code, you may be better off using an array, if insertion isn't a major factor (doesn't happen often compared to iterating through). Iterating linked lists has other problems than just the pure iteration, such as normally not being cache-coherent, which can be a huge problem on today's processors.

Answer 4

I once used a doubly-linked list of disk blocks to store the queue of messages to be processed. And the extra link (extra because you only need to access a block address queue from the head end) was used to patch up the queue if a disk block went bad, breaking the forward link. Block addresses of the head and tail messages were kept in memory. If we got a disk error reading a block, moving forward down the list, we would read the last block and trace backwards until we got another error. Then we'd patch the two blocks together, discarding some number of queued messages but keeping the queue correct.

The tail block address also allowed me to append a new message quickly to the tail of the queue without searching to find the tail, starting at the head of the list.

I believe that the end-of-list marker was an all-zero address, just like you often do with an in-memory linked-list.

Answer 5

Thanks guys!