Deletion in Doubly Linked List

Deleting elements from different positions in a doubly linked list, including from the beginning, end, and specific positions

Deletion At Beginning

1

Check if the list is empty

  • If the head is NULL (list is empty), simply return NULL.
2

Save the current head node in a temporary variable

  • Assign the current head node to a temporary variable (temp).
3

Move the `head` pointer to the `next` node

  • Update head to point to the next node of the current head.
4

Update the `prev` pointer of the new head (if it exists)

  • If the new head is not NULL, set its prev pointer to NULL.
5

Delete the old head node

  • Deallocate the memory for the node stored in temp.
6

Return the updated head pointer

  • Return the new head.
//deletionatbeginning.c
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *prev;
struct Node *next;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
struct Node* delHead(struct Node* head) {
if (head == NULL)
    return NULL;
struct Node* temp = head;
head = head->next;
if (head != NULL)
    head->prev = NULL;
free(temp);
return head;
}
void display(struct Node* head) {
struct Node* curr = head;
while (curr) {
    printf("%d ", curr->data);
    curr = curr->next;
}
printf("\n");
}

int main() {
struct Node* head = createNode(1);
head->next = createNode(2);
head->next->prev = head;
head->next->next = createNode(3);
head->next->next->prev = head->next;

printf("Original Linked List: ");
display(head);

printf("After Deletion at the beginning: ");
head = delHead(head);
display(head);

return 0;
}

Deletion At Position

1

Handle the case of an empty list

  • If head is NULL, return head as the list is already empty.
2

Initialize a traversal pointer

  • Set a pointer curr to the head of the list.
3

Traverse the list to locate the node at the given position

  • Use a loop to move curr to the node at position pos:
  • For each iteration, move curr to the next node.
  • Stop when the desired position is reached or the end of the list is encountered.
4

Handle invalid positions

  • If curr is NULL after traversal, the position is invalid. Return head without making changes.
5

Update the pointers to remove the node

  • If the node has a previous node (curr->prev is not NULL):
  • Update the next pointer of the previous node to skip the current node.
  • If the node has a next node (curr->next is not NULL):
  • Update the prev pointer of the next node to skip the current node.
6

Update the head pointer if necessary

  • If the node to be deleted is the head node, update head to point to the next node.
7

Delete the node

  • Deallocate the memory for the node curr.
8

Return the updated head pointer

  • Return the modified head pointer.
//deletionatposition.c
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *prev;
struct Node *next;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
struct Node* delPos(struct Node* head, int pos) {
if (!head)
    return head;

struct Node* curr = head;
for (int i = 1; curr && i < pos; ++i) {
    curr = curr->next;
}

if (!curr)
    return head;

if (curr->prev)
    curr->prev->next = curr->next;
if (curr->next)
    curr->next->prev = curr->prev;
if (head == curr)
    head = curr->next;

free(curr);
return head;
}
void display(struct Node* head) {
struct Node* curr = head;
while (curr) {
    printf("%d ", curr->data);
    curr = curr->next;
}
printf("\n");
}

int main() {
struct Node* head = createNode(1);
head->next = createNode(2);
head->next->prev = head;
head->next->next = createNode(3);
head->next->next->prev = head->next;

printf("Original Linked List: ");
display(head);

printf("After Deletion at the position 2: ");
head = delPos(head, 2);
display(head);

return 0;
}

Deletion At Tail

1

Check if the list is empty

  • If head is NULL, return NULL as the list is empty.

  • Handle the case of deleting the head node:

If pos is 1:

  • Move head to the next node.

  • If the new head is not NULL, set its prev pointer to NULL.

  • Delete the old head node.

  • Return the updated head.

2

Traverse the list to locate the node

  • Initialize a pointer curr to head. Use a loop to move curr to the node at position pos:

  • For each iteration, move curr to the next node.

  • Stop if curr is NULL (end of list) or the desired position is reached.

3

Handle invalid positions

  • If curr is NULL after traversal, the position is invalid. Return the original head without changes.
4

Update the pointers to remove the node

  • If curr is NULL after traversal, the position is invalid. Return the original head without changes.
5

Handle invalid positions

If the node has a previous node (curr->prev is not NULL):

  • Update the next pointer of the previous node to skip the current node.

If the node has a next node (curr->next is not NULL):

  • Update the prev pointer of the next node to skip the current node.
6

Delete the node

  • Deallocate the memory for curr.
7

Return the updated head pointer

  • Return the modified head pointer.
//deletionatend.c
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *prev;
struct Node *next;
};
struct Node* delLast(struct Node* head) {
if (head == NULL)
    return NULL;
if (head->next == NULL) {
    free(head);
    return NULL;
}
struct Node* curr = head;
while (curr->next != NULL)
    curr = curr->next;
curr->prev->next = NULL;
free(curr); 
return head;
}
void display(struct Node* head) {
struct Node* curr = head;
while (curr != NULL) {
    printf("%d ", curr->data);
    curr = curr->next;
}
printf("\n");
}

int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->prev = head;
head->next->data = 2;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->prev = head->next;
head->next->next->data = 3;

printf("Original Linked List: ");
display(head);

printf("After Deletion at the end: ");
head = delLast(head);

display(head);

return 0;
}