Delete a doubly linked list node at a given position
This article focuses on solving the problem of deleting a node at a given position in a Doubly Linked List. A Doubly Linked List is a data structure in which each node contains a value, a pointer to the next node, and a pointer to the previous node, allowing bidirectional traversal.


Problem Statement
The task is to design a program that can remove a node at a specified position in a Doubly Linked List. If the given position is valid, the program should adjust the pointers of the neighboring nodes to exclude the deleted node.
Example
Consider the following scenario:
Original Doubly Linked List: 11 → 22 → 33 → 44 → 55 → 66 → 77
Delete node at position 5.
Expected Result: 11 → 22 → 33 → 44 → 66 → 77
Idea to Solve
To solve this problem, we need to traverse the Doubly Linked List while counting the positions. Once the desired position is reached, we need to adjust the pointers of the neighboring nodes to bypass the node to be deleted.
Pseudocode
deleteNode(DoublyLinkedList list, int position):
if position < 1:
// Invalid position
return
if list.head is NULL:
print "Empty linked list"
return
if position is 1:
// Delete head node
list.head = list.head.next
if list.head is not NULL:
list.head.prev = NULL
else:
list.tail = NULL
else:
temp = list.head
n = 1
// Find node at given position
while temp is not NULL and n < position:
temp = temp.next
n = n + 1
if temp is NULL:
print "Deleted node position not found"
else:
temp.prev.next = temp.next
if temp.next is not NULL:
temp.next.prev = temp.prev
else:
// Delete tail node
list.tail = temp.prev
Algorithm Explanation
- If the given position is less than 1, return as it's an invalid position.
- If the linked list is empty, print "Empty linked list" and return.
- If the position is 1:
- Delete the head node by updating the head pointer.
- If the list is not empty, update the prev pointer of the new head.
- If the list becomes empty, update the tail pointer as well.
- If the position is not 1:
- Traverse the list until the desired position is reached.
- Update the pointers of neighboring nodes to bypass the node at the given position.
- If the node to be deleted is the last node, update the tail pointer.
Code Solution
-
1) Delete node at given position in a doubly linked list in java
2) Delete node at given position in a doubly linked list in c++
3) Delete node at given position in a doubly linked list in c
4) Delete node at given position in a doubly linked list in c#
5) Delete node at given position in a doubly linked list in php
6) Delete node at given position in a doubly linked list in python
7) Delete node at given position in a doubly linked list in ruby
8) Delete node at given position in a doubly linked list in golang
9) Delete node at given position in a doubly linked list in vb.net
10) Delete node at given position in a doubly linked list in node js
11) Delete node at given position in a doubly linked list in typescript
12) Delete node at given position in a doubly linked list in scala
13) Delete node at given position in a doubly linked list in swift
14) Delete node at given position in a doubly linked list in kotlin
Time Complexity
- For insertion, each insertion operation takes O(1) time.
- For deletion, in the worst case, where the node to be deleted is at the end of the list, the time complexity is O(n), where n is the number of nodes in the linked list.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment