Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on May 12, 2023 by Prepbytes

A doubly linked list is a data structure that consists of a set of nodes, each containing a value and two pointers – one to the next node and one to the previous node in the list.

What is a Doubly Linked List?

A doubly linked list is a sequence of elements, called nodes, where each node contains a reference to the previous and next node in the sequence. In other words, each node is linked to both its previous and next node in the list, hence the name "doubly linked" list.

Each node in a doubly linked list typically contains two pointers, one pointing to the previous node and one pointing to the next node. The first node in the list is called the head, and it does not have a previous node. Similarly, the last node in the list is called the tail, and it does not have a next node.

Insertion in a Doubly Linked List

Three cases can be considered for insertion in the doubly linked list.

• Insertion at the beginning
• Insertion after nth node
• Insertion at the end

Insertion at the Beginning of a Doubly Linked List

The procedures listed below would be used to add a new node to the doubly linked list’s starting position.

• Step 1: Add a new node.
• Step 2: Give its data a value.
• Step 3: Give the current head reference to the next pointer of the newly generated node. Consequently, it directs attention to the linked list address’s earlier start node.
• Step 4: Set the address of the new node as the head reference.
• Step 5: Change the previous pointer for the next node to the new node’s address (head reference).

Code Implementation

#include<stdio.h>
#include<stdlib.h>

struct Node
{
int data;
struct Node *next;
struct Node *prev;
};

void insertStart (struct Node **head, int data)
{

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

newNode->data = data;
newNode->prev = NULL;

// *head->prev = newNode; would not work it has (*head) must be used

//changing the new head to this freshly entered node
}

// function to print the doubly linked list
void display (struct Node *node)
{
struct Node *end;
printf ("Doubly Linked list : ");

while (node != NULL)
{
printf (" %d ", node->data);
end = node;
node = node->next;
}

}

int main ()
{

return 0;
}

Output

Doubly Linked list:  20  16  12

Insertion at the Nth Node in a Doubly Linked List

The procedures listed below would be used to add an nth node to the doubly linked lists.

• Step 1: Determine the node’s size.
• Step 2: Invalid position if the point you wish to enter is less than 1, but use the insertAtStart function if it is 0.
• Step 3: If the position you wish to input exceeds the size limit, the position is invalid, however, if the position is equal to the size limit, use the insertLast method.
• Step 4: Alternatively, construct a temporary node and give it the head’s address.
• Step 5: A new node should be created and given the data value.
• Step 6: Iterate to the location in the linked list that you wish to enter after.
• Step 7: Assign the next and previous nodes of this new node.
• Step 8: Next to this new node, place the preceding nodes.
• Step 9: Give this new node the previous node of the following node.

Code Implementation

#include<stdio.h>
#include<stdlib.h>

struct Node
{
int data;
struct Node *next;
struct Node *prev;
};

void insertLast (struct Node **head, int data);
void insertStart (struct Node **head, int data);

int calcSize (struct Node *node)
{
int size = 0;

while (node != NULL)
{
node = node->next;
size++;
}
return size;
}

void insertPosition (int pos, int data, struct Node **head)
{

if (pos < 0 || size < pos)
{
printf ("Can't insert, %d is not a valid position\n", pos);
return;
}

if (pos == 0)

else if (pos == size)
else
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
newNode->next = NULL;
while (--pos)
temp = temp->next;
struct Node *temp2 = temp->next;
newNode->next = temp->next;
newNode->prev = temp;
temp->next = newNode;
temp2->prev = newNode;
}
}

void insertLast (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
newNode->next = NULL;

{
newNode->prev = NULL;
return;
}
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}

void insertStart (struct Node **head, int data)
{
struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));
newNode->data = data;
newNode->prev = NULL;

}

void display (struct Node *node)
{
struct Node *end;
while (node != NULL)
{
printf (" %d ", node->data);
end = node;
node = node->next;
}

}

int main ()
{

printf ("linked before insertion at specific position\n");
printf ("\n\nlinked after insertion at specific position\n");

return 0;
}

Output

linked before insertion at specific position
Doubly linked list:  20  16  12  10  14  18  11

linked after insertion at specific position
Doubly linked list:  20  16  12  25  10  14  18  11

Insertion at the End of a Doubly Linked List

The procedures listed below would be used to add a node at the end of the doubly linked lists.

• Step 1: Add a new node.
• Step 2: Give its data a value.
• Step 3: As this will be the last (tail) node, assign its following node to NULL.
• Step 4: Verify that the list is empty.
• The head node should be changed to this node.
• Simply assign the preceding node as NULL and return if it is empty.
• Step 5: If not, continue until you reach the final node.
• Step 6: Give this new node the next pointer from the previous node.
• Step 7: Adding this new node between the list’s last and previous nodes.
• Step 8: The new node is now the last node.

Code Implementation

#include<stdio.h>
#include<stdlib.h>

struct Node
{
int data;
struct Node *next;
struct Node *prev;
};

void insertLast (struct Node **head, int data)
{

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

newNode->data = data;
newNode->next = NULL;

{
newNode->prev = NULL;
return;
}

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

temp->next = newNode;
newNode->prev = temp;
}

void insertStart (struct Node **head, int data)
{

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

newNode->data = data;
newNode->prev = NULL;

}

void display (struct Node *node)
{
struct Node *end;

while (node != NULL)
{
printf (" %d ", node->data);
end = node;
node = node->next;
}

}

int main ()
{

return 0;
}

Output

Doubly Linked list:  20  16  12  10  14  18  11

Conclusion
Insertion in a doubly linked list is a fundamental operation that involves adding a new node to the list at a specified position. The process is more complex than insertion in a singly linked list because we need to update both the "next" and "prev" pointers of multiple nodes. However, the advantage of a doubly linked list is that we can traverse the list both forwards and backward, which can be useful in certain applications. Understanding the process of insertion in a doubly linked list is important for anyone who works with linked lists or data structures in general.

Q1. What is the difference between insertion in a singly linked list and a doubly linked list?
Ans. In a singly linked list, insertion involves updating only the "next" pointer of the previous node and the new node. However, in a doubly linked list, insertion involves updating both the "next" and "prev" pointers of multiple nodes.