# Deletion in a Doubly Linked List | C Program

## Deletion in doubly linked list

On this page we will discuss about deletion in doubly linked list in C . In a doubly linked list, we need to delete a node from the linked list. we just need to copy the head pointer to pointer ptr and shift the head pointer to its next.

 Deletion Time Complexity (AVG) Θ(1) Deletion Time Complexity (Worst) O(1) Space Complexity O(1)

## Deletion in Doubly Linked List in C language

So when we want to delete the node in the doubly linked list we have three ways to delete the node in another position.

•   Deletion at beginning
•   Deletion at middle
•   Deletion at last

In Disadvantages, Doubly linked list occupy more space and often more operations are required for the similar tasks as compared to singly linked lists.

It is easy to reverse the linked list.

If we are at a node, then we can go to any node. But in linear linked list, it is not possible to reach the previous node.

### Deletion at Beginning

#### Algorithm

• Check if there is only 1 node or not
• If there is one node
• Free memory
• Else
• Assign head to next node in the list
• Free memory

### Function for deletion at beginning in doubly linked list

```void deleteFront (struct Node **head)
{

// if DLL is empty
{
printf ("Linked List Empty, nothing to delete\n");
return;
}

// if Linked List has only 1 node
if (tempNode->next == NULL)
{
printf ("%d deleted\n", tempNode->data);
return;
}

// move head to next node
// assign head node's previous to NULL

printf ("%d deleted\n", tempNode->data);
free (tempNode);
}

```

### Deletion at middle

#### Algorithm

• Traverse till the target node
• create a node called the previous storing previous node of the target node
• Assign previous node’s next pointer to the next node of the target node
• For the next node of the target node, its previous pointer is assigned to the targets node’s previous node’s address
• Free memory of target node

### Function for deletion at middle in doubly linked list

```void deleteNthNode (struct Node **head, int n)
{
//if the head node itself needs to be deleted

// not valid
if (n < 1 || n > len)
{
printf ("Enter valid position\n");
return;
}

// delete the first node
if (n == 1)
{
return;
}

if (n == len)
{
return;
}

// traverse to the nth node
while (--n)
{
tempNode = tempNode->next;
}

struct Node *previousNode = tempNode->prev;	// (n-1)th node
struct Node *nextNode = tempNode->next;	// (n+1)th node

// assigning (n-1)th node's next pointer to (n+1)th node
previousNode->next = tempNode->next;

// assigning (n+1)th node's previous pointer to (n-1)th node
nextNode->prev = tempNode->prev;

// deleting nth node
printf ("%d deleted \n", tempNode->data);
free (tempNode);
}
```

### Deletion at last

• Traverse till the target node
• Check if this is the last node i.e. if node->next = NULL, then its last node
• Assign last node’s previous node’s next pointer to the last node’s next node’s address, which basically is NULL in this case
• Free the memory

### Function for deletion at end in doubly linked list

```void deleteEnd (struct Node **head)
{

// if DLL is empty
{
printf ("Linked List Empty, nothing to delete\n");
return;
}

// if Linked List has only 1 node
if (tempNode->next == NULL)
{
printf ("%d deleted\n", tempNode->data);
return;
}

// else traverse to the last node
while (tempNode->next != NULL)
tempNode = tempNode->next;

struct Node *secondLast = tempNode->prev;

// Curr assign 2nd last node's next to Null
secondLast->next = NULL;

printf ("%d deleted\n", tempNode->data);
free (tempNode);
}
```

#### Code for Deletion in a Doubly Linked List

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

struct Node
{
int data;
struct Node *next;
struct Node *prev;
};
int getLength (struct Node *node);

void insert (struct Node **head, int data)
{

struct Node *freshNode = (struct Node *) malloc (sizeof (struct Node));

freshNode->data = data;
freshNode->prev = NULL;

}

{

// if DLL is empty
{
printf ("Linked List Empty, nothing to delete\n");
return;
}

// if Linked List has only 1 node
if (tempNode->next == NULL)
{
printf ("%d deleted\n", tempNode->data);
return;
}

// move head to next node
// assign head node's previous to NULL

printf ("%d deleted\n", tempNode->data);
free (tempNode);
}

{

// if DLL is empty
{
printf ("Linked List Empty, nothing to delete\n");
return;
}

// if Linked List has only 1 node
if (tempNode->next == NULL)
{
printf ("%d deleted\n", tempNode->data);
return;
}

// else traverse to the last node
while (tempNode->next != NULL)
tempNode = tempNode->next;

struct Node *secondLast = tempNode->prev;

// Curr assign 2nd last node's next to Null
secondLast->next = NULL;

printf ("%d deleted\n", tempNode->data);
free (tempNode);
}

void deleteNthNode (struct Node **head, int n)
{
//if the head node itself needs to be deleted

// not valid
if (n < 1 || n > len)
{
printf ("Enter valid position\n");
return;
}

// delete the first node
if (n == 1)
{
return;
}

if (n == len)
{
return;
}

// traverse to the nth node
while (--n)
{
tempNode = tempNode->next;
}

struct Node *previousNode = tempNode->prev;	// (n-1)th node
struct Node *nextNode = tempNode->next;	// (n+1)th node

// assigning (n-1)th node's next pointer to (n+1)th node
previousNode->next = tempNode->next;

// assigning (n+1)th node's previous pointer to (n-1)th node
nextNode->prev = tempNode->prev;

// deleting nth node
printf ("%d deleted \n", tempNode->data);
free (tempNode);
}

// required for deleteNthNode
int getLength (struct Node *node)
{
int len = 0;

while (node != NULL)
{
node = node->next;
len++;
}

return len;
}

//function to print the doubly linked list
void display (struct Node *node)
{
struct Node *end = NULL;

printf ("List in Forward direction: ");
while (node != NULL)
{
printf (" %d ", node->data);
end = node;
node = node->next;
}

printf ("\nList in backward direction:");

while (end != NULL)
{
printf (" %d ", end->data);
end = end->prev;
}
printf ("\n\n");
}

int main ()
{

// delete 3rd node

// delete 1st node

// delete 1st node

return 0;
}
```

#### Output

```List in Forward direction:  12  11  10  9  8  7
List in backward direction: 7  8  9  10  11  12

12 deleted
List in Forward direction:  11  10  9  8  7
List in backward direction: 7  8  9  10  11

7 deleted
List in Forward direction:  11  10  9  8
List in backward direction: 8  9  10  11

9 deleted
List in Forward direction:  11  10  8
List in backward direction: 8  10  11

11 deleted
List in Forward direction:  10  8
List in backward direction: 8  10

8 deleted
List in Forward direction:  10
List in backward direction: 10
```

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

## Checkout list of all the video courses in PrepInsta Prime Subscription

• Introduction to Doubly Linked list in Data Structure
• Doubly Linked List in –
C | C++ | Java
• Insertion in doubly linked list –
C | C++ | Java
• Insertion at beginning in doubly linked list –
C | C++ | Java
• Insertion at end in doubly linked list –
C | C++ | Java
• Insertion at nth node in doubly linked list –
C | C++ | Java
• Deletion in doubly linked list  –
C | C++ | Java
• Deletion from beginning in doubly linked list :
• Deletion from nth in doubly linked list :
C | C++ | Java
• Deletion from end in doubly linked list :
C | C++ | Java
• Insertion and Deletion in a  doubly linked list :
C | C++ | Java
• Insertion in the middle in a  doubly linked list :
C | C++ | Java