双向链表的自定义实现不起作用（教育）

Question

我实现了我自己的简单版本的双向链表。不幸的是，它似乎有错误。列表的头部似乎移动到新的 Node，每次我用 push_back 添加一个。因此，print 将无限期地打印最后一个值。

链表：

struct doubly_linked_list
{
    Node *head = nullptr;
    Node *tail = nullptr;
    void push_back(Node n)
    {
        if (this->head == nullptr)
        {
            this->head = &n;
            this->tail = nullptr;
        }
        n.prev = this->tail;
        if (this->tail)
        {
            n.prev->next = &n;
        }
        this->tail = &n;
    }
    void print()
    {
        Node *tmp = this->head;
        while (tmp != nullptr)
        {
            std::cout << tmp->data << ", ";
            tmp = tmp->next;
        }
    }
};

其中节点实现为

struct Node
{
    int data;
    Node *next = nullptr;
    Node *prev = nullptr;
    Node(int data)
    {
        this->data = data;
    }
    Node()
    {
        this->data = -1;
    }
};

主要

int main()
{
    doubly_linked_list dl;
    dl.push_back(Node{3});
    dl.push_back(Node{2});
    dl.push_back(Node{1});
    dl.push_back(Node{0});
    dl.push_back(Node{5});
    dl.print(); // print 5 forever
}

免责声明：请注意此 post 的主题是教育性的。我知道 c++ 标准中的列表。

Answer 1

这是一个使用原始指针的工作示例，根据您正在做的事情，您可能希望将其更改为智能指针。

#include <iostream>

struct Node
{
    int data;
    Node *next = nullptr;
    Node *prev = nullptr;
    Node(int data)
    {
        this->data = data;
    }
    Node()
    {
        this->data = -1;
    }
};

struct doubly_linked_list
{
    Node *head = nullptr;
    Node *tail = nullptr;
    void push_back(Node* n)
    {
        if (this->head == nullptr)
        {
            this->head = n;
            this->tail = nullptr;
        }
        n->prev = this->tail;
        if (this->tail)
        {
            n->prev->next = n;
        }
        this->tail = n;
    }
    void print()
    {
        Node *tmp = this->head;
        while (tmp != nullptr)
        {
            std::cout << tmp->data << ", ";
            tmp = tmp->next;
        }
     }
};

int main()
{
    doubly_linked_list dl;
    dl.push_back(new Node{3});
    dl.push_back(new Node{2});
    dl.push_back(new Node{1});
    dl.push_back(new Node{0});
    dl.push_back(new Node{5});
    dl.print(); // print 5 forever
}

双向链表的自定义实现不起作用（教育）

Custom implementation of doubly linked list not working (educational)

c++

linked-list

doubly-linked-list