Double Linked List - Node Deletion

Question

Writing a program to work with a double-linked list. The class for it works perfectly, everything is being stored right, nodes are being added, displayed, and searched for right. The problem is deletion. The code for the class and the deleteNode method is below, and for the life of me, I can't seem to figure out why it isn't deleting the proper node.

For instance, say I insert a node with the data "Morgan Captain 666-666-6666" to the end of my linked list, everything turns up when I display it and everything. I have no problem with those methods. But when I attempt to delete the node with the number "666-666-6666," I am turned up with my "Number does not exist" message.

I've drawn out my linked list diagram, an to me it makes sense, but that's obviously not the case in the code. Any pointers?

EDIT: I have gotten a case at the end of the list to work, but nothing doing for the beginning and middle entries of the list. Head node has been taken out as a parameter on all unnecessary functions, as well. Updated code is below.

EDIT 2: Seems the last case doesn't work for nodes that were added to the memory from the read-in function. Updated.

The class and struct:

struct node{
    node* next;
    node* prev;
    string lastname;
    string firstname;
    string phnum;
};

class linkedList
{
    node* n;        // indicator of current node
    node* head;     // head node, does change as needed
public:
    linkedList();
    ~linkedList();
    void choice(char choice);
    void makeList(node* &head);
    void addNode();
    void deleteNode();
    void searchName();
    void searchNum();
    void displayList();
    void writeFile();
};

The deleteNode method:

    void linkedList::deleteNode()
{
    string num;
    node *p, *f;    // To link any nodes back together after deletion.
    n = head;

    // Displays list of nodes to reference.  Function deletes based on phone number string comparison.
    displayList();
    cout << "Please enter the phone number from the list above, as displayed, that you would like to delete:  ";
    cin >> num;

    while (n != NULL)
    {
        // If a number matches
        if (n->phnum == num)
        {
            // If it's the head node - DOES NOT WORK
            if (n == head)
            {
                head = head->next;
                head->prev = NULL;
                delete n;

                cout << "This name and number has been deleted." << endl << endl;
                return;
            }
            // if it's a middle node - DOES NOT WORK
            else if (n->next != NULL)
            {
                p = n->prev;
                f = n->next;
                p->next = f;
                f->prev = p;
                delete n;

                cout << "This name and number has been deleted." << endl << endl;
                return;
            }
            // If it's an end node - WORKS FOR ADDED NODES, NOT DEFAULT ONES
            else
            {
                n->prev->next = NULL;
                delete n;

                cout << "This name and number has been deleted." << endl << endl;
                return;
            }
        }
        //If there is no matching number
        else
            n = n->next;
    }

    cout << "This number does not exist in our system." << endl << endl;

    return;
}

Why do you have head as a parameter of every member function? — user253751
Adding the Struct Node. As for head, it's because it was the only way I could get n to equal head for some reason. Maybe it's an error of coding on my part, but well, if it ain't broke, don't fix it. — Trey Brumley
@TreyBrumley - l, if it ain't broke, don't fix it. It's broke. What happens if the node you delete is the head node? You never reset the head node to the new head node. Go through your code and think why you have to pass this unnecessary parameter, especially since you have a member variable that denotes the head node. — PaulMcKenzie

Gene Gene · Accepted Answer · 2015-02-14T01:48:16

You have handled only the general case of deleting a "middle" element correctly. You must think through the cases where you're deleting the first or last element, determine the "if" conditions that will identify these cases, and use different deletion code to suit. A hint is that passing *head to a deletion routine, as you have done, will not work in all cases. I won't be more explicit so you can continue to learn.

Double Linked List - Node Deletion

1 Answers