Delete in Doubly Linked List: Beginning, End and Given location

by

In this tutorial we will learn how to perform delete operation on doubly linked list. We will see deletion from the Beginning, End, and at the Given location in doubly linked list.

Algorithm for Deleting Nodes

1. Delete from the Beginning

  • Check if List is Empty: Start by checking if the list is empty. If the head of the list is NULL, it means there are no nodes to delete. In this case, indicate that deletion is not possible.
  • Single Node in the List: If the list contains only one node (i.e., head->next is NULL), delete this node and set head to NULL. This action leaves the list empty.
  • Multiple Nodes in the List: If there are multiple nodes in the list, proceed to remove the first node. To do this:
    • Update the head of the list to point to the second node (head->next).
    • Set the prev pointer of the new head node to NULL to make it as a head node.
    • Delete the old head node.

2. Delete from the End

  • Check if List is Empty: As with deletion from the beginning, start by checking if the list is empty. If it is, indicate that deletion is not possible.
  • Single Node in the List: If the list has only one node, delete it and set head to NULL.
  • Multiple Nodes in the List: If the list contains more than one node, you need to find the last node and remove it. To do this:
    • Traverse the list to reach the last node (where node->next is NULL).
    • Set the next pointer of the second-to-last node to NULL, It will remove the last node from the list.
    • Delete the last node.

3. Delete from a Specific Location

  • Check for Empty List or Invalid Location: If the list is empty or the given location is less than 1, indicate that deletion is not possible.
  • Deletion at the First Position: If the specified location is 1, use the procedure for deleting from the beginning.
  • Deletion at a Specific Position: If the location is greater than 1, you must find the node at that position and remove it. To do this:
    • Traverse the list to reach the node at the given position.
    • Once you find the node, adjust the next pointer of its previous node to point to its next node. Similarly, adjust the prev pointer of its next node (if it exists) to point to its previous node.
    • These adjustments effectively remove the target node from the list.
    • Finally, delete the node from memory.

Delete Operation in Doubly Linked List using C

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

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

typedef struct Node Node;

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

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

// Delete from the Begining of Doubly linked list
void deleteFromBeginning(Node** head) {
    if (*head == NULL) {
        printf("Given List is empty. Can't Perform delete operation.\n");
        return;
    }
    Node *temp = *head;
    if (temp->next == NULL) {
        *head = NULL;
    } else {
        *head = temp->next;
        (*head)->prev = NULL;
    }
    free(temp);
}

// Delete from the End of Doubly linked list
void deleteFromEnd(Node** head) {
    if (*head == NULL) {
        printf("Given List is empty. Can't Perform delete operation.\n");
        return;
    }
    Node *temp = *head;
    if (temp->next == NULL) {
        *head = NULL;
        free(temp);
    } else {
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->prev->next = NULL;
        free(temp);
    }
}

// Delete from the given position of Doubly linked list
void deleteFromGivenPosition(Node** head, int position) {
    if (*head == NULL || position < 1) {
        printf("Invalid position or list is empty.\n");
        return;
    }
    if (position == 1) {
        deleteFromBeginning(head);
        return;
    }
    Node *temp = *head;
    for (int i = 1; temp != NULL && i < position; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("Position beyond list length.\n");
        return;
    }
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }
    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    }
    free(temp);
}

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

int main() {
    Node *head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    insertAtEnd(&head, 60);
    deleteFromBeginning(&head);
    deleteFromEnd(&head);
    deleteFromGivenPosition(&head, 2);
        traverseDoublyLinkedList(head);

    return 0;
}

Output

Doubly Linked List After Delete Operations: 20 40 50

Execution of the program

Initial State: Empty list (head = NULL).

After insertAtEnd(&head, 10):

List: 10

After insertAtEnd(&head, 20):

List: 10 -> 20

After insertAtEnd(&head, 30):

List: 10 -> 20 -> 30

After insertAtEnd(&head, 40):

List: 10 -> 20 -> 30 -> 40

After insertAtEnd(&head, 50):

List: 10 -> 20 -> 30 -> 40 -> 50

After insertAtEnd(&head, 60):

List: 10 -> 20 -> 30 -> 40 -> 50 -> 60

After deleteFromBeginning(&head):

List: 20 -> 30 -> 40 -> 50 -> 60

After deleteFromEnd(&head):

List: 20 -> 30 -> 40 -> 50

After deleteFromGivenPosition(&head, 2):

This deletes the node at position 2, which is ’30’ in this case.

List: 20 -> 40 -> 50

After traverseDoublyLinkedList(head):

This traverses the list and prints its elements.

Expected Output: "Doubly Linked List After Delete Operations: 20 40 50".

Explanation of the above program

Defining the Node Structure

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

This defines the structure of a node in the doubly linked list. Each node contains:

  • int data: the value stored in 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.

Creating a New Node

Node *createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}
  • This function creates a new node with the specified data.
  • It allocates memory for the node, initializes its data, and sets the next and prev pointers to NULL.

Inserting at the End of the List

void insertAtEnd(Node** head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node *temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}
  • This function inserts a new node at the end of the list.
  • If the list is empty (head is NULL), the new node becomes the head.
  • Otherwise, it finds the last node and inserts the new node after it, adjusting the next pointer of the last node and the prev pointer of the new node.

Deleting from the Beginning of the List

void deleteFromBeginning(Node** head) {
    if (*head == NULL) {
        printf("Given List is empty. Can't Perform delete operation.\n");
        return;
    }
    Node *temp = *head;
    if (temp->next == NULL) {
        *head = NULL;
    } else {
        *head = temp->next;
        (*head)->prev = NULL;
    }
    free(temp);
}
  • This function removes the first node from the list.
  • It checks if the list is empty before proceeding.
  • If there’s only one node, it deletes it and sets head to NULL.
  • If there are multiple nodes, it updates head to the second node and sets the prev pointer of the new head to NULL.

Deleting from the End of the List

void deleteFromEnd(Node** head) {
    if (*head == NULL) {
        printf("Given List is empty. Can't Perform delete operation.\n");
        return;
    }
    Node *temp = *head;
    if (temp->next == NULL) {
        *head = NULL;
        free(temp);
    } else {
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->prev->next = NULL;
        free(temp);
    }
}
  • This function deletes the last node in the list.
  • Similar to the previous function, it checks if the list is empty or has only one node.
  • If there are multiple nodes, it finds the last node, updates the next pointer of the second-to-last node, and frees the last node.

Deleting from a Given Position

void deleteFromGivenPosition(Node** head, int position) {
    if (*head == NULL || position < 1) {
        printf("Invalid position or list is empty.\n");
        return;
    }
    if (position == 1) {
        deleteFromBeginning(head);
        return;
    }
    Node *temp = *head;
    for (int i = 1; temp != NULL && i < position; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("Position beyond list length.\n");
        return;
    }
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }
    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    }
    free(temp);
}
  • This function deletes a node at a specific position.
  • It traverses the list to find the node at the given position and updates the next and prev pointers of the neighboring nodes accordingly.
  • If the position is 1, it calls deleteFromBeginning.

Traversing and Printing the List

void traverseDoublyLinkedList(Node* head) {
    Node* temp = head;
    printf("Doubly Linked List After Delete Operations: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

This function traverses the list from the head and prints the data of each node.

Main Function

int main() {
    Node *head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    insertAtEnd(&head, 60);
    deleteFromBeginning(&head);
    deleteFromEnd(&head);
    deleteFromGivenPosition(&head, 2);
    traverseDoublyLinkedList(head);

    return 0;
}

The main function demonstrates the functionality of the list by inserting nodes, performing delete operations, and then traversing the list to display its contents.

Hope the above tutorial will helped you to understand the delete operation in doubly linked list.