Microsoft Asks: Singly List or Doubly List? What are the pros and cons of using each?

Question

I am asked such question and I have my own sayings but I am not really sure what to say about cons and pros? Microsoft asked this question to one of its candidates.

Singly linked list allows you to go one way direction. Whereas doubly linked list has two way direction next and previous.

Here is a good picture which draws the Singly and Doubly LinkedLists.

However, how do you explain the pros and cons of these items in more orderly fashion?

Answer 1

Although this question has already been answered, I am somehow not satisfied with the answer (no offense meant), so here's how I would reply to it:

What to use - Singly or Doubly linked list depends on what you intend to achieve and system limitations, if any.

Singly-linked list:

Pros: Simple in implementation, requires relatively lesser memory for storage, assuming you need to delete/insert (at) next node – deletion/insertion is faster.

Cons: Cannot be iterated in reverse, need to maintain a handle to the head node of the list else, the list will be lost in memory. If you’re deleting previous node or inserting at previous node, you will need to traverse list from head to previous node to be able to carry out those operations – O(N) time.

--So, this should be used when you have lesser memory and your main goal is insertion/deletion and not searching elements.

Doubly-linked list:

Pros: Can be iterated in forward as well as reverse direction. In case of needing to delete previous node, there is no need to traverse from head node, as the node to be deleted can be found from ‘.previous’ pointer.

Cons: Relatively complex to implement, requires more memory for storage (1 ‘.previous’ pointer per node). Insertions and deletions are relatively more time consuming (assigning/reassigning ‘.previous’ pointer for neighbor nodes)

--This should be used when you have no or minimal limitations on memory, and your main goal is to search for elements.

If there are some more pros and cons to any, please feel free to add, reply in comments. Thanks!

Answer 2

I am asked such question and I have my own sayings but I am not really sure what to say about cons and pros?

It all comes down to usage. There's a trade off here.

Singly linked list is simpler in terms of implementation, and typically has a smaller memory requirement as it only needs to keep the forward member referencing in place.

Doubly linked list has more efficient iteration, especially if you need to ever iterate in reverse (which is horribly inefficient with a single linked list), and more efficient deletion of specific nodes.

That being said - since you have this tagged .NET, double linked lists also have the advantage of being directly in the framework in the form of the LinkedList<T> class. This provides a huge advantage in that you don't have to implement, test, and maintain your own collection class.

Answer 3

While singly linked list uses less memory per node (one pointer vs. two pointers), its deletion operation is O(N) if all you have is a pointer to the node you want deleted, while doubly-linked deletion is O(1). There is a little-known trick that lets you delete from a singly-linked list in O(1), but the list must be circular for it to work (move the content of next into the current, and delete next).

Doubly-linked lists can be used in places where singly-linked lists would not work (a doubly-ended queue), but they require slightly more "housekeeping", and are slightly less efficient on insertions as the result.

Answer 4

Advantage of double linked list: Can traverse in both directions

Advantage of single linked list: Less housework to be done on update/insert/delete, less memory usage.