LinkList C++ Deleting node

Question

I have a problem when deleting the node in the middle. If i put a position in the middle all the previous node will be gone can anyone help me please thanks!

It doesn't have any problem if i delete the front one but in the middle part will have some problem.

I am stuck right now.

 #include<iostream>
 #include<string>
 #include <limits>
using namespace std;
struct Student{
    string name;
    int matricNo;
    string course;
    double cgpa;
    Student* link;
};

int main(){
    Student *head = NULL, *last, *newStudent, *target;
    int menu = 0;
    int select;
    while(menu != 6){
    cout << "Student Database.\n";
    cout << "1.Add a student.\n";
    cout << "2.Delete a student.\n";
    cout << "3.View a student's information.\n";
    cout << "4.View all students' information.\n";
    cout << "5.View all students' information with CGPA of 3.0 or higher.\n";
    cout << "6.End program.\n";
    while(!(cin >> menu)){
        cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        cout << "Invalid input.\n";
    }
    if(menu == 1){
    newStudent = new Student;

    if(head == NULL)
        head = newStudent;

        cin.clear();
        cin.ignore(2000,'\n');
        cout << "Please enter the student's name : ";
        getline(cin, newStudent -> name);
        cin.clear();
        cout << "Please enter the Matric Number     : ";
            while(!(cin >> newStudent -> matricNo)){
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            cout << "Invalid input. Please enter a number.\n";
        }   
        cin.clear();
        cin.ignore(2000,'\n');
        cout << "Please enter the Course    : ";
        getline(cin, newStudent -> course);
        cin.clear();
        cout << "Please enter the student's CGPA : ";
            while(!(cin >> newStudent -> cgpa) || newStudent -> cgpa > 4 || newStudent -> cgpa < 0){
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            cout << "Invalid input. Please enter a value between 0.00 and 4.00\n";
        }
        newStudent -> link = NULL;

    if(last != NULL)
        last -> link = newStudent; 

    last = newStudent;
    system("cls");
    }

    if(menu == 2){
        if(head != NULL){
        cout << "Please enter the matric number of a student : ";
        while(!(cin >> select)){
        cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        cout << "Invalid input.\n";
        }
            for(Student* p = head; p != NULL; p = p -> link){
                if(p -> matricNo == select){
                    target = p;
                    if(head != NULL)
                    head = p -> link;
                    target -> link = NULL;
                    delete target;  
                }
            }
        }
        else if(head == last){
            head -> link=NULL;
            last -> link=NULL;
        }
        else
            cout << "No students in the database.\n";
    }
    if(menu == 3){

        if(head != NULL){
        cout << "Please enter the matric number of a student : ";
        while(!(cin >> select)){
        cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        cout << "Invalid input.\n";
        }
            for(Student* p = head; p != NULL; p = p -> link){
                if(p -> matricNo == select){
                cout << "Student's Name  : " << p -> name << endl;
                cout << "Matric Number  : " << p -> matricNo << endl;
                cout << "Course         : " << p -> course << endl;
                cout << "CGPA       : " << p -> cgpa << endl;
                cout << "==================================\n";
                }
            }
         }
        else
            cout << "No students in the database.\n";
    }
    if(menu == 4){
        if(head != NULL){
            for(Student* p = head; p != NULL; p = p -> link){
            cout << "Student's Name  : " << p -> name << endl;
            cout << "Matric Number  : " << p -> matricNo << endl;
            cout << "Course         : " << p -> course << endl;
            cout << "CGPA       : " << p -> cgpa << endl;
            cout << "==================================\n";
            }
        }
        else
            cout << "No students in the database.\n";
    }
    if(menu == 5){
        if(head != NULL){
            for(Student* p = head; p != NULL; p = p -> link){
                if(p -> cgpa >=3){
                cout << "Student's Name  : " << p -> name << endl;
                cout << "Matric Number  : " << p -> matricNo << endl;
                cout << "Course         : " << p -> course << endl;
                cout << "CGPA       : " << p -> cgpa << endl;
                cout << "==================================\n";
                }
            }
        }
        else
            cout << "No students in the database.\n";       
    }
    if(menu == 6)
        return 0;
    }   
    system("PAUSE");
    return 0;
}

Answer 1

When it comes to traversing a singly-linked list for the purpose of finding and deleting some existing node in the list, a simple paradigm shift greatly simplifies the task.

The paradigm shift in question would be to use a pointer to the pointer to each node in the list, instead of a pointer to each node in the list. When you do that, the typical awkward forest of if statement immediately disappears, and gets replaced by a very simple, straightforward, algorithm:

for (Student **p=&head; *p; p=&(*p)->next)
{
    if ((*p)->matricNo == select)
    {
        Student *node= *p;
        *p=node->next;
        delete node;
        break;
    }
}

Answer 2

To delete a node in the middle of a single-linked list like you have, you first need to find the node before the one you want to remove. That's because you need to set its link to the (to be) removed nodes link.

Somewhat graphically, lets say your list looks something like this:

        +--------+     +--------+     +--------+
... --> | Node A | --> | Node B | --> | Node C | --> ...
        +--------+     +--------+     +--------+

Now lets say you want to remove "Node B". To do that you have to make the list look like this:

                    /---------------\
        +--------+  |   +--------+  |   +--------+
... --> | Node A | -/   | Node B | -+-> | Node C | --> ...
        +--------+      +--------+      +--------+

Now "Node A" doesn't link to "Node B", so "Node B" is effectively not in the list any more. That both "Node A" and "Node B" both link to "Node C" doesn't matter since you can't get to "Node B", and also because the next step is to delete the structure for "Node B".

Note that there is a special case when the node you want to remove is the first in the list. You should also be able to handle when no node in the list is found.

---

Of course there are other solutions (as noted by UKMonkey), like using the standard std::list (or the single-linked std::forward_list). So I assume this is only for exercise to learn the basic of how linked lists works.

You could also have a double-linked list, where each node has a link not only to the next node in the list but the previous as well. The principle outlined above is the same though.