.png)
Deletion in a Doubly Linked List
Problem Statement
Given a doubly linked list, perform deletion of a node under different conditions:
- Deletion of the first node
- Deletion of the last node
- Deletion of a node with a given value
- Deletion of a node at a given position
In a doubly linked list, each node contains:
- A pointer to the previous node
- A pointer to the next node
This allows deletion in both forward and backward directions.
Structure of a Doubly Linked List Node
prev | data | next
General Edge Cases
- Empty linked list
- Single node linked list
- Invalid position
- Value not found
Approach 1: Deletion of First Node
Approach Explanation
To delete the first node:
- Move the head pointer to the second node
- Set the prev of the new head to NULL
Algorithm
- If head == NULL, return.
- Set head = head->next
- If head != NULL, set head->prev = NULL
Time Complexity
- O(1)
Space Complexity
- O(1)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Insert at end
void insertEnd(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
// Print list
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// ✅ MAIN FUNCTION (ADDED)
int main() {
struct Node* head = NULL;
insertEnd(&head, 10);
insertEnd(&head, 20);
insertEnd(&head, 30);
printf("Doubly Linked List:\n");
printList(head);
return 0;
}C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
Node* insertAtPosition(Node* head, int data, int position) {
Node* newNode = new Node(data);
if (position == 1) {
newNode->next = head;
return newNode;
}
Node* temp = head;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
cout << "Invalid position" << endl;
return head;
}
newNode->next = temp->next;
temp->next = newNode;
return head;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
Node* head = NULL;
head = insertAtPosition(head, 10, 1);
head = insertAtPosition(head, 30, 2);
head = insertAtPosition(head, 20, 2);
cout << "Linked List after insertion at position: ";
printList(head);
return 0;
}Java Implementation
static Node deleteFirst(Node head) {
if (head == null)
return null;
head = head.next;
if (head != null)
head.prev = null;
return head;
}
Python Implementation
def delete_first(head):
if head is None:
return None
head = head.next
if head:
head.prev = None
return head
JavaScript Implementation
function deleteFirst(head) {
if (head === null) return null;
head = head.next;
if (head !== null)
head.prev = null;
return head;
}
Output
Doubly Linked List:
10 <-> 20 <-> 30 <-> NULLApproach 2: Deletion of Last Node
Approach Explanation
To delete the last node:
- Traverse to the last node
- Update the next of second last node to NULL
Algorithm
- If head == NULL, return.
- Traverse to the last node.
- Set last->prev->next = NULL
Time Complexity
- O(n)
Space Complexity
- O(1)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
// Insert at end (for testing)
void insertEnd(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
// Delete Last Node
void deleteLast(struct Node** head) {
if (*head == NULL)
return;
struct Node* temp = *head;
// If only one node
if (temp->next == NULL) {
free(temp);
*head = NULL;
return;
}
// Traverse to last node
while (temp->next != NULL)
temp = temp->next;
// Remove last node
temp->prev->next = NULL;
free(temp);
}
// Print list
void printList(struct Node* head) {
while (head != NULL) {
printf("%d <-> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// Main function
int main() {
struct Node* head = NULL;
// Create list: 10 <-> 20 <-> 30 <-> 40
insertEnd(&head, 10);
insertEnd(&head, 20);
insertEnd(&head, 30);
insertEnd(&head, 40);
printf("Original List:\n");
printList(head);
// Delete last node
deleteLast(&head);
printf("\nAfter Deleting Last Node:\n");
printList(head);
return 0;
}C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
Node(int val) {
data = val;
prev = NULL;
next = NULL;
}
};
// Insert at end (for testing)
void insertEnd(Node*& head, int data) {
Node* newNode = new Node(data);
if (head == NULL) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
// Delete Last Node
void deleteLast(Node*& head) {
if (head == NULL)
return;
Node* temp = head;
// If only one node
if (temp->next == NULL) {
delete temp;
head = NULL;
return;
}
// Traverse to last node
while (temp->next != NULL)
temp = temp->next;
// Remove last node
temp->prev->next = NULL;
delete temp;
}
// Print list
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " <-> ";
head = head->next;
}
cout << "NULL\n";
}
// Main function
int main() {
Node* head = NULL;
// Create list: 10 <-> 20 <-> 30 <-> 40
insertEnd(head, 10);
insertEnd(head, 20);
insertEnd(head, 30);
insertEnd(head, 40);
cout << "Original List:\n";
printList(head);
// Delete last node
deleteLast(head);
cout << "\nAfter Deleting Last Node:\n";
printList(head);
return 0;
}}
Java Implementation
static Node deleteLast(Node head) {
if (head == null)
return null;
if (head.next == null)
return null;
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.prev.next = null;
return head;
}
Python Implementation
def delete_last(head):
if head is None:
return None
if head.next is None:
return None
temp = head
while temp.next:
temp = temp.next
temp.prev.next = None
return head
JavaScript Implementation
function deleteLast(head) {
if (head === null) return null;
if (head.next === null) return null;
let temp = head;
while (temp.next !== null)
temp = temp.next;
temp.prev.next = null;
return head;
}
Output
Original List:
10 <-> 20 <-> 30 <-> 40 <-> NULL
After Deleting Last Node:
10 <-> 20 <-> 30 <-> NULLApproach 3: Deletion of Node with Given Value
Approach Explanation
Traverse the list to find the node with the given value and update the pointers of its neighboring nodes.
Algorithm
- If head == NULL, return.
- Traverse the list until the value is found.
- If node is head, delete first node.
- If node is last, delete last node.
- Otherwise:
- node->prev->next = node->next
- node->next->prev = node->prev
Time Complexity
- O(n)
Space Complexity
- O(1)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
void insert(struct Node** head, int val) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->next = NULL;
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d <-> ", head->data);
head = head->next;
}
printf("NULL\n");
}
void deleteByValue(struct Node** head, int key) {
struct Node* temp = *head;
if (temp == NULL) return;
// delete head
if (temp->data == key) {
*head = temp->next;
if (*head != NULL)
(*head)->prev = NULL;
free(temp);
return;
}
while (temp && temp->data != key)
temp = temp->next;
if (temp == NULL) return;
if (temp->next)
temp->next->prev = temp->prev;
if (temp->prev)
temp->prev->next = temp->next;
free(temp);
}
int main() {
struct Node* head = NULL;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
printf("Before:\n");
printList(head);
deleteByValue(&head, 20);
printf("After Deleting 20:\n");
printList(head);
return 0;
}
C++
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
void insert(Node*& head, int val) {
Node* newNode = new Node{val, NULL, NULL};
if (!head) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
void printList(Node* head) {
while (head) {
cout << head->data << " <-> ";
head = head->next;
}
cout << "NULL\n";
}
void deleteByValue(Node*& head, int key) {
if (!head) return;
Node* temp = head;
if (temp->data == key) {
head = temp->next;
if (head) head->prev = NULL;
delete temp;
return;
}
while (temp && temp->data != key)
temp = temp->next;
if (!temp) return;
if (temp->next)
temp->next->prev = temp->prev;
if (temp->prev)
temp->prev->next = temp->next;
delete temp;
}
int main() {
Node* head = NULL;
insert(head, 10);
insert(head, 20);
insert(head, 30);
insert(head, 40);
cout << "Before:\n";
printList(head);
deleteByValue(head, 20);
cout << "After Deleting 20:\n";
printList(head);
return 0;
}
Java
class Node {
int data;
Node prev, next;
Node(int data) {
this.data = data;
prev = next = null;
}
}
public class Main {
static Node insert(Node head, int val) {
Node newNode = new Node(val);
if (head == null)
return newNode;
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = newNode;
newNode.prev = temp;
return head;
}
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " <-> ");
head = head.next;
}
System.out.println("NULL");
}
static Node deleteByValue(Node head, int key) {
if (head == null) return null;
Node temp = head;
if (temp.data == key) {
head = temp.next;
if (head != null)
head.prev = null;
return head;
}
while (temp != null && temp.data != key)
temp = temp.next;
if (temp == null) return head;
if (temp.next != null)
temp.next.prev = temp.prev;
if (temp.prev != null)
temp.prev.next = temp.next;
return head;
}
public static void main(String[] args) {
Node head = null;
head = insert(head, 10);
head = insert(head, 20);
head = insert(head, 30);
head = insert(head, 40);
System.out.println("Before:");
printList(head);
head = deleteByValue(head, 20);
System.out.println("After Deleting 20:");
printList(head);
}
}
Python
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def insert(head, val):
new_node = Node(val)
if not head:
return new_node
temp = head
while temp.next:
temp = temp.next
temp.next = new_node
new_node.prev = temp
return head
def print_list(head):
temp = head
while temp:
print(temp.data, end=" <-> ")
temp = temp.next
print("NULL")
def delete_by_value(head, key):
if not head:
return None
temp = head
if temp.data == key:
head = temp.next
if head:
head.prev = None
return head
while temp and temp.data != key:
temp = temp.next
if not temp:
return head
if temp.next:
temp.next.prev = temp.prev
if temp.prev:
temp.prev.next = temp.next
return head
# Main
head = None
for val in [10, 20, 30, 40]:
head = insert(head, val)
print("Before:")
print_list(head)
head = delete_by_value(head, 20)
print("After Deleting 20:")
print_list(head)
JavaScript
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
function insert(head, val) {
let newNode = new Node(val);
if (!head) return newNode;
let temp = head;
while (temp.next)
temp = temp.next;
temp.next = newNode;
newNode.prev = temp;
return head;
}
function printList(head) {
let temp = head;
let result = "";
while (temp) {
result += temp.data + " <-> ";
temp = temp.next;
}
console.log(result + "NULL");
}
function deleteByValue(head, key) {
if (!head) return null;
let temp = head;
if (temp.data === key) {
head = temp.next;
if (head) head.prev = null;
return head;
}
while (temp && temp.data !== key)
temp = temp.next;
if (!temp) return head;
if (temp.next)
temp.next.prev = temp.prev;
if (temp.prev)
temp.prev.next = temp.next;
return head;
}
// Main
let head = null;
[10, 20, 30, 40].forEach(val => head = insert(head, val));
console.log("Before:");
printList(head);
head = deleteByValue(head, 20);
console.log("After Deleting 20:");
printList(head);
Output
Before:
10 <-> 20 <-> 30 <-> 40 <-> NULL
After Deleting 20:
10 <-> 30 <-> 40 <-> NULL
Approach 4: Deletion at a Given Position
Approach Explanation
Traverse the list until the required position and delete the node by updating adjacent pointers.
Algorithm
- If head == NULL, return.
- If position is 1, delete first node.
- Traverse to the given position.
- Update neighboring pointers.
Time Complexity
- O(n)
Space Complexity
- O(1)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
void insert(struct Node** head, int val) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->next = NULL;
if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
void printList(struct Node* head) {
while (head) {
printf("%d <-> ", head->data);
head = head->next;
}
printf("NULL\n");
}
void deleteAtPosition(struct Node** head, int pos) {
if (*head == NULL || pos <= 0) return;
struct Node* temp = *head;
// delete head
if (pos == 1) {
*head = temp->next;
if (*head)
(*head)->prev = NULL;
free(temp);
return;
}
int count = 1;
while (temp && count < pos) {
temp = temp->next;
count++;
}
if (temp == NULL) return;
if (temp->next)
temp->next->prev = temp->prev;
if (temp->prev)
temp->prev->next = temp->next;
free(temp);
}
int main() {
struct Node* head = NULL;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
printf("Before:\n");
printList(head);
deleteAtPosition(&head, 2);
printf("After Deleting Position 2:\n");
printList(head);
return 0;
}
C++
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
void insert(Node*& head, int val) {
Node* newNode = new Node{val, NULL, NULL};
if (!head) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
void printList(Node* head) {
while (head) {
cout << head->data << " <-> ";
head = head->next;
}
cout << "NULL\n";
}
void deleteAtPosition(Node*& head, int pos) {
if (!head || pos <= 0) return;
Node* temp = head;
if (pos == 1) {
head = temp->next;
if (head) head->prev = NULL;
delete temp;
return;
}
int count = 1;
while (temp && count < pos) {
temp = temp->next;
count++;
}
if (!temp) return;
if (temp->next)
temp->next->prev = temp->prev;
if (temp->prev)
temp->prev->next = temp->next;
delete temp;
}
int main() {
Node* head = NULL;
insert(head, 10);
insert(head, 20);
insert(head, 30);
insert(head, 40);
cout << "Before:\n";
printList(head);
deleteAtPosition(head, 2);
cout << "After Deleting Position 2:\n";
printList(head);
return 0;
}
Java
class Node {
int data;
Node prev, next;
Node(int data) {
this.data = data;
prev = next = null;
}
}
public class Main {
static Node insert(Node head, int val) {
Node newNode = new Node(val);
if (head == null)
return newNode;
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = newNode;
newNode.prev = temp;
return head;
}
static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " <-> ");
head = head.next;
}
System.out.println("NULL");
}
static Node deleteAtPosition(Node head, int pos) {
if (head == null || pos <= 0)
return head;
Node temp = head;
if (pos == 1) {
head = temp.next;
if (head != null)
head.prev = null;
return head;
}
int count = 1;
while (temp != null && count < pos) {
temp = temp.next;
count++;
}
if (temp == null)
return head;
if (temp.next != null)
temp.next.prev = temp.prev;
if (temp.prev != null)
temp.prev.next = temp.next;
return head;
}
public static void main(String[] args) {
Node head = null;
head = insert(head, 10);
head = insert(head, 20);
head = insert(head, 30);
head = insert(head, 40);
System.out.println("Before:");
printList(head);
head = deleteAtPosition(head, 2);
System.out.println("After Deleting Position 2:");
printList(head);
}
}
Python
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
def insert(head, val):
new_node = Node(val)
if not head:
return new_node
temp = head
while temp.next:
temp = temp.next
temp.next = new_node
new_node.prev = temp
return head
def print_list(head):
temp = head
while temp:
print(temp.data, end=" <-> ")
temp = temp.next
print("NULL")
def delete_at_position(head, pos):
if not head or pos <= 0:
return head
temp = head
if pos == 1:
head = temp.next
if head:
head.prev = None
return head
count = 1
while temp and count < pos:
temp = temp.next
count += 1
if not temp:
return head
if temp.next:
temp.next.prev = temp.prev
if temp.prev:
temp.prev.next = temp.next
return head
# Main
head = None
for val in [10, 20, 30, 40]:
head = insert(head, val)
print("Before:")
print_list(head)
head = delete_at_position(head, 2)
print("After Deleting Position 2:")
print_list(head)
JavaScript
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
function insert(head, val) {
let newNode = new Node(val);
if (!head) return newNode;
let temp = head;
while (temp.next)
temp = temp.next;
temp.next = newNode;
newNode.prev = temp;
return head;
}
function printList(head) {
let temp = head;
let res = "";
while (temp) {
res += temp.data + " <-> ";
temp = temp.next;
}
console.log(res + "NULL");
}
function deleteAtPosition(head, pos) {
if (!head || pos <= 0) return head;
let temp = head;
if (pos === 1) {
head = temp.next;
if (head) head.prev = null;
return head;
}
let count = 1;
while (temp && count < pos) {
temp = temp.next;
count++;
}
if (!temp) return head;
if (temp.next)
temp.next.prev = temp.prev;
if (temp.prev)
temp.prev.next = temp.next;
return head;
}
// Main
let head = null;
[10, 20, 30, 40].forEach(val => head = insert(head, val));
console.log("Before:");
printList(head);
head = deleteAtPosition(head, 2);
console.log("After Deleting Position 2:");
printList(head);
Output
Before:
10 <-> 20 <-> 30 <-> 40 <-> NULL
After Deleting Position 2:
10 <-> 30 <-> 40 <-> NULL
Comparison of Deletion Operations
| Deletion Type | Time Complexity | Space Complexity |
|---|---|---|
| Delete First | O(1) | O(1) |
| Delete Last | O(n) | O(1) |
| Delete by Value | O(n) | O(1) |
| Delete by Position | O(n) | O(1) |
Key Points to Remember
- Doubly linked lists allow backward traversal
- Deletion requires updating both prev and next pointers
- Handle head and tail deletion separately
- Always check for NULL pointers
Conclusion
Deletion in a doubly linked list is efficient and flexible due to the presence of backward links. By carefully updating adjacent node pointers, deletion can be performed without breaking the structure of the list, using linear time and constant space.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
