Linked List Insertion Sort

This is a discussion on Linked List Insertion Sort within the C++ Programming forums, part of the General Programming Boards category; Need your guys's opinion.. do you think this would be a good algorithm for an insertion sort for a double ...

  1. #1
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903

    Linked List Insertion Sort

    Need your guys's opinion.. do you think this would be a good algorithm for an insertion sort for a double linked list..?

    be honest!

    Code:
    void insertion_sort(node* input)
    {
    	node *temp = head_ptr;  //Preserve head_ptr integrity right away
    
    	while((input->price < temp->price) && (temp != NULL))   //Traverse the list until you find out where
                                                                    //user entered price is no longer greater than 
    		temp = temp->next;	                        //a previously entered price..  and return a 
    							        //pointer to the list location.
    
    	//temp should contain the location of the list just previous to one with a greater price
    
    	
    	
    	//This next block of code performs the insertion
    	
    	input->next = temp->next;	//Make the user entered node point to the next node in line
    
    	temp->next  = input;		//Make the current node point to the user entered node
    
    	input->prev = temp;	        //Make the user input node point back to the previous node
    
    }
    How is my syntax?

    Any optimization or other suggestions == good
    Last edited by The Brain; 03-30-2005 at 04:19 AM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  2. #2
    Registered User
    Join Date
    Mar 2005
    Location
    New Zealand
    Posts
    20
    Well I don't think I'm an expert on syntax or anything, but you do have a slight error in there and have forgotten to put one of the links in.

    As far as i can tell, the input should be inserted before temp as temp is the first object in the list that has either the same r higher value than input. so:

    Code:
    //First make input point to the right nodes
    input->next = temp;	
    input->prev = temp->prev;
    
    //Then get the right nodes pointing to input
    temp->prev = input;
    input->prev->next  = input;
    Last edited by FlyingDutchMan; 03-30-2005 at 05:01 AM.

  3. #3
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    If your while loop traverses through the whole list, temp will be NULL, and any code after that dealing with temp will be trying to dereference a NULL pointer which is bad.

    Also, it looks like head_ptr is a global, which would't be a good idea, but maybe you just didn't include all your code.

    When working with linked lists, remember to consider the special cases. What if you're dealing with the head or tail of the list?
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  4. #4
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    how aboot this..??

    Code:
    //Function will add an insert a node into a doubly-linked list in ascending order according to price
    
    
    //All global variables (declared outside of int main())
    //are properly prefaced with the :: scope resolution operator
    
    
    void add_node(node* input)
    {
    	node *temp = ::head_ptr;  //Preserve head_ptr integrity right away
    
    	while(temp->price > input->price && temp!=NULL)			//Traverse the list until you find out where
    															//user entered price is no longer greater than 
    		temp = temp->next;									//a previously entered price..  and return a 
    															//pointer to the list location.
    
    
    	//Handle special case of adding the first node (empty list provision)
    	if(!node_counter)
    	{
    		::head_ptr = input;
    		::tail_ptr = input;
    	}
    
    	//Handle special case of adding to the beginning of the list (head node insertion)
    	if(temp==::head_ptr && ::node_counter)
    	{
    		::head_ptr->prev	= input;
    		input->next			= ::head_ptr;
    		input->prev			= NULL;
    		::head_ptr			= input;	//re-assign head pointer
    	}
    
    	//Handle special case of adding to the end of the list (tail node insertion)
    	if(temp->prev!=::head_ptr && temp->next==NULL && ::node_counter)
    	{
    		::tail_ptr->next	= input;
    		input->next			= NULL;
    		input->prev  		= ::tail_ptr;
    		::tail_ptr			= input;	//re-assign tail pointer
    	}
    
    	//Else perform a regular insertion (node is somewhere in the middle of the list)
    	if(temp->prev!=NULL && temp->next!=NULL)
    	{
    		input->next = temp->next;	//Copy memory location of the next node 
    									//so the new node points to the same location
    
    		input->prev = temp;			//Make the new node point back to the 
    									//node with the lesser price
    
    		temp->next = input;			//Make the lesser price node point to the
    									//insertion node
    
    		temp = input->next;			//Re-assign Temp so it will now point to the
    									//next node in line
    
    		temp->prev = input;			//The next node in line will point back to temp
    	}
    
    	++::node_counter;
    
    	/*	
    
    	Handle circular closure here depending on the programmer's own implementation 
    	of circular linked list theory.
    
    	*/
    
    }



    Feel free to download the properly formatted version
    Attached Files Attached Files
    Last edited by The Brain; 04-04-2005 at 07:15 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    This check is incorrect:
    Code:
    while(temp->price > input->price && temp!=NULL)
    It should be the other way around. Otherwise, you end up dereferencing a null pointer when trying to get price, before checking to ensure that temp is in fact not null.
    Code:
    while( temp && temp->price > input->price )
    Eh... let me fix that in a bit. Too much on my plate right now.

    Quzah.
    Last edited by quzah; 04-04-2005 at 07:24 PM.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  2. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  3. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21