CODEWITHSUNDEEP
c++sortingpointerslinked-listcontainer-classes
Stephen Fedewa
Stephen Fedewa

Reputation: 9

Inserting Nodes in to a Linked List in Sorted Order

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]);
    }

}

Upvotes: 0

Views: 952

Answers (2)

Audrey Brooke
Audrey Brooke

Reputation: 99

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.

Upvotes: 2

Misho Tek
Misho Tek

Reputation: 644

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)

Upvotes: 1

Related Questions