Linked List Insertion Sort

[The Brain]

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!

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

[FlyingDutchMan]

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:

//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;

[joshdick]

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?

[The Brain]

how aboot this..??

//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

[quzah]

This check is incorrect:

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.

while( temp && temp->price > input->price )

Eh... let me fix that in a bit. Too much on my plate right now.

Quzah.