Help with Insertion sort on a single linked list

Hi everyone,

I am trying to write a program involving adding nodes to a single linked list and allowing the user to enter the names of students and the student numbers up to as many as they wish. I want to add the nodes that the user enters to the list so that the entire list of data is sorted by student number in ascending order including the student data which is NOT entered by the user (which are the five initialized students in main() before we get any data from the user). It is set up so that the list is displayed before and after EVERY time a student is added to the list by the user. I have sorted stuff many times with arrays before but this is my first time doing it with linked lists so I was wondering how I can go about doing this in my code which is listed below:

Code:

---


#include <iostream>
#include <string>
#include <stdlib.h>

struct link {
    int stnum;
    string name;
    link *next;
};

class linklist {

  private:
      link *first;

  public:
      linklist() {
        first = NULL;
      }
    void additem(int s, string n);
    void display();
};

void linklist::additem(int s,string n) {
    link * newlink = new link;
    newlink -> stnum = s;
    newlink -> name = n;
    newlink -> next = first;
    first = newlink;
}

void linklist::display() {
    link *current = first;
    while(current != NULL) {
        cout << current->stnum << "  " << current->name <<endl;
        current = current -> next;
    }
}

int main() {
    int numstud, i;
    int stunum;
    string sname;
    linklist student;
    student.additem(1315,"Mary");
    student.additem(1307,"John");
    student.additem(1293,"Kim");
    student.additem(1270,"Marty");
    student.additem(1258,"Linda");
    cout << "Enter # of students you wish to add to the list: ";
    cin >> numstud;
    cout << endl;
    for (i = 0; i < numstud; i++) {
      cout << "Enter the student number: ";
      cin >> stunum;
      cout << endl;
      cout << "Enter the student name: ";
      cin >> sname;
      student.additem(stunum, sname);
      student.display();
    }
    cin.get();
    return 0;
}

---

Any assistance would be greatly appreciated. Thanks.

Code:

---

#include <stdlib.h>

---

Use this instead:

Code:

---

#include <cstdlib>

---

A helpful thing would be to have a constructor for your link class/struct so it can set the elements for you:

Code:

---

struct link {
    int stnum;
    string name;
    link *next;
    link(int _stnum, string _name) : stnum(_stnum), name(_name), next(0) {}
};

---

This will help you clean up some of your insert code.

You also need a destructor for your list class that walks through the linked list and deletes all the allocated memory.

Your additem function simply needs to move to the correct position in the list and insert at that location:

Code:

---

void linklist::additem(int s,string n) {
    // Easier creation of a new link due to link's constructor
    link * newlink = new link(s,n);

    // Check if we need to insert this node at the very beginning of the list
    if( !first || first->stnum > s )
    {
        newlink->next = first;
        first = newlink;
    }

    // Otherwise we need to insert the node elsewhere into the list
    else
    {
        link* temp = first;
        while( temp->next && temp->next->stnum < s )
            temp = temp->next;
        newlink->next = temp->next;
        temp->next = newlink;
    }
}

---

The above code is not tested so I don't know if it works but it should at least give you a start in the right direction.

Thanks for the suggestions.

I'm pretty busy at the moment with other things so I may not get a chance to try anything with the program tonight but I will get to it tomorrow.

Thanks.

Here's a question I have. If you know the answer, drop a reply.

Would I be able to use an overloaded operator(+) method instead of the additem() method to add a node to the linked list?

Thanks.

Probably, but it might not be good design. You generally want overloaded operators to mimic how built-in datatypes use them. If you think this is true in this case then go ahead.

You should implement operator+=, which makes more sense for a list anyway.

Eventually you will want to implement a destructor, copy constructor, and copy assignment operator (operator=) to get rid of the memory leaks in your code. Once you do that you can implement operator + in terms of operator+=.