Thread: Problem deleting a node from a linked list

Hello
I am trying to make something by the cprogramming.com tutorial of linked lists. Problem is in the remove function, in the line where I'm trying to "delete conductor".

Anyone see what the obvious misstake is? I'm not really sure how to do this in other ways than this.

Constructive replies appreciated. Thanks in advance


EDIT1:
Please no comments on the goto in the main while loop. its temporary

Here is my code:

Code:

#include <iostream>
#include <cstdlib>
#include <conio.h>
#include <windows.h>
#include <vector>
#include <string>

using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::string;

class Person {
    public:
        int ID;
        string name;
        Person *next;
};
Person *conductor;
Person *root;

void display() {
    int c = 0;
    conductor = root;
    if (conductor != 0) {
        while (conductor->next != 0) {
            c += 1;
            conductor = conductor->next;
            cout << "ID: " << conductor->ID << endl;
            cout << "Name: " << conductor->name << endl;
            cout << endl;
        }
    }
    if (c == 0) {
        cout << "No one added." << endl;
    }    
}    


void remove() {
    
    int found = 0;
    
    int n;
    cout << "-Remove-" << endl;
    cout << "Enter ID: ";
    cin >> n; 
    
    
    conductor = root;
    
    int i = 0;
    while (conductor->next != 0) {
        conductor = conductor->next;
        
        if (n == i) {
            found = 1;
            delete conductor;
        }    
        ++i;
    }   
    
    if (found != 1) {
        cout << "No such ID found." << endl;
    }    
    
}    


void add() {
    conductor = root;
    
    int i = 0;
    while (conductor->next != 0) {
        conductor = conductor->next;
        ++i;
    }   
    
    conductor->next = new Person;
    conductor = conductor->next;
    
    string iname; // input name
    
    cout << "Enter name: ";
    cin >> iname;
    
    conductor->name = iname;
    conductor->ID = i;
    
    cout << "Added." << endl;
    
}    



int main() {
    
    root = new Person; // sets it to actually point to something
    root->next = 0;
    
    root->ID = 1;
    root->name = "Test name";
    
    conductor = root;
    
    while (1) {
        int option;
        cout << "Menu:" << endl;
        cout << "1   add" << endl;
        cout << "2   delete" << endl;
        cout << "3   display" << endl;
        cout << "4   exit" << endl;
        cout << ">> ";
        cin >> option;
        switch (option) {
            case 1:
                add();
                break;
            case 2:
                cout << endl;
                remove();
                break;
            case 3:
                display();
                break;
            case 4:
                goto end;
        }    
    }            
    
    end:
    
    return 0;
}

*grits teeth*...
OK... no comment about the goto then...


I see two major problems in your code:

1) (Not asked about): In your add function, you don't set

Code:

conductor->next = 0

You should, since you use the condition

Code:

(conductor->next == 0)

to determine if you have reached the end of the list.
You could also make a constructor for the Person class that set

Code:

next = 0

.


2)

Code:

    
while (conductor->next != 0) {
        conductor = conductor->next;
        
        if (n == i) {
            found = 1;
            delete conductor;
        }    
        ++i;
    }

I've got a few questions/comments:
(1) Why do you need the variable "i"? I only had a quick look around, but couldn't see where you use it.
(2) For efficiency, use a "break;" statement as the last statement in the "if" above, so that your code looks like this:

Code:

    
while (conductor->next != 0) {
        conductor = conductor->next;
        
        if (n == i) {
            found = 1;
            delete conductor;
            break;
        }    
    }

It will cause the loop to terminate as soon as the item has been found. Also keep in mind that optimized code that doesn't work is worse than worthless - its actually a loss, because you spent time optimizing it.

As for answering your question, I think your problem is that you simply delete the pointer, without linking up the list again. If your linked list is a chain, your remove() function is splitting the chain in two by removing a link, not making the chain shorter by removing a link.

Try something like this: (This is only pseudocode, not c++)

Code:

IF found THEN
  Set conductor to point at the node before the target for removal
  Set temporary Person pointer to point at the node after the target for removal
  Delete conductor->next
  set conductor->next to temporary Person pointer
END IF

This essentially removes the target node and then links up what used to be its two neighbours with each other.
It's been a while since I've programmed a linked list, I could have made a mistake here somewhere.

Question / constructive comment:
Why do you repeatedly use the following construct:

Code:

    if (conductor != 0) {
        while (conductor->next != 0) {
            //  Code...
        }
    }

when you could achieve the same (much more elegantly (and therefore less error-prone)) by simply using:

Code:

    while (conductor->next != 0) {
        //  Code...
    }