Doubly Linked List – Introduction and Insertion

Last Updated on June 15, 2022 by Ria Pathak

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

A doubly linked list is a list that contains links to the next and previous nodes. We know that in a singly linked list, we can only traverse forward. But, in a doubly linked list, we can traverse both in a forward and backward manner.

Doubly Linked List Representation

Advantages over singly linked list

• A doubly linked list can be traversed both in the forward and backward directions.
• If the pointer to the node to be deleted is given, then the delete operation in a doubly-linked list is more efficient.
• Insertion of a new node before a given node is more efficient.

Disadvantages over singly linked list

• Extra space is required to store the previous pointer.
• All operations of a doubly-linked list require an extra previous pointer to be maintained. We have to modify the previous pointers together with the next pointer.

Insertion in a doubly-linked list

Insert at the beginning.

In this approach, the new node is always added at the start of the given doubly linked list, and the newly added node becomes the new head.

Approach

The approach is going to be very simple. We’ll make the next of the new node point to the head. Then, we will make the previous pointer of head point to the new node. Lastly, we will make the new node the new head.

Algorithm

• Allocate the new node and put in the data
• Make the next of the new node as head and previous as NULL.
• If the head is not pointing to NULL, then change the previous pointer of the head node to the new node.
• Make the new node the new head.

Dry Run

Code Implementation

void push(struct Node** head_ref, int new_data)
{
    struct Node* NewNode = (struct Node*)malloc(sizeof(struct Node));

    NewNode->data = new_data;

    NewNode->next = (*head_ref);
    NewNode->prev = NULL;

    if ((*head_ref) != NULL)
        (*head_ref)->prev = NewNode;

    (*head_ref) = NewNode;
}

public void push(int new_data)
{

    Node new_Node = new Node(new_data);

    new_Node.next = head;
    new_Node.prev = null;

    if (head != null)
        head.prev = new_Node;

    head = new_Node;
}

def push(self, new_data):

    new_node = Node(data = new_data)
    new_node.next = self.head
    new_node.prev = None

    if self.head is not None:
        self.head.prev = new_node

    self.head = new_node

Time Complexity: O(1), as no traversal is needed.
Space Complexity: O(1), as no extra space is required.

Insert at the end

In this approach, the new node will always be added after the last node of the given doubly linked list.

Approach

The approach is going to be very simple. Firstly, we have to traverse till the end of the list. After reaching the last node, we will make it point to the new node. After this step, we will make the previous pointer of the new node point to the last node.

Algorithm

• Allocate the new node and put in the data.
• As the new node is going to be the last, so the next of this new node will be NULL.
• If the linked list is empty, then simply make the new node as the head node and return.
• Else, traverse till the end of the doubly linked list and make the next of the last node point to the new node.
• Lastly, make the prev of the new node point to the last node.

Code Implementation

void append(struct Node** head_ref, int new_data)
{
    struct Node* NewNode = (struct Node*)malloc(sizeof(struct Node));
  
    struct Node* last = *head_ref; 

    NewNode->data = new_data;

    NewNode->next = NULL;

    if (*head_ref == NULL) {
        NewNode->prev = NULL;
        *head_ref = NewNode;
        return;
    }

    while (last->next != NULL)
        last = last->next;

    last->next = NewNode;
  
    NewNode->prev = last;
  
    return;
}

void append(int new_data)
{

    Node new_node = new Node(new_data);

    Node last = head; 

    new_node.next = null;

    if (head == null) {
        new_node.prev = null;
        head = new_node;
        return;
    }

    while (last.next != null)
        last = last.next;

    last.next = new_node;

    new_node.prev = last;
}

def append(self, new_data):
        new_node = Node(data = new_data)
        last = self.head
        new_node.next = None

        if self.head is None:
            new_node.prev = None
            self.head = new_node
            return

        while (last.next is not None):
            last = last.next

        last.next = new_node
        new_node.prev = last

Time Complexity: O(n), as one traversal is needed.
Space Complexity: O(1), as no extra space is required apart from the creation of node, which takes 20 bytes.

Insert after a given node

In this approach, the new node will always be added after a given node.

Approach

The approach is going to be very simple. We are given a pointer to a node as prev_node. The new node is to be inserted after prev_node.

As we have the pointer to that node (prev_node), we can perform this operation in O(1) time. Firstly, we will create the new node. Now, we will make the new node point to the next of prev_node. By doing this, we are making the new node point to the next node of prev_node.

Now, prev will point to the new node. Now, we just have to change the necessary links. So, we will make prev_node as the previous of the new node. In the end, if the new node is not the last node, we will make the new node’ s next node’s prev as the new node. By doing this, we are making the previous of the next node of the new node point to the new node.

Algorithm

• Allocate the new node and put in the data.
• Make the new node point to the next of prev_node.
• Now, make the prev_node point to the new node.
• The previous of the new node will point to the prev_node.
• If the new node is not the last node, it’s next’s previous point to the new node. By doing this, the new node becomes the previous of the next of the new node.
• If the linked list is empty, then simply make the new node as the head node and return.

Dry Run

Code Implementation

void insertAfter(struct Node* prev_node, int new_data)
{
    if (prev_node == NULL) {
        printf("the given previous node cannot be NULL");
        return;
    }

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

    new_node->data = new_data;

    new_node->next = prev_node->next;

    prev_node->next = new_node;

    new_node->prev = prev_node;

    if (new_node->next != NULL)
        new_node->next->prev = new_node;
}

public void InsertAfter(Node prev_Node, int new_data)
{

    if (prev_Node == null) {
        System.out.println("The given previous node cannot be NULL ");
        return;
    }

    Node new_node = new Node(new_data);

    new_node.next = prev_Node.next;

    prev_Node.next = new_node;

    new_node.prev = prev_Node;

    if (new_node.next != null)
        new_node.next.prev = new_node;
}

def insertAfter(self, prev_node, new_data):

        if prev_node is None:
            print("the given previous node cannot be NULL")
            return

        new_node = Node(data = new_data)
        new_node.next = prev_node.next
        prev_node.next = new_node
        new_node.prev = prev_node

        if new_node.next is not None:
            new_node.next.prev = new_node

Time Complexity: O(1), as no traversal is needed.
Space Complexity: O(1), as no extra space is required.

Insert before a given node

In this approach, the new node will always be added before a given node.

Approach

The approach is going to be very simple. We are given a pointer to a node as next_node. The new node is to be inserted before next_node.

As we have the pointer to that node (next_node), we can perform this operation in O(1) time. Firstly, we will create the new node. Now, we will make the previous of the new node as the previous of the next_node. By doing this, we are trying to add the new node in between the next_node and the previous node of the next node.

Now, the previous of the next node will point to the new node and the next of the new node will point to the next_node. Now, if the previous of the new node is not NULL, then the next of the previous node of the new node will point to the new node. By doing this, the we are changing the appropriate links.

If the previous of the new node is NULL, it means that the new node is the first node in the list, hence it will become our new head.

Algorithm

• Allocate the new node and put in the data.
• Make the previous of the new node point to the previous of the next node.
• The previous of the next_node will point to the new node.
• The new node will point to the next_node
• If the new node is not the head of the list, then the next of the previous of the new node will point to the new node. Else, the new node will become the head of the list.

Dry Run

Code Implementation

void insertBefore(struct Node** head_ref,
                  struct Node* next_node, int new_data)
{

    if (next_node == NULL) {
        printf("the given next node cannot be NULL");
        return;
    }
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));

    new_node->data = new_data;

    new_node->prev = next_node->prev;

    next_node->prev = new_node;

    new_node->next = next_node;

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

    else
        (*head_ref) = new_node;
}

void insertBefore(Node head_ref, Node next_node,int new_data)
{
    if(nex_node==null)
    {
        System.out.println("the display next node cannot be null");
        return;
    }
    Node new_node=new Node(new_data);
    new_node.prev=next_node.prev;
    next_node.prev=new_node;
    new_node.next=next_node;
    
    if(new_node.prev!=null)
    {
        new_node.prev.next=new_node;
    }
    else 
    {
        head_ref=new_node;
    }
}

def insertBefore(self, next_node, new_data):

    if next_node is None:
        print("the given next node cannot be NULL")
        return

    new_node = Node(new_data)
    new_node.prev = next_node.prev
    next_node.prev = new_node
    new_node.next = next_node

    if new_node.prev:
        new_node.prev.next = new_node

    else:
        self.head = new_node

Time Complexity: O(1), as no traversal is needed.
Space Complexity: O(1), as no extra space is required.

So, in this article, we have tried to explain what a doubly-linked list is, and its insertion operations. Doubly Linked List is a very important topic when it comes to Coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.