Insertion in Doubly Linked List : Beginning, End and Given Location

by

In this tutorial we will see algorithm and program to insert a given node at Beginning in the doubly linked list, at the End of doubly linked list and at the given location in doubly linked list.

Insertion in Doubly Linked List Algorithm

Insertion at the Beginning

  1. Create a New Node:
    • Start by creating a new node. Allocate memory for it and set the data field with the given value.
    • Since it’s a new node, initially set both its next and prev pointers to NULL.
  2. Check if List is Empty:
    • If the head (the first node of the list) is NULL, it means the list is empty.
    • In this case, the new node is the only node in the list, so set head to this new node.
  3. Insert the New Node:
    • If the list is not empty, then it already has at least one node.
    • Set the next pointer of the new node to the current head. This step links the new node to the existing list.
    • Set the prev pointer of the current head to the new node. This links the old head back to the new node.
    • Finally, update head to point to the new node, making it the new first node of the list.

Insertion at the End

  1. Create a New Node:
    • Similar to the first step above, create a new node and initialize it with the given data.
  2. Check if List is Empty:
    • If the list is empty (head is NULL), then make the new node the head of the list.
  3. Find the Last Node and Insert:
    • If the list is not empty, traverse it to find the last node. Do this by iterating through the list until you find a node whose next pointer is NULL.
    • Once you find the last node, set its next pointer to the new node.
    • Set the prev pointer of the new node to the last node.
    • The new node’s next remains NULL since it’s now the last node in the list.

Insertion at a Specific Location

  1. Create a New Node:
    • As before, start by creating a new node with the given data.
  2. Inserting at the Start:
    • If the specified location is 1 (the beginning of the list), use the steps for inserting at the beginning.
  3. Traverse to the Specific Location:
    • If the location is other than the start, begin at head and traverse the list.
    • Move through the list until you reach the node just before the desired position.
    • It’s important to ensure that this position is valid, i.e., it’s not beyond the end of the list.
  4. Insert the New Node:
    • Once you’re at the right spot, link the new node into the list.
    • Set the next pointer of the new node to the next node in the list.
    • Set the prev pointer of the next node (if it exists) to the new node.
    • Update the next pointer of the node before the insertion point to point to the new node.
    • Finally, set the prev pointer of the new node to the node before the insertion point.

C Program to Insert at Beginning, End and Given location in Doubly Linked List

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

// Doubly linked list Structure
struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
}; 

typedef struct Node Node;

// Create a new node for Doubly Linked List
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Insert at the beginning of Doubly Linked List
void insertAtBegin(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        newNode->next = *head;
        (*head)->prev = newNode;
        *head = newNode;
    }
}

// Insert at the end of Doubly Linked List
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// Insert at a specific location
void insertAtGivenLocation(Node** head, int data, int position) {
    Node* newNode = createNode(data);
    if (position == 1) {
        insertAtBegin(head, data);
        return;
    }
    Node* temp = *head;
    for (int i = 1; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("Position is beyond the length of the list.\n");
        return;
    }
    newNode->next = temp->next;
    newNode->prev = temp;
    if (temp->next != NULL) {
        temp->next->prev = newNode;
    }
    temp->next = newNode;
}

// Traverse and print the Doubly Linked List
void traverseDoublyLinkedList(Node* head) {
    Node* temp = head;
    printf("Doubly Linked List: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    Node* head = NULL;
    
    insertAtBegin(&head, 20); // Insertion at beginning
    insertAtGivenLocation(&head, 30, 1); // Insertion at position 1
    insertAtEnd(&head, 10); // Insertion at the end
    
    insertAtBegin(&head, 50); // Insertion at beginning
    insertAtGivenLocation(&head, 60, 2); // Insertion at position 2
    insertAtEnd(&head, 40); // Insertion at the end
    
    traverseDoublyLinkedList(head);
    return 0;
}

Output

Doubly Linked List: 50 60 30 20 10 40

Insertion in Doubly Linked List Program Explanation

Node Structure Definition

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

typedef struct Node Node;
  • Purpose: Defines the structure of each node in the doubly linked list.
  • Components:
    • int data: Holds the data value of the node.
    • struct Node* next: A pointer to the next node in the list.
    • struct Node* prev: A pointer to the previous node in the list.
  • The typedef is used to define Node as an alias for struct Node at the beginning. After that you can simply use Node to refer to this structure.

createNode Function

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}
  • Purpose: Creates a new node with given data.
  • Process:
    • Allocates memory for a new node.
    • Initializes the node’s data with the given value.
    • Sets the next and prev pointers of the node to NULL.
    • Returns the newly created node.

insertAtBegin Function

void insertAtBegin(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        newNode->next = *head;
        (*head)->prev = newNode;
        *head = newNode;
    }
}
  • Purpose: Inserts a new node at the beginning of the list.
  • Process:
    • Creates a new node.
    • If the list is empty (head is NULL), the new node becomes the head.
    • If the list is not empty, adjusts the pointers to insert the new node before the current head.

insertEnd Function

void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}
  • Purpose: Inserts a new node at the end of the list.
  • Process:
    • Creates a new node.
    • If the list is empty, the new node becomes the head.
    • If the list is not empty, traverses to the last node and adjusts the pointers to add the new node at the end.

insertAtGivenLocation Function

void insertAtGivenLocation(Node** head, int data, int position) {
    Node* newNode = createNode(data);
    if (position == 1) {
        insertAtBegin(head, data);
        return;
    }
    Node* temp = *head;
    for (int i = 1; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("Position is beyond the length of the list.\n");
        return;
    }
    newNode->next = temp->next;
    newNode->prev = temp;
    if (temp->next != NULL) {
        temp->next->prev = newNode;
    }
    temp->next = newNode;
}
  • Purpose: Inserts a new node at a specified position in the list.
  • Process:
    • Creates a new node.
    • If the position is 1, uses insertBegin to insert at the start.
    • Otherwise, traverses to the node just before the desired position and adjusts the pointers to insert the new node.

traverseDoublyLinkedList Function

void traverseDoublyLinkedList(Node* head) {
    Node* temp = head;
    printf("Doubly Linked List: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
  • Purpose: Traverses the list and prints the data of each node.
  • Process:
    • Starts from the head and moves through the list.
    • Prints the data of each node until it reaches the end of the list.

main Function

int main() {
    Node* head = NULL;
    
    insertAtBegin(&head, 20); // Insertion at beginning
    insertAtGivenLocation(&head, 30, 1); // Insertion at position 1
    insertAtEnd(&head, 10); // Insertion at the end
    
    insertAtBegin(&head, 50); // Insertion at beginning
    insertAtGivenLocation(&head, 60, 2); // Insertion at position 2
    insertAtEnd(&head, 40); // Insertion at the end

    traverseDoublyLinkedList(head);
    return 0;
}
  • Purpose: Demonstrates the functionality of the list.
  • Process:
    • Initializes an empty list.
    • Demonstrates insertion at the end, at the beginning, and at a specific position.
    • Traverses the list to display its contents.

This tutorial has explained and demonstrated of managing a doubly linked list, from node creation to insertion at various ways and traversal.