Sorted Insert in doubly linked list

Question

I am making a doubly linked list using a struct ListItem which has prev and next pointers and a value of type T.

Am I doing it right?

When I run the main code, I can see only 1, 15, and 16 in the display.

template <class T>
void List<T>::insertSorted(T item)
{
    ListItem<T> *node=new ListItem<T>(item);
    if (head==NULL)
    {
         head=node;
    }          
    else if (head!=NULL)
    {
         T c,d;
         ListItem<T> *temp,*temp2;
         temp=head;
         c=temp->value;
         int count=0;
         while (temp->next!=NULL)
         {
               if (temp->prev!=NULL)
               temp2=temp->prev;

               if (c>item && item>temp2->value)
               {
                    if (temp->prev!=NULL)
                    {
                         temp2->next=node;
                         node->prev=temp2;
                         node->next=temp;
                         temp->prev=node;     
                         count++;
                    }  
                    else if (temp->prev==NULL)
                    {
                         head=node;
                         head->next=temp;
                         count++;
                    }              
               }
               temp=temp->next;
               c=temp->value;
         }
         if (temp->value<item)   //comparison with last temp
         {
             temp->next=node;
             node->prev=temp;
         }
         else if (temp->value>item)
         {
              temp2=temp->prev;
              temp2->next=node;
              node->prev=temp2;
              node->next=temp;
              temp->prev=node;
        }
    }        
}
int main()
{
    List<int> Mylist;
    for (int i=16;i>0;i--)
    {
        Mylist.insertSorted(i);  //insertion should be in ascending order according 
                                  //to my fnction
    }
    Mylist.printList();  //prints the whole linked list
    system("PAUSE");
    return 0;
}

Answer 1

No, what you are doing is UB. Given head != NULL and head->next != NULL, meaning you have at least two items in the list:

 else if (head!=NULL)
 {
      T c,d;
      ListItem<T> *temp,*temp2; //temp2 points to nirvana
      temp=head;                //temp is head
      c=temp->value;            
      int count=0;
      while (temp->next!=NULL)  //head->next != NULL, so enter the loop
      {
            if (temp->prev!=NULL)  //head->prev is NULL...
              temp2=temp->prev;    //.. so temp2 continues to point into nirvana     

            if (c>item && item>temp2->value) //take nirvana's value. OUCH!

Restructure your code. Lay out your algorithm on paper, look what it should do in different cases (no elements in list, one element in list, two or more elements, item is smalles, item is biggest, or item is somewhere in between). If you got it right on paper, write it down in code.

Edit: Hint: I suppose the list is sorted before. What property should the list element have, before which you want to insert the new item? And how can you find it?