I need help sorting this double linked list (C++)

Question

This is what I have so far:

void sort(const E &t)
{
  DNode<E> *tmp = new DNode<E>(t,NULL,NULL);


    if(size==0)
    {
        cout << "List is empty" << endl;
    }

            else if(t<=head->element)
            {
                tmp->element=t;
                head->prev = tmp;
                tmp->next=head;
                head = tmp;
            }
                    else if(t>=tail->element)
                    {
                        tmp->element=t;
                        tail->next = tmp;
                        tmp->prev=tail;
                        tail = tmp;
                    }

                         curr=tmp;
                         insert(t);
                         size++;
}

insert() is just another function in my program:

 void insert(const E &t)
{
  DNode<E> *tmp = new DNode<E>(t,NULL,NULL);
  if (size == 0)
  { curr=head=tail=tmp; }
  else 
  {
    tmp->next=curr;
    tmp->prev=curr->prev;
    if (curr->prev) curr->prev->next=tmp;
    else { head=tmp; }
    curr->prev=tmp;
    curr=tmp;
  }
  size++;
}

It does compile, but it doesn't give the correct results. I'm not sure what my errors are, and I would really need help. Any help would be appreciated.

This is in my main program:

  one.sort(10);
  one.sort(20);
  one.sort(30);
  one.sort(40);
  one.sort(50);
  one.sort(60);
  one.print();
  one.moveToEnd();
  one.prev(); 
  one.prev();
  one.remove();
  one.remove();
  one.print();

  cout<<endl;

I should be getting this:

HEAD==> 10 -> 20 -> 30 -> 40 -> 50 -> 60 <==TAIL HEAD==> 10 -> 20 -> 50 -> 60 <==TAIL

But I get this instead: HEAD==> 10 -> 20 -> 20 -> 30 -> 30 -> 40 -> 40 -> 50 -> 50 -> 60 -> 60< ==TAIL HEAD==> 10 -> 20 -> 20 -> 30 -> 30 -> 40 -> 40 -> 60 -> 60 <==TAIL

@jogojapan for my clarification, what do they suggest you replace that tag with/use? — M4rc, Oct 25 '12 at 02:45
@M4rc The advice is not to use it at all - either a question has merit or it does not - rather than a specific solution to some homework question. Generally specific answers to homework are not welcome anymore — Adrian Cornish, Oct 25 '12 at 02:46
I can't see any loop nor recursion in your code. How are you supposed to sort a list without them? Is the length of the list known "a priori" or what else? — akappa, Oct 25 '12 at 02:48
@M4rc As Adrian said. Also, I should have linked to this: http://meta.stackexchange.com/questions/147100/the-homework-tag-is-now-officially-deprecated — jogojapan, Oct 25 '12 at 02:49
@AdrianCornish Appreciated, I was curious. I just look at the few that do tag it and I do realize why they're not using STL, or other methods because of it and was wondering if there was a replacement to it jogojapan: I appreciate the link I will review to expand my understanding of the situation. — M4rc, Oct 25 '12 at 02:51
When you step through your code, at what line does the data structure no longer contain the correct value? That's the line with the bug. — Raymond Chen, Oct 25 '12 at 02:55
I guess SO doesn't want programming professor to work to hard rewriting their assignments all the time ;-) — Adrian Cornish, Oct 25 '12 at 02:58

femtoRgon · Accepted Answer · 2012-10-25T03:28:56.787

The cause of the behavior you're seeing is that your missing an else

this:

curr=tmp;
insert(t);
size++;

is executed whether you have added something to the head or tail, or not. Since each entry you give will be added to the tail, it gets inserted twice each time. You should only call insert if you have not yet added the value to the head or tail.

If I understand correctly, curr=tmp; and size++; should be run regardless, so only the call to insert should be inside an else block, I think.

EDIT:

Should look like this:

if(size==0)
{
    cout << "List is empty" << endl;
    //Need to insert here as well, to add the first value to the list.
    insert(t);
}

        else if(t<=head->element)
        {
            tmp->element=t;
            head->prev = tmp;
            tmp->next=head;
            head = tmp;
        }
                else if(t>=tail->element)
                {
                    tmp->element=t;
                    tail->next = tmp;
                    tmp->prev=tail;
                    tail = tmp;
                }

                else 
                {
                     insert(t);
                }
                curr=tmp;
                size++;

I've (kinda) maintained your whitespace usage, though I find it a bit unusual, by the way. I would normally place related 'if' 'else if' and 'else' statements on the same indention level, and indent further for nested blocks. I think that's more standard, but neither here nor there.

Odd. Are you reordering those three statements to place the insert first, directly after the last 'else if' block? It should come first, in an 'else', followed by the other two statements. If you didn't order it in that way, then you would indeed see a syntax error. Edited my answer to clarify my meaning. Is that what you had? — femtoRgon, Oct 25 '12 at 03:04
Yes, that's what I had. I'm not sure what the problem is. It says the list is empty, and then it crashes. — Exn, Oct 25 '12 at 03:19
Ah, sure it does. Hadn't really thought about it. Since we aren't getting that second insert, you're never getting a first value added to your list. In that first if block, handling the empty list, you should insert the first value into your list, rather than just drop it. Calling insert in that block as well should fix the problem, since you've created the logic to handle that case already in the insert function. I'll modify the code above to reflect that. — femtoRgon, Oct 25 '12 at 03:27

score 0 · Answer 2 · answered Oct 25 '12 at 02:52

Hope this helps:

    struct node {
       node* next;
       node* prev;
       Person p;
    };

    void sort(node* head) {
       node* n1;
       node* n2;

           for(n1 = head; n1->next != head; n1 = n1->next) {

                for( n2 = n1->next; n2 != head; n2 = n2->next) {

                       // swap data here if necessary
                 }
           }
      }

For swapping:

     X1 = currPtr->previoius;
     X2 = currPtr->next->next;
     currNext = currPtr->next;
     currNext->previous = currPtr->previous;
     currPtr->previous = currPtr->next;
     currPtr->next = currNext->next;
     currNext->next = currPtr;
     X1->next = currPtr->previous;
     X2->previous = currPtr;

I need help sorting this double linked list (C++)

2 Answers2