c++recursiondoubly-linked-list

Delete node at nth position from doubly linked list recursively? (C++)


I have been trying to practice a bit with some algorithms and in my code for a doubly linked list, I want to be able to delete a node at nth position recursively. I have tried doing this on my own but I cannot seem to find an effective way of doing so with recursion. If someone could possibly help me out in doing so that would be great. Here is the code I have so far.

Additionally, I am also aware that the current code I have for my delete function only works for a singly linked list. I figured this out on my own and just put it there as a placeholder / messing around with the code I have written below.

#include <cctype>

using namespace std;

struct Node{

  int data;
  Node* next;
  Node* prev;

};

Node* add(Node* head, int data);
void display(Node* head);
void displayReverse(Node* head);
Node* deleteNode(Node* head, int pos, Node* delNode);

int main(){


  Node* head = NULL;

  head = add(head, 1);
  head = add(head,2);
  head = add(head, 3);
  head = add(head, 4);
  head = add(head, 5);

  display(head);
  cout<<endl;
  displayReverse(head);

  cout<<endl;
  int del;
  cout<<"pos to delete: ";
  cin>>del;

  Node* delNode = NULL;
  head = deleteNode(head, del, delNode);
  display(head);
  return 0;
}

Node* add(Node* head, int data){

  if(head==NULL){ //if list is empty
    
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
  }
  else if(head!=NULL && head->next == NULL){ //if the head points to a node that has a next that is not empty, but the node at the next is empty, then add to the end of list

    Node* newNode = new Node;
    head->next = newNode;
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = head;
  }
  else{ //if the head does not equal null, and the head next does not equal null either

    head->next = add(head->next, data);
  }
  return head;

}

void display(Node* head){

  if(head!=NULL){

    cout<<head->data<<" ";
    display(head->next);
    
  }
  return;
  

}

void displayReverse(Node* head){ //checks if the nodes are actually linked (this implementation works)

  while(head->next!=NULL){
    head = head->next;
  }

  while(head!=NULL){
    cout<<head->data<< " ";
    head = head->prev;

  }

}


Node* deleteNode(Node* head, int pos, Node* delNode){

  if(pos = 1){

    delNode = head->next;
    delete head;
    return delNode;

  }
  else{

    head->next = deleteNode(head->next, pos-1, delNode);
    return head;
  }


}

Solution

  • To delete nth node from a doubly linked list recursively :

    Implementation:

    Node* deleteNode (Node* head, int pos) {
        static int cnt;
    
        if (head == NULL) {
            return NULL;
        }
    
        if (++cnt < pos) {
            head->next = deleteNode (head->next, pos);
            if (head->next) {
                // reset the pointer
                head->next->prev = head;
            }
        }
    
        if (cnt == pos) {
            Node *tmp = head->next;
            head->prev = NULL;
            head->next = NULL;
            free (head);
            // reset counter
            cnt = 0;
            if (tmp) {
                tmp->prev = NULL;
            }
            return tmp;
        }
    
        return head;
    }
    

    Output:

    # ./a.out   
    1 2 3 4 5 
    5 4 3 2 1 
    pos to delete: 2
    1 3 4 5 
    
    # ./a.out
    1 2 3 4 5 
    5 4 3 2 1 
    pos to delete: 1
    2 3 4 5 
    
    # ./a.out
    1 2 3 4 5 
    5 4 3 2 1 
    pos to delete: 5
    1 2 3 4 
    

    For invalid position :

    # ./a.out
    1 2 3 4 5 
    5 4 3 2 1 
    pos to delete: 8
    1 2 3 4 5 
    

    Additional:

    1). Avoid adding using namespace std; in your program. Check this.