title: Why are double-linked lists used in Dial's version of Dijkstra's algorithm?
body: <p>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. <a href="http://www.cs.ucsb.edu/~suri/cs231/ShortestPaths.pdf" rel="nofollow">http://www.cs.ucsb.edu/~suri/cs231/ShortestPaths.pdf</a>, <a href="http://www.acsu.buffalo.edu/~nagi/courses/684/4.shortestpath.pdf" rel="nofollow">http://www.acsu.buffalo.edu/~nagi/courses/684/4.shortestpath.pdf</a>). However, the operations required are only this (so far as I see):</p>
  
  <ol>
  <li><p>Checking if a bucket is empty</p></li>
  <li><p>Adding a node to a bucket (order doesn't matter)</p></li>
  <li><p>Iterating over a bucket while deleting passed nodes.</p></li>
  </ol>
  
  <p>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).</p>
  
  <p>So, is there a reason I am missing why a doubly-linked list is desirable instead?</p>