Problem deleting a node from a linked list

This is a discussion on Problem deleting a node from a linked list within the C++ Programming forums, part of the General Programming Boards category; Hello I am trying to make something by the cprogramming.com tutorial of linked lists. Problem is in the remove function, ...

  1. #1
    Registered User
    Join Date
    Feb 2005
    Location
    oslo
    Posts
    26

    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;
    }
    Last edited by Dag_; 03-17-2005 at 03:38 AM.
    life is too short smart but hard !

  2. #2
    Registered User
    Join Date
    Mar 2002
    Location
    South Africa
    Posts
    35
    *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...
        }
    I code.
    I think.
    Ergo, I think in code.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  2. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 12:21 PM
  3. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 06:47 PM
  4. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21