Linked list (deleting a node)

Question

My question is if the user enters a last name and there are multiple same last name inside the linked list and one of the last name is in the head node. How am I going to delete one of the other last name without deleting the head node. I tried some ways i can think of but the desired node is deleted (which is good) including the head node (which is not I want..)

void NumberList::deleteCertainRecord()
{
string lname = "";

ListNode *ptr;
ptr = head;
string answer;
cout << "Please enter last name: "<<endl;
cin>>answer;
int num = 0;
char confirm;
while (ptr!= NULL){
    lname = ptr -> data.person.getLastName();

    if(lname == answer){
        num++;
        cout << "Person found : ";
        cout << ptr->data.person.getTitle()<<" " << ptr -> data.person.getFirstName() << " " << ptr -> data.person.getLastName() << endl << endl;
        cout << "Do you want to delete his/her record? [Y/N]" << endl;
        do{
            cin >> confirm;
            if(confirm=='Y'||confirm=='y'){
                    ListNode *previousNode;

                    if(isEmpty()){
                        return;
                    }

                    else if(head->data.person.getLastName() == answer){
                        ptr = head->next;
                        delete head; 
                        head = ptr;
                    }

                    else{
                        ptr = head;

                        while(ptr!=NULL && ptr->data.person.getLastName() != answer){
                            previousNode = ptr;
                            ptr = ptr->next;
                        }

                        if(ptr==NULL){
                            cout<< "Node not found!" << endl;
                            return;
                        }
                        else{
                            previousNode->next = ptr->next;
                            delete ptr; 
                        }
                    }
                    cout << endl << "Deleting..."<<endl;
                    cout << "Done!!" <<endl;
                    cout << "Exiting delete function... "<<endl;
                    return;
            }
            else if(confirm=='N'||confirm=='n'){
                break;
            }
            else{
                cout << "invalid input, please enter again!!" << endl;
            }
        }while(confirm!='Y'&&confirm!='y'&&confirm!='n'&& confirm!='N');
        cout << endl;
    }

    ptr = ptr -> next;
}
if (num == 0){
    cout << "\nNo person with the last name ("<< answer << ") was found!" << endl;
    cout << "Exiting delete function... "<<endl;
    return;
}
}

Answer 1

The sheer amount of code your doing this with is clouding the actual intent.

• You have a linked list of people.
• Given a last name you want to enumerate the list looking for matches.
• Upon discovering a match, you want to prompt the user for deletion confirmation
• If confirmed to delete, extricate the discovered node, leaving the list otherwise-intact, and delete it.
• Else if not confirmed, skip to the next node, looking for more matches

You're apparently having a problem with the deletion portion if the node is, in fact, the head node. Special-cased head-node logic is always tricky for people new to linked lists. Fortunately it can be circumvented entirely if you use the right algorithm. Assuming your list is properly terminated with NULL, including a NULL head pointer if the list is empty, such an algorithm is below:

ListNode ** pp = &head;
while (*pp)
{
    if ((*pp)->data.person.getLastName() == answer &&
         confirmDelete((*pp)->data.person)) // <== TODO: write this function
    {
        ListNode *victim = *pp;
        *pp = victim->next;
        delete victim;
    }
    else
    {   // just advance to next person
        pp = &(*pp)->next;
    }
}

This will properly delete the user even if they're the first node in the list and properly advance the head pointer for you. It also works on single-node lists both with and without matching conditions, and even empty lists where head is NULL. This technique uses the pointers in the list as the mechanism for enumerating the list; not just their values, the actual pointers.

Lastly, this can be made considerably more efficient if you keep the list sorted, but I leave that to you.