Why we use doubly linked list instead of singly linked list?

Insertion is clearly less work in a singly-linked list, as long as you are content to always insert at the head or after some known element. [That is, you cannot insert before a known element, but see below.]

Deletion, on the other hand, is trickier because you need to know the element before the element to be deleted.

One way of doing this is to make the delete API work with the predecessor of the element to be deleted. This mirrors the insert API, which takes the element which will be the predecessor of the new element, but it's not very convenient and it's hard to document. It's usually possible, though. Generally speaking, you arrive at an element in a list by traversing the list.

Of course, you could just search the list from the beginning to find the element to be deleted, so that you know what its predecessor was. That assumes that the delete API includes the head of the list, which is also inconvenient. Also, the search is stupidly slow.

The way that hardly anyone uses, but which is actually pretty effective, is to define a singly-linked list iterator to be the pointer to the element preceding the current target of the iterator. This is simple, only one indirection slower than using a pointer directly to the element, and makes both insertion and deletion fast. The downside is that deleting an element may invalidate other iterators to list elements, which is annoying. [It doesn't invalidate the iterator to the element being deleted, which is nice for traversals which delete some elements, but that's not much compensation.]

If deletion is not important, perhaps because the datastructures are immutable, singly-linked lists offer another really useful property: they allow structure-sharing. A singly-linked list can happily be the tail of multiple heads, something which is impossible for a doubly-linked list. For this reason, singly-linked lists have traditionally been the simple datastructure of choice for functional languages.

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!

Difference Between Doubly linked list vs Singly linked list

• The singly linked list and doubly linked list is a type of linked list to arrange memory and information.
• The singly linked list and doubly linked list is part of dynamic data structure to avoid memory wastage and traverse using element in the list.
• The doubly linked list is a function that contains data, next node, and previous node simultaneously.
• The singly linked list is a function that contains data and the next node only.
• The singly linked list is a simple linked list to traverse one way from the first node to the next node.
• The doubly linked list is a complex linked list to traverse both ways from one node to another and vice versa.
• The singly linked list contains two parts, such as memory and pointer, but the last pointer becomes null.
• The doubly linked list contains three parts such as a previous pointer, memory node, and next pointer but the initial and last pointer becomes null.

Head to Head Comparison Between Doubly linked list vs Singly linked list [Infographics]

Below are the top differences between Doubly linked list vs Singly linked list

Key differences between Doubly linked list vs Singly linked list

Some of the key differences between Doubly linked list vs Singly linked list are given below:

• The doubly linked list is bidirectional because of two address pointer. Therefore, a singly linked list is unidirectional because of the one address pointer.
• The doubly linked list has occurred more memory space than the singly linked list.
• The singly linked list simple, whereas the doubly linked list, is a complex dynamic data structure of the list.
• The doubly linked list provides an empty head and tail pointer. Hence, a singly linked list provides an empty tail only.
• The doubly linked list more efficient than the singly list.
• The doubly linked list contains three parameters, and the singly linked list contains two parameters.
• The singly linked list image is given below.

• The doubly linked list image is given below.

• The doubly linked list gives time complexity O[1], whereas the singly linked list gives time complexity O[n].

Comparison table

• The doubly linked list is a complex function, and the singly linked list is a simple data structure.
• The comparison table is displayed features and descriptions of the singly linked list and doubly linked list.
• The below table is showing similarities and differences of the type of the linked list.

Conclusion

• The singly linked list and doubly linked list make the application usable, handy, and manageable.
• The singly linked list and doubly linked list helps to manage and operate a list of data.

Recommended Articles

This is a guide to the Doubly linked list vs Singly linked list. Here we discuss the Doubly linked list vs Singly linked list key differences with infographics and comparison table. You may also have a look at the following articles to learn more –

1. Snapseed vs Lightroom
2. Krita vs Photoshop
3. Lumion vs V-Ray
4. Lubuntu vs Xubuntu