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

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.


Related Searches to Write a function to Delete a node from Doubly Linked List ?