Thread: Help with Insertion sort on a single linked list

  1. #1
    Registered User
    Join Date
    Nov 2004
    Posts
    73

    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.

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User
    Join Date
    Nov 2004
    Posts
    73

    Re:

    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.

  4. #4
    Registered User
    Join Date
    Nov 2004
    Posts
    73
    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.

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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+=.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  4. Linked List Merge Sort
    By LostNotFound in forum C++ Programming
    Replies: 2
    Last Post: 02-17-2003, 10:34 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM