Thread: Sorting a linked list

  1. #1
    Unregistered
    Guest

    Question Sorting a linked list

    I've got a test program for a linked list that I intend to use in a large program, and so far I can get it to insert and delete where I want. But I can get it to sort properly, could someone help? MY list is singly linked btw.
    I set it up so that I have two lists, one that holds to original values and another that holds the sorted values.
    Code:
    #include <iostream.h>
    
    class Employee{
      public:
        int data;
    };
    
    class Node{
      public:
        Employee Rec;
        Node *next;
    };
    
    int main(){
      Node *Root = new Node;
      Node *Iterator = new Node;
      Node *Sort = new Node;
      Root->Rec.data=0;
      Root->next=NULL;
      Iterator=Root;
      Sort=Iterator;
    
      for(int i=1; i<10; i++){
        Iterator->next = new Node;
        Sort->next = new Node;
        Iterator=Iterator->next;
        Sort=Sort->next;
        Iterator->Rec.data=i;
        Sort->Rec.data=i;
        Iterator->next=NULL;
        Sort->next=NULL;
      }
    
      Iterator=Root;
      while(Iterator!=NULL){
        cout<<Iterator->Rec.data<<endl;
        Iterator=Iterator->next;
        if(Iterator->Rec.data==5){
          Node *New = new Node;
          New->Rec.data=12;
          New->next=Iterator->next;
          Iterator->next=New;
        }
        if(Iterator->Rec.data==2){
          Iterator->next=Iterator->next->next;
        }
      }
      Iterator=Root; Sort=Root;
      while(Sort!=NULL){
        if(Sort->next->Rec.data > Iterator->Rec.data){
          Iterator->next=Sort->next;
          Sort->next=Iterator;
        }
      }
      Sort=Root;
      while(Sort!=NULL&&Iterator!=NULL){
        cout<<Sort->Rec.data<<"    "<<Iterator->Rec.data<<endl;
        Sort=Sort->next; Iterator=Iterator->next;
      }
      delete Root, Iterator, Sort;
      return 0;
    }
    thanks in advance for the help

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    25
    I'll give you the short answer for now then latter I will post a great example for you. The problem is in how you need to look at the linked list. I would make a LinkList object, have it create a haed and tail node at creation. Then I would pass the address of my objects to the linklist and have it deligate command to the head node. The head node would only have a pointer to the next node in the list(either the tail or and internal node), the head would have 1 method called insert. Insert would take the address passed to it from the linkedlist object and pass it to its Next->Insert(&Employee). This call it will be to the tail node. The tail node catchs any calls to it and says"Hey Im at the end, nothing comes after me. So you will be inserted before me." It will create a new internal node, give the address of the employee to it,assign the headnodes Next pointer to the internal node, and set the new nodes next pointer to point to the tail. Now after another Employee object is pass to the linked list it will send it to the head, the head blindly sends it to the next(which now will be the internal node). A compare will be called and if the criteria is met(alphabatised I presume) it will be inserted before the internal node or be pass to the next node to be processed.

    It may sound difficult but I assure you it isn't. I'll send a little source code your way in a little bit so you can run it in a debugger and see what is going on.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM