[FIXED] How to delete a specific value from a doubly linked list?

Issue

I was given a task with a DOUBLY linked list to delete a specific number from the list. My code is giving an Access Violation error. Even after multiple dry runs, I can't figure out what is wrong. The task basically is to create a search function which finds a specific number in the linked list, and a deletion function which deletes that specific link.

node* search(int val){
    node* cur=head;
    while(cur!=NULL){
        if(cur->data==val){
            cout<<"value found "<<val<<endl;
            return cur;
        }
        cur=cur->next;
    }
    cout<<"value not exist"<<endl;
    return NULL;
}

bool delspval(int val){
    node*temp=0;
    if(search(val)==NULL){
        return 0;
    }
    else{
        temp=search(val);
        temp->prev->next=temp->next;
        delete temp;
        temp=0;
        cout<<"specific value "<<val<<" deleted"<<endl;
        return 1;
    }
}

In the above given code, the line temp->prev->next=temp->next; is giving the error. I'm pretty much a beginner at linked lists, so any help would be appreciated.

minimal working code:

#include<iostream>
using namespace std;
class dll{
    struct node{
        int data;
        node *next,*prev;
    };
    node *head;
public:
    dll(){
        head=NULL;
    }
    void inatst(int val){
        node *temp=new node;
        temp->data=val;
        temp->next=head;
        head=temp;
    }
    node* search(int val){
        node* cur=head;
        while(cur!=NULL){
            if(cur->data==val){
                cout<<"value found "<<val<<endl;
                return cur;
            }
            cur=cur->next;
        }
        cout<<"value not exist"<<endl;
                    return NULL;
    }
    bool delspval(int val){
        node*temp=0;
        if(search(val)==NULL){
            return 0;
        }
        else{
            temp=search(val);
            temp->prev->next=temp->next;
            delete temp;
            temp=0;
            cout<<"specific value "<<val<<" deleted"<<endl;
            return 1;
                }
            }
    void display(){
        node*cur=head;
        while(cur!=NULL){
            cout<<cur->data<<" ";
            cur=cur->next;
        }
        cout<<endl;
    }
    ~dll(){
        while(head!=NULL){
            node*cur=head;
            head=cur->next;
            delete cur;
            cur=head;
        }
    }
};
void main(){
    dll l1;
    l1.inatst(1);
    l1.inatst(2);
    l1.inatst(3);
    l1.inatst(4);
    l1.inatst(5);
    l1.inatst(6);
    l1.display();
    l1.delspval(3);
    system("pause");
}

Solution

For starters, the search() function is being called twice within the delspval() function:

if(search(val)==NULL){

and

temp=search(val);

that makes the delspval() function less efficient.

This statement:

temp->next->prev=temp->next;

does not make sense.

The delspval() function can be defined in the following way. I suppose that the class contains only one pointer to the head node. If the class contains also a pointer to the tail node, then the function below must be modified.

bool delspval( int val )
{
    node *temp = search( val );
    bool success = temp != nullptr;

    if ( success )
    {
        if ( temp->next != nullptr )
        {
            temp->next->prev = temp->prev;
        }
        // If the class has a pointer to the tail node
        //   then uncomment the else part  
        /*
        else
        {
            tail = temp->prev;
        }
        */

        if ( temp->prev != nullptr )
        {
            temp->prev->next = temp->next;
        }
        else
        {
            head = temp->next;
        }

        delete temp;
    }

    return success;
}

Answered By - Vlad from Moscow

Answer Checked By - David Goodson (PHPFixing Volunteer)

Read More

[FIXED] How can I print a doubly-linked list?

Issue

I wrote a program that creates a list from a sorted array, but somehow my print function does not work. Does anybody know what the problem is?

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>


typedef struct node{struct node *prev; int data; struct node *next;} node;
node *head;

void insertion_at_beginning();
void insertion_at_end();
void bubble_sort();
void print_list();
node* array_to_list();


int main()
{
    srand((long) time(NULL));
    int data[200];

    node *head = NULL;

    for (int i=0;i<200;i++){
        data[i] = rand() % (49 + 1 - 0) + 0;
    }

    bubble_sort(data, 200);

    head = array_to_list(data, 200);
    print_list(head, "LIST");

    return 0;
}

void insertion_at_beginning(int d)
{
   struct node *ptr;

   ptr = (struct node *)malloc(sizeof(struct node));
   if(ptr == NULL)
   {
       printf("\no v e r f l o w");


   if(head==NULL)
   {
       ptr -> next = NULL;
       ptr -> prev = NULL;
       ptr -> data = d;
       head = ptr;
   }
   else
   {
       ptr -> data = d;
       ptr -> prev = NULL;
       ptr -> next = head;
       head -> prev = ptr;
       head = ptr;
   }
}
}

void insertion_at_end(int f)
{
   struct node *ptr, *temp;

   ptr = (struct node *) malloc(sizeof(struct node));
   if(ptr == NULL)
   {
       printf("\no v e r f l o w");
   }

       ptr -> data = f;
       if(head == NULL)
       {
           ptr -> next = NULL;
           ptr -> prev = NULL;
           head = ptr;
       }
       else
       {
          temp = head;
          while(temp -> next != NULL)
          {
              temp = temp -> next;
          }
          temp -> next = ptr;
          ptr -> prev = temp;
          ptr -> next = NULL;
          }

       }

node* array_to_list(int d[], int size)
{
    insertion_at_beginning(d[0]);
    int i;
    for(i=1; i<size; i++)
    {
        insertion_at_beginning(d[i]);
    }
    return head;
}

void bubble_sort(int array[], int size)
{
    for (int i = 0 ; i < size - 1; i++)
          {
            for (int j = 0 ; j < size - i - 1; j++)
            {
              if (array[j] < array[j+1])
              {
                  int temp = array[j];
                  array[j] = array[j+1];
                  array[j+1] = temp;
              }
            }
          }
}

void print_list(node *h, char *title)
{
    printf("%s\n\n", title);
    while (h != NULL)
    {
        printf("%d : ", h -> data);
        h = h -> next;
        printf("%d : ", h -> data);
        h = h -> next;
        printf("%d : ", h -> data);
        h = h -> next;
        printf("%d : ", h -> data);
        h = h -> next;
        printf("%d : ", h -> data);
        h = h -> next;
        printf("\n");
    }
}

So with this last function I did manage printing a singly-linked list, and I thought that it should work the same way with a doubly linked list. But somehow it does not print anything except the title "LIST".

Solution

in void insertion_at_beginning(int d)

   if(ptr == NULL)
   {
       printf("\no v e r f l o w");
                                        <<<< NO EXIT BRACKET

   if(head==NULL)
   {
       ptr -> next = NULL;
       ptr -> prev = NULL;
       ptr -> data = d;
       head = ptr;
   }
   else
   {
       ptr -> data = d;
       ptr -> prev = NULL;
       ptr -> next = head;
       head -> prev = ptr;
       head = ptr;
   }
}

So your code does nothing unless malloc returns NULL.
Learning lesson : Formating your code (with a tool like clang-tidy) can save you a red-face.

Answered By - Tiger4Hire

Answer Checked By - Robin (PHPFixing Admin)

Read More

[FIXED] What is causing segmentation fault in append Node function in doubly linked list?

Issue

My doubly linked list implementation is as follows that each node holds an array of four values

#define EMPTYNODE 0

struct node {
short data[4]; // pay attention
struct node* next;
struct node* prev;
};

typedef struct node nodeQ_t;

typedef enum{
   LIST_FALSE = 0,
   LIST_TRUE = 1,
} status_t;

nodeQ_t* createNode(short values[4]){

    nodeQ_t* node = (nodeQ_t*)malloc(sizeof(node));
    for(int i=0; i < 4; i++){
       node->data[i] = values[i];
     }

   node->next = EMPTYNODE;
   node->prev = EMPTYNODE;
   return node;
}

now I am trying to write append function in a way that I supply it head and a node created in createNode function so that it would append it to the list.... but it creates a segmentation fault...

status_t appendNode(nodeQ_t* head, nodeQ_t* newNode){
if(head == EMPTYNODE || newNode == EMPTYNODE){
    return LIST_FALSE;
};

nodeQ_t* currentNode = head;

while(currentNode != EMPTYNODE){
    if(currentNode->next == EMPTYNODE){ //it means that current node is tail
        currentNode->next = newNode;  //segmenttion fault arises at exactly this line 
        newNode->prev = currentNode;
    }
    currentNode = currentNode->next;
}
return LIST_TRUE;
}

please let me know what is the reason for that... for your reference my main function is

int main(){
  short array[4] = {1,2,3,4};

  nodeQ_t* head  = createNode(array);

  printList(head);


  short array2[4] = {5,6,7,8};

  nodeQ_t* newNode = createNode(array2);

  appendNode(head, newNode);


  printList(head);



  return 0;

}

if you need any further information or explanation for anything please do let me know

Solution

As mentioned in the comments, you need to break out of the loop once you've reached the end:

while(currentNode != EMPTYNODE) {
    if (currentNode->next == EMPTYNODE) {
        currentNode->next = newNode;
        newNode->prev = currentNode;
        // need a break here
    }
    currentNode = currentNode->next;
    // When at the end of the list the 1st time through, 
    // currentNode is the newly created node because you have
    //     currentNode->next = newNode
    // then
    //     currentNode = currentNode->next
    // On the next iteration, the new node next ends up getting pointed to itself 
    // since on that iteration newNode and currentNode are the same.
    // and you end up with an infinite loop.
}

Another option is to loop on currentNode->next:

while (currentNode->next) {
    currentNode = currentNode->next;
}
currentNode->next = newNode;
newNode->prev = currentNode;

I should note that this works because you previously ensured that currentNode is not NULL.

Also, your allocation here is wrong:

nodeQ_t* node = (nodeQ_t*)malloc(sizeof(node));

Because node is a pointer and sizeof(node) is the size of a pointer, not the size of struct node. Should be

nodeQ_t* node = (nodeQ_t*)malloc(sizeof(*node));

Answered By - Johnny Mopp

Answer Checked By - David Marino (PHPFixing Volunteer)

Read More