Inserting Nodes in to a Linked List in Sorted Order

Question

I need help inserting data from class node into a linked list. List is a container for nodes. They need to be sorted based on last name, then first name, and age. (I already have operator functions to compare them) I'm just not sure how to use the pointers to insert and sort them. Below are my two class definitions, and what I have for my insert function so far. I also provided a potential selection sort algorithm from a previous project that could be tooled to work with this. Can anyone help?

//Class Declarations

 class node;
    class list
    {
    public:
    void insert(string f, string l, int a);
    int length();

private:
    node *head;
    int listlength;
};
class node
{
    friend list;
public:
    node();                           // Null constructor
    ~node();                          // Destructor 
    void put(ostream &out);           // Put
    bool operator == (const node &);  // Equal
    bool operator < (const node &);   // Less than
private:
    string first, last;
    int age;
    node *next;
};

//How insert is called in MAIN

while (!infile.eof())
        {
            infile >> first >> last >> age;

            // Process if okay

        if (infile.good())
            a.insert(first, last, age);
        };

//Insert Function

  void list::insert(string f, string l, int a)
        {
        node *temp1, *temp2 = head;
        temp1 = new node();
        temp1->first = f;
        temp1->last = l;
        temp1->age = a;
        temp1->next = NULL;
        if (listlength == 0)
        {
            temp1->next = head;
        }
        else
            while (temp2->next != NULL)
            {
                ;
            }

    }

//Potential sort algorithm

 void sort(person b[], int count)
{
    int i = 0, j = 0, indexofsmallest = i;
    person smallest = b[i];

    for (i = 0; i < count; i++)
    {
        smallest = b[i];
        indexofsmallest = i;

        for (j = i+1; j < count; j++)
        {
            if (b[j] < smallest)
            {
                smallest = b[j];
                indexofsmallest = j;
            }
        }

        //cstdlib swap function

        swap(b[i], b[indexofsmallest]);
    }

}

Unrelated: You have avoided part of the the `while (!infile.eof())` trap. Great job, but you need to add an else case to `if (infile.good())` to clear the error and remove the unparsable data from the stream. If you do not the program will never reach the end of the file and loop forever. — user4581301, Oct 19 '17 at 20:52
In `list::insert` if you add to `while (temp2->next != NULL)` a check for `*temp2 < *temp1` you are most of the way to finding the correct insertion point. — user4581301, Oct 19 '17 at 20:55

Audrey Brooke · Answer 1 · 2017-10-19T20:35:00.867

If you really want to sort a linked list, which is not recommended, you would have to adjust your algorithm to work with pointers instead of array indices. This would look something like this:

void sort(node* head, int count)
{
    // int i = 0, j = 0,
    node* smallest = head;

    while (head != NULL)
    {
    smallest = head;
    node* toTest = head->next;
    while (toTest != NULL)
    {
        if (toTest->age < smallest->age)
        {
            smallest = toTest;
        }
        toTest = toTest->next;
    }

    //make your own swap function

    pointerSwap(head, smallest);

    head = head -> next;
}

}

You could write your own swap algorithm that applies to pointers, this might be difficult unless you keep track of the item before the ones your sending in the list.

score 1 · Answer 2 · answered Oct 19 '17 at 20:01

Because of not having quick access to every element in the linked list, all regular sorting algorithms will take too much time, especially in the singly linked list, so one approach will be to just keep list sorted in the process of insertion. Worst case O(n^2)

Inserting Nodes in to a Linked List in Sorted Order

2 Answers2