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

The debugger is your friend, use it to step through the code line by line. — Some programmer dude
– Some programmer dude, Commented Feb 15, 2013 at 9:13
If the results aren't what you expected then either your expectations are wrong, or you're not doing it right. — Open AI - Opting Out
– Open AI - Opting Out, Commented Feb 15, 2013 at 9:16

Arne Mertz · Accepted Answer · 2013-02-15 09:31:44Z

2

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?

edited Feb 15, 2013 at 9:31

answered Feb 15, 2013 at 9:24

Arne Mertz

24.7k4 gold badges56 silver badges91 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

User14229754 Over a year ago

the elements should be in ascending order.new item should be smaller than the next item.

Arne Mertz Over a year ago

So, your algorithm should be: 1: search for the first bigger item, 2 insert new item before it. Special case: there's no bigger item in the list. 2 has two cases as well: 2a first item in the list is already bigger than the new one, 2b first bigger item is later in the list. In total, you have 3 cases. Identify which case you have and handle the insertions accordingly.

Collectives™ on Stack Overflow

Sorted Insert in doubly linked list

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related