Add node in sorted linked list

Question

I'm trying to make sorted linked list in ascending order , but for some reason the code give me one value if some one can tell me why I will be thankful see this function:

void AddNode(Node *&head){

        int temp;
        Node *q;
        Node *prev = 0; 
        Node *t;

        cout <<"enter a number : ";
        cin >> temp;
        t = new Node ;
        t->number = temp;
        t->next = 0;

        if (head == 0) {
            head = t;
        } else {
            q = head;
            while (q != 0 ){
                prev = q;

                if(q->number > t->number){
                    prev->next = t;
                    t->next = q;
                    break;  
                }

                q = q->next; // counter     
            }

            if (q == 0 ) // if it is the last value
                q = t;
        }

    }

That parameter?? It smells. Anyway If it compiles then you need to step-over your code to see what is exactly happening. Using F-10 on Visual Studio — Khalil Khalaf
– Khalil Khalaf, Commented Apr 21, 2016 at 14:28
You don't update head when the new node is inserted in front. Also, q = t at the end doesn't do anything useful - you are updating a local variable but aren't using this new value. — Igor Tandetnik
– Igor Tandetnik, Commented Apr 21, 2016 at 14:30
@FirstStep: What should the OP do if using Eclipse or Code::Blocks? Maybe the OP should use a debugger? There are other IDEs besides Visual Studio. — Thomas Matthews
– Thomas Matthews, Commented Apr 21, 2016 at 14:51

Jean-Baptiste Yunès · Accepted Answer · 2016-04-22 07:45:06Z

3

Inserting at the end is wrong:

if (q == 0 ) // if it is the last value
    q = t;

You just modify q but never update the link of the last element. You should try:

if (q==0) // past end of list
    prev->next = t; // next of last element is t

----------EDIT-------------

Your management of pointers through looping is wrong, the following works and should be much clear (only one pointer is used to move in the list):

if (head == 0) { // empty list
    head = t;
} else if (t->number < head->number) { // insert in first place
  t->next = head;
  head = t;
} else { // general case
  q = head;
  while (q->next != 0 && q->next->number<t->number) {
    q = q->next;
  }
  cout << "insert after " << q->number << endl;
  t->next = q->next;
  q->next = t;
}

edited Apr 22, 2016 at 7:45

answered Apr 21, 2016 at 14:32

Jean-Baptiste Yunès

36.6k4 gold badges51 silver badges76 bronze badges

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

1 Comment

Jean-Baptiste Yunès Over a year ago

see my new (tested) solution

Collectives™ on Stack Overflow

Add node in sorted linked list

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related