双向链表，按顺序添加节点

Question

我想一直保持我的双向链表排序并保持头节点和尾节点指针更新。我设法在所有操作中保持头指针更新，但我无法跟踪尾指针。它只将最后一个元素显示为 tail->info 但不能返回 tail=tail->prev; 这是我的代码：

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

Answer 1

@JonathanPotter 是对的。 "You're not setting ptr->prev when you link a new node in." 这就是问题所在。这段代码对我来说很好用。查看修改，添加了一些用于设置上一个节点的部分。代码可能有点乱，但您可能会理解逻辑并编写更好的代码。

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

双向链表，按顺序添加节点

Doubly linked list, add node in-order

c++

sorting

linked-list