Why are double-linked lists used in Dial's version of Dijkstra's algorithm?

Question

Several papers and slide decks I've seen mention Dial's implementation of Dijkstra's single-source shortest path algorithm. They all say that a bucket is stored as a doubly-linked list. (e.g. http://www.cs.ucsb.edu/~suri/cs231/ShortestPaths.pdf, http://www.acsu.buffalo.edu/~nagi/courses/684/4.shortestpath.pdf). However, the operations required are only this (so far as I see):

1. Checking if a bucket is empty

2. Adding a node to a bucket (order doesn't matter)

3. Iterating over a bucket while deleting passed nodes.

All of them can be done with a singly-linked list as easily (for 2, just change the pointer to the beginning of the list to the new node, and change its next pointer to the old first node in the bucket).

So, is there a reason I am missing why a doubly-linked list is desirable instead?

Answer 1

I figured it out. The operation I've missed is that while we are iterating over a bucket, we need to move the neighboring vertices, and so to delete their nodes from other buckets. This can be done in O(1) for doubly-linked lists and O(size of bucket) for singly-linked lists.