Doubly Linked List Node Deletion

[val24]

Hello everyone, I'm having problems with deletion of a single node within a linked list. I have a populated list. When I delete my target node, my code deletes the first node of the list instead. I am searching for my node via an "ISBN" number. My structs are structured as a header struct pointing to the ends to the list, structs to traverse the list and within these structs I point to a data struct which holds necessary data for my project. Would I absolutely need temp variables to delete a node?

void delRec(slist* list)
{   
    sentry* node = new sentry;
    node = list->first; // allow node to be the first member of my list
    if (!node->next) // if first item points to null, nothing to do; return 
        return;
        
    cout << "Which ISBN would you like to delete?\n\n";
    
    while(1) // outputting all values
    {
        if(node->prev)
        {
            cout << "ISBN: " << node->record->longbn << '\n';
        }
        if(!node->next)
            break;
        node = node->next;
    }
    
    long tempbn; 
    cout << "ISBN: ";
    cin >> tempbn;
    cout << "Deleting: " << tempbn << '\n';
    pause();
    node = list->first; // send it back to the front
    while(1)
    {   
        if(node->prev)
        {   // If value entered is value im looking for; delete.
            if(node->record->longbn == tempbn  /*&& node != list->first && node != list->last*/);
            {   
                delete node->record; // delete its info node
                node->prev->next = node->next; // Redirect pointers
                node->next->prev = node->prev;
                //node->next = NULL;
                //node->prev = NULL;
                delete node; // delete my pointer node
                break; 
                //return;
            }
        }
        if(!node->next)
            break;
        node = node->next;
    }                                                                   
}

[dhayden]

So if I'm reading this right, the list always has a sentry node at the beginning and that's why you check for node->prev each time. If that's right then it would be easier to walk the list with code like this:

[code]for (node = list->first->next; node; node = node->next) {
   cout << "ISBN: " << node->record->longbn << '\n';
}

[/code]
You leak the sentry allocated at line 3. To fix this, combine lines 3 and 4 into sentry *node = list->first;
Line 35: If you're deleting the last node then node->next will be nullptr. Also, you'll have to update your tail pointer (assuming that you have one).

None of these things explain the behavior you're seeing. I suspect that the pointers for the list are invalid when you call delRec(). That means that the bug is in another if your functions. I suggest that you add a function to print the list both forwards and backwards and call it after each insertion/deletion. You'll probably find that the pointers get out of whack somewhere.

[bird1234]

node* temp = head, *delTemp = last;

 if (temp == NULL)
 {
  cout << "\nEmpty";
 }
 else if (temp->data == item)
 {
  if (temp->next != NULL)
  {
   head = head->next;
   head->back = temp->back;
   delete temp;
  }
  else
  {
   delete temp;
   head = NULL;
  }
  found = false;
 }
 else if (delTemp->data == item)
 {
  last = last->back;
  last->next = delTemp->next;
  delete delTemp;
  found = false;
 }
 else
 {
  while (temp != NULL)
  {
   if (temp->data == item)
   {
    delTemp = temp;
    temp = temp->back;
    temp->next = delTemp->next;
    delTemp->next->back = temp;
    found = false;
    delete delTemp;
   }
   else
   {
    temp = temp->next;
   }
  }
 }

[val24]

Thanks for the help, the for loop is a great way to clean my code up. Didnt even think about using it that way. Bird Im positive your code will will delete the node but i was hoping there might be a way to do so without a temp variable.

[val24]

dhayden, I am able to print the list properly. I even have an insertion sort working on it on another function. I'm pretty sure the problem is in the deletion function still. Nevertheless, I'll find it and post the solution here.

[dhayden]

Val24, if you post your fill code here, we can probably be more helpful.

Oh, and your code won't work if you delete the first element. You need to update list->first.

[val24]

Thanks for taking your time dhayden. As for the function, I know it won't delete the first or last properly. I wanted to test it out on a node that is != first or last, just to know that the delete mechanism works at all. I will post my populate function below and my structs as declared in my header file.

As for my delRec(), I am trying to delete without a temp variable. I don't think I have seen any examples where a node is not deleted without a temp variable. I wanted to try it without the temp variable because to my logic it should be able to work without the temp. If that proves false, I will switch it to include a temp variable.

Note, my populate is missing deletions.

typedef struct sentry sentry; 

struct data{
    string isbn;
    long longbn; // integer isbn
};

struct slist {
    int length;
    sentry *first;
    sentry *last;
};

struct sentry {
    slist *list;
    sentry *next;
    sentry *prev;
    data *record;
};

void populate(slist* list)
{
    // node / body
    sentry *entry, *t, *first;
    entry = new sentry;
    
    // separate struct to hold info
    entry->record = new data;
    t = entry;
    first = entry;
    
    // Full initialization of the header node.
    list->first = entry;
    list->last = entry;
    list->length = 0;
    
    entry->prev = NULL;
    entry->next = NULL; // Avoids a memory leak.
    entry->list = list;
    
    int i = 1;
    while(i <= 8){ 
        entry = new sentry;        // Create new node and 
        entry->record = new data; // create its sub struct.
        list->length = i;   
        entry->list = list;        // Point to header node.
        list->last = entry;        // Point header node to last member of DLL. 
    
        // Will need to update this to include author and book. 
        cout << "Enter n->record->isbn: "; 
        getline(cin, entry->record->isbn);
    
        inputCheck(entry);
        cout << '\n';    
        entry->prev = t; // Connect current node to the previous.
        t->next = entry; // Connect previous node to current node.
        t = entry;       // Previous node is now current node. 
        entry->next = NULL; // The current node's next now points to a dark abyss.
        i++;
    }
    sort(list);
}

[dhayden]

Your populate function sets the isbn field, but the delRec() function is looking for the longbn field.

Ah ha! I found the problem with delRec. There's a semicolon at the end of line 31 in your original post. So the code basically says:

if (this node matches) then do nothing
{
    remove the current node
    break;
}

Once you get your code working, consider these things:

- Why does sentry contain a pointer to data instead of a data object directly?
- Your populate() code is confusing. The code inside the loop keeps bouncing around between setting members of entry, entry->record, and list. Try to straighten that out. Adding a constructor to sentry() would really help.
- It would also help if you created a function to add an ISBN to the list. Have populate() call this fuction. Right now the code relies on variable t when it shouldn't.
- variable first in populate() is unused.

[val24]

HAH! A damn semicolon. Well that's something I didn't know would happen. Thank you for all the help you put in. The struct formatting is something our professor wanted us to use. I personally would've put the data into the same struct containing the pointers. I'll go ahead and clean up the rest of the code with the advice you gave. It's my first time using pointers and structs so this project was really an eye opener. Thanks again, I probably would've rewritten the whole delRec function. The string is input with a format containing a dash, I then convert that to a long without the dash and use that as the index for each node. Really stoked that delRec is working without a temp variable. I'll go ahead and mark the topic as solved:D