Insertion in Doubly Linked List in C++

In a doubly linked list, there are three ways in which the insertion operation can be performed:

• Insertion at the beginning of DLL
• Insertion at the end of DLL
• Insertion at Specific Position in DLL

a. Insertion at the Beginning in Doubly Linked List

First, create a new node to be inserted and then follow the below approach to insert a new node at the beginning of a doubly linked list:

Approach:

• First, create a newNode
• If the list is empty:
  • set newNode->next to NULL.
  • set newNode->prev to NULL.
  • point the head pointer to newNode.
• If the list is not empty:
  • set newNode->next to head.
  • set newNode->prev to NULL.
  • set head->prev to newNode.
  • point the head pointer to newNode.

b. Insertion at the End in Doubly Linked List

First, create a new node to be inserted and then follow the below approach to insert a new node at the end of a doubly linked list:

Approach:

• First, create a newNode.
• If the list is empty:
  • set newNode->next to NULL.
  • set newNode->prev to NULL.
  • point the head pointer to newNode.
• If the list is not empty:
  • find the last node by iterating the list (i.e. where last->next == NULL).
  • set last->next to newNode.
  • set newNode->prev to last.
  • set newNode->next to NULL.

c. Insertion at Specific Position in Doubly Linked List

First, create a new node to be inserted and then follow the below approach to insert a new node at a given position in a doubly linked list:

Approach:

• First, create a newNode.
• Check whether the given position is valid or not by finding the size of the list.
• If the given position is 0 (or 1 depending on indexing):
  • we can use the insertion at the beginning approach only.
• If the given position is the last i.e. it is equal to the size of the list:
  • we can use the insertion at the end approach here.
• If the given position is valid then do the following:
  • start traversing the list to find the node that comes immediately before the given position (call it prevNode).
  • set newNode->next to prevNode->next.
  • set newNode->prev to prevNode.
  • if prevNode->next is not NULL, set prevNode->next->prev to newNode.
  • set prevNode->next to newNode.

A Doubly Linked List (DLL) is a two-way list in which each node has two pointers, the next and previous that have reference to both the next node and previous node respectively. Unlike a singly linked list where each node only points to the next node, a doubly linked list has an extra previous pointer that allows traversal in both the forward and backward directions.

In this article, we will learn about the doubly linked list representation, implementation of doubly linked list in C++, basic operations that can be performed on doubly linked list, its advantages and disadvantages.