Doubly linked list, add node in-order

Question

I want to keep my doubly linked list sorted all the time and keep the head and the tail node pointers updated. I managed to keep the head pointer updated in all operations but I can not keep track of the tail pointer. It only shows the last element as tail->info but can not go back as doing tail=tail->prev; here is my code:

AddInOrder(node* &head, node* &tail, int number) {     

    node *ptr=head; 

    if (head==NULL || number<head->info) {       

        node*temp=new node;

        temp->info=number; 
        temp->next=head;   
        temp->prev=NULL;
        head=temp;   
        tail=temp;    
        return 0;
    }

    while(ptr->next!=NULL && ptr->next->info<number) {         
        ptr=ptr->next;                                        
    }

    node*temp=new node;              
    temp->info=number;
    temp->next=ptr->next;
    temp->prev=ptr;
    ptr->next=temp;

    while(ptr->next!=NULL) {
        ptr=ptr->next;                 
    }

    tail=ptr;             

    return 0;
}

"but can not go back as doing tail=tail->prev;" - I'm trying to fathom a situation where you would ever want to do that in the first place, as if anything it will put your tail pointer somewhere it shouldn't be; not on the last node of the list. — WhozCraig
– WhozCraig, Commented Mar 3, 2015 at 22:31
let's say I type 6,9,1,2,3 it displays1,2,3,6,9 when I start displaying them from the head pointer but starting from the tail to the head it gives 9 then 6 and then it stops where it shouldnt and contiune like 3,2,1 — Cem Aytekin
– Cem Aytekin, Commented Mar 3, 2015 at 22:34
I want to print the list in reverse so I start from the tail and go back — Cem Aytekin
– Cem Aytekin, Commented Mar 3, 2015 at 22:36
You're not setting ptr->prev when you link a new node in. And when you add a new node to the head of the list you're wiping out your tail pointer. — Jonathan Potter
– Jonathan Potter, Commented Mar 3, 2015 at 22:37

mhs · Accepted Answer · 2015-03-05 00:48:29Z

1

@JonathanPotter was right. "You're not setting ptr->prev when you link a new node in." that is the problem. this code works fine for me. see the modification, added some part for setting prev node. code may be little messy but you may understand the logic and write a better code.

int AddInOrder(node* &head, node* &tail, int number) 
{     
    node *ptr=head; 
    node*temp=new node;
    temp->info=number; 

    if ( head==NULL )
    {
        temp->next=head;   
        temp->prev=NULL;
        head=temp;
        tail = temp;

        return 0;
    }

    if ( number<head->info )
    { 
        temp->next=head;   
        temp->prev=NULL;

        head->prev = temp;
        head=temp;
        return 0;
    }

    while(ptr->next!=NULL && ptr->next->info<number) 
    {         
        ptr=ptr->next;    
        continue;
    }

    if (ptr->next != NULL)
    {
        ptr->next->prev = temp;
    }
    temp->next=ptr->next;
    temp->prev=ptr;
    ptr->next=temp;

    while(ptr->next!=NULL)
    {
            ptr=ptr->next;                 
    }

    tail=ptr;             

    return 0;
}

edited Mar 5, 2015 at 0:48

answered Mar 4, 2015 at 2:22

mhs

1,0422 gold badges16 silver badges36 bronze badges

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

1 Comment

Cem Aytekin Over a year ago

Still same problem.Goes correctly with next bonds but when I start from the tail and want to go back with prev bonds,it does not go back correctly.I think I have problem with the prev connections anyway thanks for your interest i will work more on this.

Collectives™ on Stack Overflow

Doubly linked list, add node in-order

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