Advantages, Disadvantages And Uses Of a Doubly Linked List

Introduction

A Linked List is a linear data structure where each element has a pointer pointing to the next, forming a sequence of elements. Unlike an array, elements in the linked list are not stored in contiguous memory locations; instead, they are stored at random locations connected through pointers.

In this article, we will explore the types of linked lists and the advantages, disadvantages, and uses of doubly-linked lists.

Types of Linked Lists

There are three types of linked lists:

• Singly Linked Lists
• Doubly linked lists
• Circular Linked Lists

Singly Linked List

A singly linked list is the most generic linked list. Each element has only one pointer that points to the next element in the sequence of the linked list. Therefore it is traversed in a unidirectional way. 

Each element contains two fields:

• Data
• Next Pointer

Doubly Linked List

It is a complex Linked List where each element has two pointers: "next pointer” and “previous pointer”. The “next pointer” points to the next element in the sequence, whereas the “previous pointer” points to the previous element in the sequence. Therefore we can traverse a doubly linked list in both forward and backward directions.

Each element contains three fields:

• Previous Pointer
• Data
• Next Pointer

Circular Linked List

It is a doubly linked list where the first and last elements are also connected, forming a complete circle. The “next pointer “ of the last element points to the beginning of the linked list, and the “previous pointer” of the first element points to the last element of the linked list.

Each element contains three fields:

• Previous Pointer
• Data
• Next Pointer

In a singly-linked list, each element contains two pieces of information: data and a pointer to the next element. But in the doubly linked list, each element includes extra information called the previous pointer. The previous pointer points to the previous element corresponding to each element in the linked list.

Advantages of Doubly Linked List

The following are the advantages of Doubly Linked List:

• It allows traversing in both forward and backward directions because of the next and previous pointers, unlike the singly linked list, which allows traversing in only one direction.
   
• Deletion of elements is more straightforward compared to a singly linked list. This is because to delete an element, we need access to the element to be deleted and the element previous to it. So, we require two pointers for deletion in a singly linked list. In contrast, in a doubly-linked list, there is no need to maintain an extra pointer as each element carries the information of the previous element.
   
• Reversing a doubly linked list is also easy. We only need to swap each element’s next and previous pointers and update the head element to point to the last element to reverse a doubly-linked list. 
   
• We can easily insert a  new element before a given element because we have information for both previous and next element so we can update it accordingly.
   
• It is very easy to implement.

Disadvantages of Doubly Linked List

The following are the disadvantages of Doubly Linked List:

• It consumes extra memory space compared to a singly linked list due to the additional previous pointer it has to maintain for each element.
  Note: This disadvantage can be overcome using XOR-linked lists.
   
• It is impossible to access the list’s elements directly because they are stored at random locations, and we can only access them sequentially.
   
• All the operations require more time due to the overhead of handling extra pointers. For instance, if you have to insert a new element, you must modify the previous pointers and the next pointers, similarly in the case of deletion.

Uses of Doubly Linked List

In this section, we will see some of the practical applications of the doubly linked list.

• It is used in web browsers to implement the backward and forward navigation of web pages through the back and forward buttons.
   
• Various applications implement the Undo and Redo functionality using a doubly-linked list.
   
• Doubly linked lists are used in constructing the Most recently used(MRU) or Least Recently Used(LRU) cache.
   
• It is used in games. For example, to represent the classical deck of cards.
   
• Various data structures can be implemented, like stacks, hash tables, binary trees etc.
   
• The thread scheduler uses them in the operating system to maintain a list of all the running processes.

Frequently Asked Questions

What are the different types of a linked lists?

There are three types of linked lists: Singly-linked list, Doubly-linked list and Circular linked list.

What are the advantages of a linked list?

The advantages of a linked list include that it is dynamic in nature, the deletion and insertion are very fast and the memory is utilised efficiently in linked lists because we don’t need to declare size in advance.

What is a doubly-linked list?

A doubly linked list is one of the types of linked lists in which each element consists of data and pointers to the previous and the next elements.

Can a doubly linked list be circular?

Yes, a doubly-linked list in which the last element and the head element are adjacent is said to be a circular doubly-linked list.

Why doubly linked list is better than singly linked list ?

Doubly linked list contains two pointers namely “next” and “previous” due to which accessing elements in a doubly linked list is easy compared to singly linked list as both forward and backward traversal is possible.

Conclusion

This article taught us the advantages and disadvantages of a doubly linked list. We also got to know about the uses of double-linked lists.  

To study more about Linked Lists, refer to Applications Of Linked Lists.

To learn more about implementing several operations in a doubly-linked list, you must check out Introduction and Implementation of Doubly Linked Lists.

Some of the problems are based on linked lists which you can solve - 

• Difference Between Array List and Linked List
• Reverse DLL elements in groups
• Reverse Linked List
• Merge Two Sorted Linked Lists
• Cycle Detection in a Singly Linked List

Are you planning to ace the interviews with reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on CodeStudio now!