answersLogoWhite

0

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.

User Avatar

Wiki User

12y ago

What else can I help you with?

Related Questions

Convert single linked list to double linked list?

You copy a singly linked list into a doubly linked list by iterating over the singly linked list and, for each element, calling the doubly linked list insert function.


what are the differences between singly link list and doubly link list?

singly linked list stores only the address of next node while doubly linked list stores the address of previous node and next node and hence it is called doubly linked list. In singly linked list only forward traversing is possible while in doubly linked list forward and backward traversal is possible.


Does each node in a doubly linked list contain a link to the previous as well as the next node?

Yes, each node in a doubly linked list contain a link to the previous as well as the next node. That is the definition of the doubly linked list.


What is the difference between doubly linked list and circular linked list?

A doubly linked list is a linked list in which each node knows where both of its neighbors are.A circular linked list is a linked list in which the "tail" of the list is linked to the "root". (Note that both the tail and root of the list are undefined/arbitrary in a circular linked list)Doubly linked lists are actually not necessarily related to circular linked list (aside from both being based on a linked list structure). In fact, you can have a circular doubly linked list, where each node knows where both of its neighbors are andwhere the list wraps around to connect to itself.


How can a binary tree be converted into a doubly linked list?

To convert a binary tree into a doubly linked list, perform an in-order traversal of the tree and adjust the pointers to create the doubly linked list. This involves setting the left child pointer to the previous node and the right child pointer to the next node in the list.


Which operation is perform more efficiently by doubly linked list than by single linked list?

zsd


Write a algorithm for doubly linked list in c?

sorry


What is the time complexity of operations in a doubly linked list?

The time complexity of operations in a doubly linked list is O(1) for insertion and deletion at the beginning or end of the list, and O(n) for insertion and deletion in the middle of the list.


How can you efficiently sort a doubly linked list?

To efficiently sort a doubly linked list, you can use a sorting algorithm such as merge sort or quicksort. These algorithms can be implemented to work with doubly linked lists by considering the pointers in both directions. By recursively dividing the list and merging or partitioning the elements, you can achieve an efficient sorting process.


What is difference between linked list and singly linked list?

Answersingly linked list has the node inserted only at one end. and the pointer corresponds to the next pointer.but in a doubly linked list, the node pointer points to the both previous and the next node.singly linked list has two nodesdoubly linked list has three nodesA doubly linked list makes sense when you need to traverse the list in both directions. You aren't able to do that with a singly linked list.


What is meant by doubly linked list?

In C programming, a double linked-list refers to a linked data structure that contains a set of links that have been linked sequentially.


Traversing in Doubly Linked List is faster then Singly Linked List?

Traversing a doubly linked list is generally faster than traversing a singly linked list, but the speedup depends on how you do the traversal:Traversing from first to last node: No difference.Random access: Doubly linked list is faster, the difference is a fixed factor. (Like twice as fast. Which makes it still very slow for random access compared to arrays.)Reverse order: Doubly linked list is just as fast traversing "backwards" as "forwards", while a singly linked list traversing in reverse order needs to traverse the entire list once for every element in the list - it is a LOT slower. (Time complexity O(n) for doubly linked list, O(n*n) for singly linked, if you are familiar with the notation.)If you are talking about the computer science "big O notation", doubly linked and singly liked lists are the same. This is because the Big O notation ignores fixed factors and only looks at how time increases with the length of the list, and in this respect the two are the same. (Except for the special case of traversing the list in reverse order. Even here a singly linked list could do it in O(n) time - same as a doubly linked list - by reversing the list (O(n)) before traversing it (O(n)) for a total time of 2*O(n), which by the rules of Big O is the same as O(n).)