What is are the drawback S of singly linked list over doubly linked list?

There are many data structures like arrays, linked lists, etc. Each sort of arrangement has its strengths and weaknesses. For these reasons, it’s important to know the benefits and drawbacks of different data structures when it comes to designing, optimizing, and scaling programs. In this article, we will discuss the advantages and disadvantages of the linked list.

Linked List:

A Linked list is a dynamic arrangement that contains a “link” to the structure containing the subsequent items. It’s a set of structures ordered not by their physical placement in memory (like an array) but by logical links that are stored as a part of the info within the structure itself.

A linked list is another way to collect similar data. However, unlike an array, elements during a linked list aren’t in consecutive memory locations. A linked list consists of nodes that are connected with one another using pointers. The figure illustrates a linked list.

Types Of Linked List:

• Singly Linked List: It is the simplest type of linked list in which every node contains some data and a pointer to the next node of the same data type. The node contains a pointer to the next node means that the node stores the address of the next node in the sequence. A single linked list allows the traversal of data only in one way.
• Doubly or Two Way Linked List: A doubly linked list or a two-way linked list is a more complex type of linked list that contains a pointer to the next as well as the previous node in sequence, Therefore, it contains three parts are data, a pointer to the next node, and a pointer to the previous node. This would enable us to traverse the list in the backward direction as well.
• Circular Linked List: A circular linked list is that in which the last node contains the pointer to the first node of the list. While traversing a circular liked list, one can begin at any node and traverse the list in any direction forward and backward until reaching the same node where started. Thus, a circular linked list has no beginning and no end.
• Circular Doubly Linked List: A Doubly Circular linked list or a circular two-way linked list is a more complex type of linked-list that contains a pointer to the next as well as the previous node in the sequence. The difference between the doubly linked and circular doubly list is the same as that between a singly linked list and a circular linked list. The circular doubly linked list does not contain null in the previous field of the first node.

Advantages Of Linked List:

• Dynamic data structure: A linked list is a dynamic arrangement so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give the initial size of the linked list.
• No memory wastage: In the Linked list, efficient memory utilization can be achieved since the size of the linked list increase or decrease at run time so there is no memory wastage and there is no need to pre-allocate the memory.
• Implementation: Linear data structures like stack and queues are often easily implemented using a linked list.
• Insertion and Deletion Operations: Insertion and deletion operations are quite easier in the linked list. There is no need to shift elements after the insertion or deletion of an element only the address present in the next pointer needs to be updated.

Disadvantages Of Linked List:

• Memory usage: More memory is required in the linked list as compared to an array. Because in a linked list, a pointer is also required to store the address of the next element and it requires extra memory for itself.
• Traversal: In a Linked list traversal is more time-consuming as compared to an array. Direct access to an element is not possible in a linked list as in an array by index. For example, for accessing a node at position n, one has to traverse all the nodes before it.
• Reverse Traversing: In a singly linked list reverse traversing is not possible, but in the case of a doubly-linked list, it can be possible as it contains a pointer to the previously connected nodes with each node. For performing this extra memory is required for the back pointer hence, there is a wastage of memory.
• Random Access: Random access is not possible in a linked list due to its dynamic memory allocation.

A Doubly Linked List(DLL) is a linear data structure that contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in a singly linked list. Below is the image to illustrate the same.

Advantages Of DLL:

• Reversing the doubly linked list is very easy.
• It can allocate or reallocate memory easily during its execution.
• As with a singly linked list, it is the easiest data structure to implement.
• The traversal of this doubly linked list is bidirectional which is not possible in a singly linked list.
• Deletion of nodes is easy as compared to a Singly Linked List. A singly linked list deletion requires a pointer to the node and previous node to be deleted but in the doubly linked list, it only required the pointer which is to be deleted.

Disadvantages Of DLL:

• It uses extra memory when compared to the array and singly linked list.
• Since elements in memory are stored randomly, therefore the elements are accessed sequentially no direct access is allowed.

Uses Of DLL:

• It is used in the navigation systems where front and back navigation is required.
• It is used by the browser to implement backward and forward navigation of visited web pages that is a back and forward button.
• It is also used to represent a classic game deck of cards.
• It is also used by various applications to implement undo and redo functionality.
• Doubly Linked List is also used in constructing MRU/LRU (Most/least recently used) cache.
• Other data structures like stacks, Hash Tables, Binary trees can also be constructed or programmed using a doubly-linked list.
• Also in many operating systems, the thread scheduler(the thing that chooses what process needs to run at which time) maintains a doubly-linked list of all processes running at that time.