How To Insert In A Doubly Linked List In C

Define Doubly Linked List

Doubly Linked List is a variation of the Linked list in which navigation is possible in both ways, either forward or backward easily as compared to Single Linked List. Following are the essential terms to understand the concept of a doubly linked list.

  • data − Each data of a linked list is used to store data called an element.
  • Next − Each link of a linked list contains a link to the next link called Next.
  • Prev − Each link of a linked list contains a link to the previous link called Prev.

Here is the representation of the DLL node:

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

Let’s Discuss insertion in the doubly linked list in c.

Insertion in Doubly Linked List:

A node can be added in 3 ways in the doubly linked list:

  • At the front of the DLL.
  • After a Given Node.
  • At the end of the DLL.

1. Adding a node at the front

In this insertion, we will add the node at the front of the doubly linked list.

  • Create a new node
    • Allocate memory for newNode.
    • Assign data to the newNode.

  • Set prev and next pointers of the new node
    • point next of newNode to the first node of the doubly linked list
    • point prev to null

  • 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

Below is the implementation of the insertion at beginning of the DLL:

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

	new_node->data = new_data;

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

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

	(*head_ref) = new_node;
}

2. Adding node after the given node

We are given a pointer to a node as prev_node, and the new node is inserted after the given node.
Let’s add one node in the DLL. We have to add a new node with value E in the DLL with nodes A->B->C->D. We have to add a new node after node with value A.

  • Create a node
    • Allocate memory for newNode
    • Assign data to the newNode.

  • Set the next pointer of the new node and the previous node
    • assign the value of next from the previous node to the next of newNode
    • assign the address of newNode to the next of the previous node

  • Set the prev pointer of the new node and the next node
    • assign the value of prev of the next node to the prev of newNode
    • assign the address of newNode to the prev of next node

The Final Doubly Linked List after insertion is

Below is the implementation of insertion after the given node in the Doubly Linked list in C:

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

    struct Node* last = *head_ref; /* used in step 5*/

    new_node->data = new_data;

    new_node->next = NULL;

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

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

    last->next = new_node;

    new_node->prev = last;

    return;
}

3. Adding a node at the end

In this insertion, we will add the node at the end of the doubly linked list.
Let’s discuss it by adding a new node with value E at the end of the linked list with nodes A->B->C->D.

  • Create a node
    • Allocate memory for newNode
    • Assign data to the newNode.

  • Set prev and next pointers of the new node and the previous node
    If the linked list is empty, make the new node the head node. Otherwise, traverse to the end of the doubly linked list and perform the operations as shown below:

The Final list will be

Here is the implementation of insertion at the end of the doubly linked list in C:

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

    struct Node* last = *head_ref; /* used in step 5*/

    new_node->data = new_data;

    new_node->next = NULL;

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

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

    last->next = new_node;

    new_node->prev = last;

    return;
}

Below is the complete program to test the above functions:

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

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

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

	new_node->data = new_data;

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

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

	(*head_ref) = new_node;
}

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;
}

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

	struct Node* last = *head_ref;

	new_node->data = new_data;

	new_node->next = NULL;

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

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

	last->next = new_node;

	new_node->prev = last;

	return;
}

void printList(struct Node* node)
{
	struct Node* last;
	printf("\nTraversal in forward direction \n");
	while (node != NULL) {
		printf(" %d ", node->data);
		last = node;
		node = node->next;
	}

	printf("\nTraversal in reverse direction \n");
	while (last != NULL) {
		printf(" %d ", last->data);
		last = last->prev;
	}
}

int main()
{
	struct Node* head = NULL;

	append(&head, 2);

	push(&head, 4);

	push(&head, 6);

	append(&head, 8);

	insertAfter(head->next, 10);

	printf("Created DLL is: ");
	printList(head);

	getchar();
	return 0;
}

FAQ Related To Doubly Linked List In C

1. What are the advantages of doubly-linked lists over singly-linked lists?

  • A DLL can be traversed in both forward and backward directions.
  • The delete operation in DLL is more efficient if a pointer to the node to be deleted is given.
  • We can quickly insert a new node before a given node.
  • In a singly linked list, to delete a node, a pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using the previous pointer.

2. What are the limitations of doubly linked lists?
Disadvantages of a Doubly Linked List:

  • Compared to a singly linked list, each node stores an extra pointer which consumes additional memory.
  • Operations require more time due to the overhead of handling extra pointers as compared to singly-linked lists.
  • No random access of elements.

3. What is the difference between singly and doubly linked lists?
Both the Singly linked list and Doubly linked list are the executions of a Linked list. The singly-linked list holds data and a link to the next component. While in a doubly-linked list, every node includes a link to the previous node.

4. Which companies asked Doubly linked list in their interview?
Companies like Samsung, Josh Technologies, PrepBytes, Zscaler, and Infosys had recently asked for a Doubly Linked List in their interview round.

We tried to discuss Insertion in Doubly Linked List in C in this article. We hope this article gives you a better understanding of the doubly linked list. Prepbytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program that will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.

Leave a Reply

Your email address will not be published. Required fields are marked *