sort linked list

[ruval002]

so i have the following code, it inserts a number to a list and then i call my sort function which is below this function, the problem is that my sort function takes forever, is there a way i can implement my insert function so that everytime it inserts a number it inserts it on the correct place

for example

myq.insert(2);
myq.insert(5);
myq.insert(4)
myq.display(); // after this is called it should display 2 4 5

void LL::insert(int NewNum)
{

  if(rear == NULL)//CASE:1(if rear is null)                                    
    {
      front = rear = new PCB;
      rear->id = NewNum;
    }
  else//CASE:2(if the list is not empty)                                       
    {
      rear->next = new PCB;
      rear = rear->next;
      rear->id = NewNum;
      rear->next = NULL;
    }
  

  count++;
}

void LL::sort()
{
  int i,j,m,n=0,hold;
  PCB *q, *p, *t;
  for(PCB*q = front ; q ; q=q->next)
    ++n;

  for(i=1 , t = front  ; i<=n-1 ;  t = t->next , ++i)
    for( j=0 , p = front  ; j<n-i ;  p = p->next , ++j)
      if(p->id > (p->next)->id)
        {
          hold = p->id;
          p->id = (p->next)->id;
          (p->next)->id = hold;
        }
}

[Ancient Dragon]

>>is there a way i can implement my insert function so that everytime it inserts a number it inserts it on the correct place

Of course there is. Just start at the beginning of the list and check each node for a value that is either < or > the newvalue (depending on whether you want ascending or descending sort). If found, then insert the new node in the correct location, adjusting next pointers as necessary. If not found then the new node just goes at the tail of the list.

[ruval002]

how would i start to do that?
would it be faster than using my sorting algorithm? i have to do a test where insert is called over a million times

[Kanoisa]

the problem is that my sort function takes forever

Have you checked the logic of your sort function to make sure it does not result in an infinate loop? For a sort function to take "forever" you would need a very large amount of data or there is a problem with the sorting algrotihm.

I think your sort implementaion may have problems. I would suggest looking at it first before looking else where.

[ruval002]

it does work, i test it. It just that when repeating it a thousand times it takes forever. Is there any other faster sorting algorithms i can use?

[Kanoisa]

Have you came across binary search / sort? and other more advanced search / sort functions? Iv never tried to impliment one of them but there are lots of sorting algorithms each with thier individual merits.

Try looking at resources such as this one http://www.sorting-algorithms.com/ to try get a feel for which algorithm will work best for your data.

[Ancient Dragon]

If you are going to add thousands of nodes to the linked list then don't sort anything until after all the nodes have been added. Then sort only once.

[WaltP]

I've never understood all this sorting of linked lists. Why not just add the node between the nodes containing the values above and below the new node? Just add them in their sorted position!

[Ancient Dragon]

I've never understood all this sorting of linked lists. Why not just add the node between the nodes containing the values above and below the new node? Just add them in their sorted position!

That would be ok for small lists, but this one will contain thousands of nodes. In that case it will be a lot faster to just add new nodes to the tail of the list and then sort it when its all done.

[WaltP]

If you say so. I'm dubious.

[Ancient Dragon]

I wrote a test program to test my theory. The program contained two test cases, both created a linked list with 100,000 nodes and called clock() to time each of them.

case 1: linked list that inserted new nodes in correct places, searched sequentially from the beginning of the list and stopped when the correct position was found.

case 2: Inserted all new nodes at the tail end of the list, then used bubble sort algorithm to sort them.

Result: case 1 = 83413 clock ticks, case 2 = 37,753 or less than have the time of case 1. The time difference could be even greater had I used a more efficient sort algorithm.

#include <ctime>
#include <iostream>
#include <cstdlib>

struct node
{
    struct node* next;
    int data;
};

const int MaxItems = 100000;

void insert(struct node**head, int newdata)
{
    struct node* n = new struct node;
    n->data = newdata;
    n->next = NULL;
    if( *head == NULL)
        *head = n;
    else
    {
        struct node* curr = *head;
        struct node* prev = curr;
        while( curr && curr->data < newdata)
        {
            prev = curr;
            curr = curr->next;
        }
        if(curr == *head)
        {
            n->next = *head;
            *head = n;
        }
        else
        {
            n->next = prev->next;
            prev->next = n;
        }
    }
}

void ShowList(struct node*head)
{
    while(head->next)
    {
        std::cout << head->data << '\n';
        head = head->next;
    }
}

void FreeList(struct node** head)
{
    struct node* n = *head;
    while(n)
    {
        struct node* h = n;
        n = n->next;
        delete h;
    }
    *head = NULL;
}

void CreateList1()
{
    struct node* head = NULL;
    clock_t t1, t2;
    t1 = clock();
    srand((unsigned int)time(0));
    for(int i = 0; i < MaxItems; i++)
    {
        insert(&head, rand());
    }
    t2  = clock();
    std::cout << "List1: " << t2-t1 << '\n';
//    ShowList(head);
    FreeList(&head);
}


void CreateList2()
{
    clock_t t1, t2;
    struct node* head = NULL;
    struct node* tail;
    t1 = clock();
    for(int i = 0; i < MaxItems; i++)
    {
        struct node* n = new struct node;
        n->data = rand();
        n->next = NULL;
        if( head == NULL)
        {
            head = tail = n;
        }
        else
        {
            tail->next = n;
            tail = n;
        }
    }
    // sort the list
    struct node*n1 = head;
    while( n1->next->next )
    {
        struct node* n2 = n1->next;
        while(n2->next)
        {
            if( n1->data > n2->data)
            {
                int h = n1->data;
                n1->data = n2->data;
                n2->data = h;
            }
            n2 = n2->next;
        }
        n1 = n1->next;
    }
    t2 = clock();
    std::cout << "List2: " << t2-t1 << '\n';
    std::cout << "\n\n";
    //ShowList(head);
    FreeList(&head);

}


int main()
{
    CreateList1();
    CreateList2();
}

[WaltP]

Result: case 1 = 83413 clock ticks, case 2 = 37,753 or less than have the time of case 1. The time difference could be even greater had I used a more efficient sort algorithm.

Aha -- that's why! Thanks for clearing that up.

[Fortran IV]

I agree that the best way is to put the node where it belongs in the list in the first place. Linked lists should always be ordered in some way. If they are not ordered, then a linked list is the wrong data structure to be using. You should have a “Put” or “Insert” function that reads the index of the first node and compares it to the element to be inserted. If it is not the location for the new value, use the link in the node to go to the next node. As soon as it finds the correct location for the new node, it breaks the links between the existing nodes, and inserts the new node. It then completes and is ready for the next piece of data. This should be very fast. For a list with 100 existing nodes, adding 100 nodes, you would have to check an average of about 75 nodes per each new node. That is, the first new node would have to check an average of 50 nodes (half the original 100 on the list) until it found its location. The second new node would have to check and average of 50 ½, since the list has 101 nodes, and so on. The last new node (the 200 on the list) checks an average of 99 ½ nodes. There are also 100 “insertions” where the links are broken and reconnected. The “insertion” is typically much computationally intensive than the comparison. This is an average of 750 comparisons and 100 insertions to add 100 nodes.

By appending all the nodes to the end, and then sorting the entire list, you have to do 100 insertions right off the bat. You then have to sort each node on the list (200) against a list of 200, for an average of 100 comparisons per node. You also have to insert each node in the new location. 100 initial insertions + 100 sort insertions = 200 insertions. 200 nodes x 100 (average) comparisons = 20000 comparisons. Of course, that assumes a very efficient sort algorithm. Which leads me to the next point:

You sort algorithm is not very efficient. For one thing, it compares each new node against each existing node, until it finds the new location. It then inserts the new node. And then it continues on through the rest of the list anyway! I suspect that your algorithm may actually put multiple copies of nodes in the list. This could be why it is so slow. You should be able to find a much better sort algorithm. Google “Bubble Sort” or “Shell Sort”. Different sort algorithms work better for different data structures and data. I don’t recall which is best for a bubble sort. In theory, a properly maintained linked list does not need to be sorted, but a prudent programmer writes a sort function for it anyway.

I’m not sure they even teach sorting algorithms any more. Now it is all relational databases. Back when I learned linked lists, sorting seemed to be one of the main ways computers were used. No one used relational databases. That could be because it was really hard to implement a relational database with punched cards…

Let me talk about a misconception. In human terms, it sounds more efficient to “Put all the new data at the end” and “Sort the whole list once” than to “Read through the list to figure out where each items goes” and “Do this for every new item”. And for a human, it is more efficient to do things that way (It is actually easier to sort all the new elements, and then merge them into the existing elements. My Work Study job involved a lot of mindless filing, and I had a lot of time to think about more efficient ways to do it.) Humans are very slow with looking at two items and comparing them. Computers on the other hand, are very fast at comparing things, especially numbers (Strings are a lot slower). Moving things around tends to be slower. Always try to think about things in terms of how a computer actually does its processing. It is well worth it for a beginning programmer to learn about the inner workings of computers.

[Ancient Dragon]

>>Let me talk about a misconception. In human terms, it sounds more efficient to “Put all the new data at the end” and “Sort the whole list once” than to “Read through the list to figure out where each items goes” and “Do this for every new item”.

Good in theory, but it doesn't work like that. For linked lists with large number of nodes it is more efficient to sort at the end, as my previous post proved. Compile and run the program yourself to see the difference. The time difference becomes even greater as more and more items are inserted. I'm not saying you should sort at the end for every linked list -- only those with lots of nodes.

>>No one used relational databases. That could be because it was really hard to implement a relational database with punched cards
Apparently someone used them because they came into use during mid-1960s -- like shown in this wiki article. But you may be right if you was programming before then.