c++ - 最后在双向链表中追加或插入

Question

我试图在双向链表的末尾插入一个值，我成功地在头或第一个节点插入了值，但没有插入第二个值

这里的问题是在输入第二个值时

class d_list
{
private:

    struct node
    {
        double data;
        node *next;
        node *previous;
    };

    node *first;
    node *last ;
public:
    d_list(void)
    {
        first = nullptr;
        last = nullptr;
    };
    void append(double);

};

void d_list::append(double num)
{
    node *ptr;
    node *toinsert;
    if(!first)
    {
        first = new node;
        first->previous= nullptr;
        first->data = num;
        last= new node;
        first->next= last->previous;
        last->previous = first->next;
        last->next= nullptr;

    }
    else
    {
        if(last->next == nullptr)
        {
            ptr = new node;
            ptr->next =last->previous;
            ptr->data=num;
            last->previous = ptr->next  ;
        }


        last->next= nullptr;
    }

}


int _tmain(int argc, _TCHAR* argv[])
{
    d_list aa;
    cout<<"going to append first"<<endl;
    aa.append(44);
    cout<<"going to append second"<<endl;
    aa.append(50.5);

    return 0;
}

Answer 1

你的代码中有很多问题:

• 您的节点 next 和previous 成员从未在任何地方初始化，因此在使用时未定义。将构造函数添加到 node 或确保它们在分配后被初始化。
• 向空列表添加节点是不正确的。 first->next 未定义，为什么要创建两个节点，第一个和最后一个？在一个只有一个元素的列表中，first == last。 first/last 设置next/previous 也没有任何意义。
• 在结构良好的双链表中，last->next 应始终为 null，first->previous 也应如此。
• 将节点添加到非空列表中也是不正确的。
• 虽然您没有在示例中显示它，但您最终将需要一个析构函数以及一个复制运算符和复制构造函数(三规则)。目前您正在泄漏内存，如果您尝试删除节点，您可能会导致双重释放和崩溃。

我建议您稍微回顾一下代码，以确保您正确理解双向链表背后的概念。在纸上画出带有下一个/上一个箭头的列表，看看在将节点添加到空/非空列表时需要如何更改它们，以及如何删除和移动节点。一旦您弄清楚 next/prev 应该如何设置，那么将其转换为代码应该相对简单。

编辑以回答评论:要添加一个新节点，您可以在技术上将它添加到任何地方，但通常在最后添加(至少从我所看到的)。有关在空列表和非空列表中添加新节点的完整且正确的代码，请参阅其他答案。