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.
 Delete a node Doubly Linked List

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:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,