Yukti Kumari
Last Updated: Mar 10, 2023
EASY

## Introduction

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.

There are three types of linked lists:

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

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

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.

• 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.

• It consumes extra memory space compared to a singly linked list due to the additional previous pointer it has to maintain for each element.

• 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.

### What are the different types of a linked lists?

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.