Back to home

- What is Doubly Linked List?
- Representation of Doubly Linked List
- Operations of Linked List
- Implementation
- Time & Space Complexity Analysis

Logicmojo - Updated Sept 18, 2021

After arrays, the second most popular data structure is Linked List. A linked list is a linear data structure, made of a chain of nodes in which each node contains a value and a pointer to the next node in the chain. In this article, letβs see how to implement a doubly linked list.

Doubly linked list is a type of linked list in which each node apart from storing its data has two links. The first link points to the previous node in the list and the second link points to the next node in the list. The first node of the list has its previous link pointing to NULL similarly the last node of the list has its next node pointing to NULL.

The two links help us to traverse the list in both backward and forward direction. But storing an extra link requires some extra space.

**Implementation of Doubly Linked List**

First we define the node.

struct node{

int data;// Data

node *prev; // A reference to the previous node

node *next; // A reference to the next node

};

Now that we have understood the structure of the DLL, let us compare it with SLL and see what advantages this has to offer over SLL.

1. A DLL can be traversed in both forward and backward direction.

2. We can easily insert a node before a given node.

But DLL also suffers from some **limitations** such as:

Every node of DLL requires extra space for a previous pointer.

**Why Linked List?**

Arrays can be used to store linear data of similar types, but arrays have the following limitations.

1. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.

2. Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted but in Linked list if we have the head node then we can traverse to any node through it and insert new node at the required position.

Advantages over arrays

1. Dynamic size

2. Ease of insertion/deletion

**Operations of Linked List**

Following are the basic operations that are done on any linked list:

β’ Insertion

β’ Deletion

**Insertion**

Pushing a node to a doubly-linked list is similar to pushing a node to a linked list, but extra work is required to handle the pointer to the previous node.

We can insert elements at 3 different positions of a doubly-linked list:

β’ Insertion at the beginning

β’ Insertion in-between nodes

β’ Insertion at the End

**Insertion at the beginning**

Let's add a node with value at the beginning of the doubly linked list we made above.

1. Create a new node

β’ allocate memory for newNode

β’ assign the data to newNode.

2. Set prev and next pointers of new node

β’ point next of newNode to the first node of the doubly linked list

β’ point prev to null

3. Make new node as head node

β’ Point prev of the first node to newNode (now the previous head is the second node)

β’ Point head to newNode

// insert node at the front void insertFront(struct Node** head, int data) { // allocate memory for newNode struct Node* newNode = new Node; // assign data to newNode newNode->data = data; // point next of newNode to the first node of the doubly linked list newNode->next = (*head); // point prev to NULL newNode->prev = NULL; // point previous of the first node (now first node is the second node) to newNode if ((*head) != NULL) (*head)->prev = newNode; // head points to newNode (*head) = newNode; }

** Insertion in between two nodes**

Let's add a node with value after node with value 1 in the doubly linked list.

1. Create a new node

β’ allocate memory for newNode

β’assign the data to newNode.

2. Set the next pointer of new node and previous node

β’ assign the value of next from previous node to the next of newNode

β’ assign the address of newNode to the next of previous node

3. Set the prev pointer of new node and the next node

β’ assign the value of prev of next node to the prev of newNode

β’ assign the address of newNode to the prev of next node

// insert a node after a specific node void insertAfter(struct Node* prev_node, int data) { // check if previous node is NULL if (prev_node == NULL) { cout << "previous node cannot be NULL"; return; } // allocate memory for newNode struct Node* newNode = new Node; // assign data to newNode newNode->data = data; // set next of newNode to next of prev node newNode->next = prev_node->next; // set next of prev node to newNode prev_node->next = newNode; // set prev of newNode to the previous node newNode->prev = prev_node; // set prev of newNode's next to newNode if (newNode->next != NULL) newNode->next->prev = newNode; }

**Insertion at the End**

Let's add a node with value 6 at the end of the doubly linked list

Create a new node

β’ Set prev and next pointers of new node and the previous node

If the linked list is empty, make the newNode as the head node. Otherwise, traverse to the end of the doubly linked list and

// insert a newNode at the end of the list void insertEnd(struct Node** head, int data) { // allocate memory for node struct Node* newNode = new Node; // assign data to newNode newNode->data = data; // assign NULL to next of newNode newNode->next = NULL; // store the head node temporarily (for later use) struct Node* temp = *head; // if the linked list is empty, make the newNode as head node if (*head == NULL) { newNode->prev = NULL; *head = newNode; return; } // if the linked list is not empty, traverse to the end of the linked list while (temp->next != NULL) temp = temp->next; // now, the last node of the linked list is temp // point the next of the last node (temp) to newNode. temp->next = newNode; // assign prev of newNode to temp newNode->prev = temp; }

**Deletion from a Doubly Linked List**

Similar to insertion, we can also delete a node from 3 different positions of a doubly linked list.

Suppose we have a double-linked list with elements 1, 2, and 3.

**Delete the First Node of Doubly Linked List**

β’ If the node to be deleted (i.e. del_node) is at the beginning

β’ Reset value node after the del_node (i.e. node two)

if (*head == del_node) *head = del_node->next; if (del_node->prev != NULL) del_node->prev->next = del_node->next; free(del);

**Delete the Last Node of Doubly Linked List**

In this case, we are deleting the last node with value 3 of the doubly linked list.

Here, we can simply delete the del_node and make the next of node before del_node point to NULL.

if (del_node->prev != NULL) del_node->prev->next = del_node->next;

**Doubly Linked List Code in Python, C++**

# Initialise the Node class Node: def __init__(self, data): self.item = data self.next = None self.prev = None # Class for doubly Linked List class doublyLinkedList: def __init__(self): self.start_node = None # Insert Element to Empty list def InsertToEmptyList(self, data): if self.start_node is None: new_node = Node(data) self.start_node = new_node else: print("The list is empty") # Insert element at the end def InsertToEnd(self, data): # Check if the list is empty if self.start_node is None: new_node = Node(data) self.start_node = new_node return n = self.start_node # Iterate till the next reaches NULL while n.next is not None: n = n.next new_node = Node(data) n.next = new_node new_node.prev = n # Delete the elements from the start def DeleteAtStart(self): if self.start_node is None: print("The Linked list is empty, no element to delete") return if self.start_node.next is None: self.start_node = None return self.start_node = self.start_node.next self.start_prev = None; # Delete the elements from the end def delete_at_end(self): # Check if the List is empty if self.start_node is None: print("The Linked list is empty, no element to delete") return if self.start_node.next is None: self.start_node = None return n = self.start_node while n.next is not None: n = n.next n.prev.next = None # Traversing and Displaying each element of the list def Display(self): if self.start_node is None: print("The list is empty") return else: n = self.start_node while n is not None: print("Element is: ", n.item) n = n.next print("\n") # Create a new Doubly Linked List NewDoublyLinkedList = doublyLinkedList() # Insert the element to empty list NewDoublyLinkedList.InsertToEmptyList(10) # Insert the element at the end NewDoublyLinkedList.InsertToEnd(20) NewDoublyLinkedList.InsertToEnd(30) NewDoublyLinkedList.InsertToEnd(40) NewDoublyLinkedList.InsertToEnd(50) NewDoublyLinkedList.InsertToEnd(60) # Display Data NewDoublyLinkedList.Display() # Delete elements from start NewDoublyLinkedList.DeleteAtStart() # Delete elements from end NewDoublyLinkedList.DeleteAtStart() # Display Data NewDoublyLinkedList.Display()

**Implementation in C++**

#include <iostream> using namespace std; // node creation struct Node { int data; struct Node* next; struct Node* prev; }; // insert node at the front void insertFront(struct Node** head, int data) { // allocate memory for newNode struct Node* newNode = new Node; // assign data to newNode newNode->data = data; // make newNode as a head newNode->next = (*head); // assign null to prev newNode->prev = NULL; // previous of head (now head is the second node) is newNode if ((*head) != NULL) (*head)->prev = newNode; // head points to newNode (*head) = newNode; } // insert a node after a specific node void insertAfter(struct Node* prev_node, int data) { // check if previous node is null if (prev_node == NULL) { cout << "previous node cannot be null"; return; } // allocate memory for newNode struct Node* newNode = new Node; // assign data to newNode newNode->data = data; // set next of newNode to next of prev node newNode->next = prev_node->next; // set next of prev node to newNode prev_node->next = newNode; // set prev of newNode to the previous node newNode->prev = prev_node; // set prev of newNode's next to newNode if (newNode->next != NULL) newNode->next->prev = newNode; } // insert a newNode at the end of the list void insertEnd(struct Node** head, int data) { // allocate memory for node struct Node* newNode = new Node; // assign data to newNode newNode->data = data; // assign null to next of newNode newNode->next = NULL; // store the head node temporarily (for later use) struct Node* temp = *head; // if the linked list is empty, make the newNode as head node if (*head == NULL) { newNode->prev = NULL; *head = newNode; return; } // if the linked list is not empty, traverse to the end of the linked list while (temp->next != NULL) temp = temp->next; // now, the last node of the linked list is temp // assign next of the last node (temp) to newNode temp->next = newNode; // assign prev of newNode to temp newNode->prev = temp; } // delete a node from the doubly linked list void deleteNode(struct Node** head, struct Node* del_node) { // if head or del is null, deletion is not possible if (*head == NULL || del_node == NULL) return; // if del_node is the head node, point the head pointer to the next of del_node if (*head == del_node) *head = del_node->next; // if del_node is not at the last node, point the prev of node next to del_node to the previous of del_node if (del_node->next != NULL) del_node->next->prev = del_node->prev; // if del_node is not the first node, point the next of the previous node to the next node of del_node if (del_node->prev != NULL) del_node->prev->next = del_node->next; // free the memory of del_node free(del_node); } // print the doubly linked list void displayList(struct Node* node) { struct Node* last; while (node != NULL) { cout << node->data << "->"; last = node; node = node->next; } if (node == NULL) cout << "NULL\n"; } int main() { // initialize an empty node struct Node* head = NULL; insertEnd(&head, 5); insertFront(&head, 1); insertFront(&head, 6); insertEnd(&head, 9); // insert 11 after head insertAfter(head, 11); // insert 15 after the seond node insertAfter(head->next, 15); displayList(head); // delete the last node deleteNode(&head, head->next->next->next->next->next); displayList(head); }

Doubly Linked List Time complexity | Time complexity | Space complexity |
---|---|---|

Insert Operation | O(1) | O(1) |

Deletion | O(1) | O(1) |

**Doubly Linked List Applications**

1. Redo and undo functionality in software.

2. Forward and backward navigation in browsers.

3. For navigation systems where forward and backward navigation is required

With this article at Logicmojo, you must have the complete idea of analyzing Doubly Linked List and it's operations.

**Good Luck & Happy Learning!!**