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.
Categorized in:
Tagged in:
Accenture interview questions and answers, algorithm for insertion and deletion in doubly linked list, Altimetrik India Pvt Ltd interview questions and answers, Applied Materials interview questions and answers, Bharti Airtel interview questions and answers, BMC Software interview questions and answers, Capgemini interview questions and answers, CASTING NETWORKS INDIA PVT LIMITED interview questions and answers, CGI Group Inc interview questions and answers, Chetu interview questions and answers, Ciena Corporation interview questions and answers, Collabera Te interview questions and answers, delete a node from linked list in c, delete all nodes in doubly linked list, delete all nodes in doubly linked list c++, delete at position in a doubly linked list, delete last node in doubly linked list in c++, delete last node in doubly linked list java, delete node from doubly linked list c++, delete node from doubly linked list java, deletion in doubly linked list, Dell International Services India Pvt Ltd interview questions and answers, doubly circular linked list in data structure, doubly linked list, doubly linked list c code, doubly linked list deletion, doubly linked list deletion program in cm, doubly linked list example, doubly linked list implementation, doubly linked list implementation in c, doubly linked list in c, doubly linked list in data structure, doubly linked list insertion and deletion, doubly linked list java, doubly linked list operations, doubly linked list program in c, doubly linked list program in data structure, doubly linked list program in data structure using c, Flipkart interview questions and answers, geekyants interview questions and answers, Genpact interview questions and answers, Globallogic India Pvt Ltd interview questions and answers, IBM interview questions and answers, Indecomm Global Services interview questions and answers, insertion and deletion in doubly linked list in c, lete a node from doubly linked list, Mphasis interview questions and answers, NetApp interview questions and answers, Oracle Corporation interview questions and answers, remove node from doubly linked list java, SAP Labs India Pvt Ltd interview questions and answers, Sapient Consulting Pvt Ltd interview questions and answers, Tech Mahindra interview questions and answers, Tracxn Technologies Pvt Ltd interview questions and answers, UnitedHealth Group interview questions and answers, Wipro Infotech interview questions and answers, WM Global Technology Services India Pvt.Ltd Limited (WMGTS) interview questions and answers, write a function to delete a node from doubly linked list, write a function to delete a node from doubly linked list java, Xoriant Solutions Pvt Ltd interview questions and answers, Yodlee Infotech Pvt Ltd interview questions and answers