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.

- Update the

### 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.

- Traverse the list to reach the last node (where

### 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.