When is a doubly linked list appropriate?

Answer 1

Whenever you need constant time access to both the head and tail of the list and require bi-directional traversal of the list from any given node (not necessarily the head or tail).

With a singly linked list, the only way to perform a reverse traversal is through a recursive call. For instance, the following C function will print singly linked nodes in reverse order (the caller simply passes the head node to the function):

void print_reverse(node* current)

{

if( current )

{

print_reverse( current->next);

current->print(); }

}

While this works, for long lists there's a risk you might run out of stack space. This is because the head node (in the initial call) cannot print itself until the recursive call to the next node has returned, which it can't do until its recursive call returns, and so on until the recursion reaches the tail node. Only then will the recursions begin to unwind and the nodes can actually print themselves. Even if stack space isn't an issue, it's inefficient because you are effectively traversing the list twice; forwards to get to the tail and then backwards to do the actual printing.

With a doubly-linked list you simply traverse the list from the tail node to the head node in order to print them in reverse order:

void print_reverse(list& List)

{

node* current = List.tail;

while( 0 != current )

{

current->print();

current = current->prev; }

}

While not quite as concise as a recursive call, it is a good deal more efficient.

The other advantage is that should you have a reference to any node (whether the head, the tail or anything in between), you have the option to traverse forwards or backwards as you see fit. With a singly linked list you can only go forwards from a given node unless you used recursion to get to that node in the first place.

Answer 2

You use a doubly-linked list when you require bidirectional traversal of a list.