• 03-30-2005
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! :)

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 :cool:
• 03-30-2005
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:

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;```
• 03-30-2005
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?
• 04-04-2005
The Brain
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.         */ }```

`while(temp->price > input->price && temp!=NULL)`
`while( temp && temp->price > input->price )`