Write a function to Delete a node from Doubly Linked List ?
Write a function to Delete a node from Doubly Linked List ?
- In a single linked list, every node has link to its next node in the sequence.
- So, we can traverse from one node to another node only in one direction and we cannot traverse back. We can solve this kind of problem by using double linked list.
- Double linked list is a sequence of elements in which every element has links to its previous element and next element in the sequence.
- In double linked list, every node has link to its previous node and next node. So, we can traverse forward by using next field and can traverse backward by using previous field.

Algorithm
Algorithm to delete node from any position
Input :
head
{
Pointer to the first node of the list
}
last
{
Pointer to the last node of the list
}
N
{
Position to be deleted from list
}
Begin :
current ← head;
For i ← 1 to N and current != NULL do
current ← current.next;
End for
If (N == 1) then
deleteFromBeginning()
End if
Else if (current == last) then
deleteFromEnd()
End if
Else if (current != NULL) then
current.prev.next ← current.next
If (current.next != NULL) then
current.next.prev ← current.prev;
End if
unalloc (current)
write ('Node deleted successfully from ', N, ' position')
End if
Else then
write ('Invalid position')
End if
End Sample Code in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
/* Function to delete a node in a Doubly Linked List.
head_ref --> pointer to head node pointer.
del --> pointer to node to be deleted. */
void deleteNode(struct Node** head_ref, struct Node* del)
{
if (*head_ref == NULL || del == NULL)
return;
/* If node to be deleted is head node */
if (*head_ref == del)
*head_ref = del->next;
/* Change next only if node to be deleted is NOT
the last node */
if (del->next != NULL)
del->next->prev = del->prev;
/* Change prev only if node to be deleted is NOT
the first node */
if (del->prev != NULL)
del->prev->next = del->next;
/* Finally, free the memory occupied by del*/
free(del);
}
/* Function to delete the node at the given position
in the doubly linked list */
void deleteNodeAtGivenPos(struct Node** head_ref, int n)
{
/* if list in NULL or invalid position is given */
if (*head_ref == NULL || n <= 0)
return;
struct Node* current = *head_ref;
int i;
/* traverse up to the node at position 'n' from
the beginning */
for (int i = 1; current != NULL && i < n; i++)
current = current->next;
/* if 'n' is greater than the number of nodes
in the doubly linked list */
if (current == NULL)
return;
/* delete the node pointed to by 'current' */
deleteNode(head_ref, current);
}
/* Function to insert a node at the beginning
of the Doubly Linked List */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* since we are adding at the beginning,
prev is always NULL */
new_node->prev = NULL;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* change prev of head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given doubly
linked list */
void printList(struct Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
/* Create the doubly linked list 10<->8<->4<->2<->5 */
push(&head, 5);
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
cout << "Doubly linked list before deletion:n";
printList(head);
int n = 2;
/* delete node at the given position 'n' */
deleteNodeAtGivenPos(&head, n);
cout << "\nDoubly linked list after deletion:n";
printList(head);
return 0;
} Output
Doubly linked list before deletion:
10 8 4 2 5
Doubly linked list after deletion:
10 4 2 5 Time Complexity
- O(n), in worst case where n is the number of nodes in the doubly linked list.
Tags:
Accenture interview questions and answersalgorithm for insertion and deletion in doubly linked listAltimetrik India Pvt Ltd interview questions and answersApplied Materials interview questions and answersBharti Airtel interview questions and answersBMC Software interview questions and answersCapgemini interview questions and answersCASTING NETWORKS INDIA PVT LIMITED interview questions and answersCGI Group Inc interview questions and answersChetu interview questions and answersCiena Corporation interview questions and answersCollabera Te interview questions and answersdelete a node from linked list in cdelete all nodes in doubly linked listdelete all nodes in doubly linked list c++delete at position in a doubly linked listdelete last node in doubly linked list in c++delete last node in doubly linked list javadelete node from doubly linked list c++delete node from doubly linked list javadeletion in doubly linked listDell International Services India Pvt Ltd interview questions and answersdoubly circular linked list in data structuredoubly linked listdoubly linked list c codedoubly linked list deletiondoubly linked list deletion program in cmdoubly linked list exampledoubly linked list implementationdoubly linked list implementation in cdoubly linked list in cdoubly linked list in data structuredoubly linked list insertion and deletiondoubly linked list javadoubly linked list operationsdoubly linked list program in cdoubly linked list program in data structuredoubly linked list program in data structure using cFlipkart interview questions and answersgeekyants interview questions and answersGenpact interview questions and answersGloballogic India Pvt Ltd interview questions and answersIBM interview questions and answersIndecomm Global Services interview questions and answersinsertion and deletion in doubly linked list in clete a node from doubly linked listMphasis interview questions and answersNetApp interview questions and answersOracle Corporation interview questions and answersremove node from doubly linked list javaSAP Labs India Pvt Ltd interview questions and answersSapient Consulting Pvt Ltd interview questions and answersTech Mahindra interview questions and answersTracxn Technologies Pvt Ltd interview questions and answersUnitedHealth Group interview questions and answersWipro Infotech interview questions and answersWM Global Technology Services India Pvt.Ltd Limited (WMGTS) interview questions and answerswrite a function to delete a node from doubly linked listwrite a function to delete a node from doubly linked list javaXoriant Solutions Pvt Ltd interview questions and answersYodlee Infotech Pvt Ltd interview questions and answersOther Articles
Previous