Introduction to Doubly Linked List 

 

Introduction

In the previous articles we have studied about Singly Linked List and various operations on it.

In this article , we are going to understand the new concept in the data structure called Doubly Linked List .
In the next few articles, we will study the various operations on Doubly Linked List.

What is Doubly Linked List ?

Doubly Linked List ( DLL ) is a type of linked list in which every node has three fields : one data field and two address fields.
A node of a doubly linked list can be graphically represented as shown below ,

The data field is used to store the data element. One address field is used to store the memory address of the next node while another address field is used to store the memory address of previous node.

A typical doubly linked list ( DLL ) can be graphically represented as below, 

Doubly Linked list ,dll
 
As each node has address of next and previous node, the traversal is possible in both forward and backward direction.

The previous address field of first node is NULL.
Also, the next address field of last node is NULL.

Operations on Doubly Linked List

  1. Create and display the doubly linked list.
  2.  Insertion in doubly linked list.
  3. Deletion in doubly linked list.

Advantages of Doubly Linked List

  1. Traversal in both forward and backward direction is possible.
  2. Insertion and deletion in doubly linked list is relatively easy than singly linked list. Unlike singly linked list , we do not need to maintain two pointers to insert or delete. Each node in DLL has address of next as well as previous node , so operations become easy . 

Disadvantages of Doubly Linked List

  1. As doubly linked list has one extra address field, its implementation requires more  memory.
  2. For any operation , we need to modify previous pointer along with next pointer.