Thread: soting a linked list

  1. #1
    Registered User
    Join Date
    Oct 2004
    Posts
    2

    soting a linked list

    I got this function to write within a linked list program to insert a node into an ordered list.

    Pre-condition:head is head of a linked list(NULL if the list is empty)
    the last node has "next" equal to NULL
    Also, the datum fields of the linked list are in ascending order
    Post condition: A node is inserted with "datum" equal to the parameter n, The linked list is still in order.

    Code:
    void InsertNodeInOrderedList(nodeptr& head, int n);
    What I have is:

    Code:
    void insertNodeInOrderedList( nodeptr& head, int n) {
    	int datum1, datum2;
    	nodeptr temp = new node;
    	nodeptr temp2 = head;
    	if(head == NULL) {
    		head = temp;	//set head to new node	
    		temp -> datum = n;	//data in
    		temp->next = NULL;	//next node is NULL
    		
    		
    	}
    	else   //if list is empty
    	{
    		while(temp2->next !=NULL)
    		{
    			temp2 = temp2 -> next;	//next node will be head, if the next node is not of NULL
    		}
    					
    		
    		temp2 -> next = temp;  //set the next node to be the new node
    		temp -> datum = n;  //datum in the new node will be equal to parameter n
    		datum1 = temp2->datum;  //initialize datum1 to be data of the head
    		datum2 = temp2->next->datum;  //initialize datum1 to be data of the next node
    		if(datum1 < datum2){  //test
    			temp2 = temp;  //head will equal new node
    			temp2->next = temp->next;  //next node will equal next new node
    			
    		}
    		temp ->next = NULL;
    		
    		
    	}
    }
    I even put my explanation all over the place to help anyone in figuring what I am thinking. Oh I feel this is needed.

    Code:
    typedef struct node * nodeptr
    
    struct node {
          int datum;
          nodeptr next;
    };

    I have played and played with this thing trying to get it to work. Well it will just put on the input, but not order it. I thought I had the understandment on this down, but I guess not so well. Could someone please give me some help?

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Compare and contrast:
    Code:
    #include <iostream>
    
    struct node {
      int data;
      node *next;
    
      node ( int init, node *link )
        : data ( init ), next ( link )
      {}
    };
    
    node *insert_ordered ( node *list, int data )
    {
      if ( list == 0 ) {
        // Empty list
        list = new node ( data, 0 );
      }
      else if ( data < list->data ) {
        // Head insertion
        list = new node ( data, list );
      }
      else {
        // Internal insertion
        node *it = list;
    
        // Find the end of the list or the first larger item
        while ( it->next != 0 && data > it->next->data )
          it = it->next;
    
        // Insert before the first larger item
        it->next = new node ( data, it->next );
      }
    
      return list;
    }
    
    int main()
    {
      node *list = 0;
    
      for ( int i = 0; i < 10; i++ )
        list = insert_ordered ( list,rand() % 100 );
    
      for ( node *it = list; it != NULL; it = it->next )
        std::cout<< it->data <<' ';
      std::cout<<std::endl;
    }
    Remember to consider all of your possible cases. The first and most obvious case is an empty list. Then you have three cases for ordered insertion: at the head, at the tail, somewhere inbetween. The latter two can be merged together, so the only other special case aside from an empty list is when the new item is smaller than the head.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM