c++ - 双向链表的自定义实现不起作用(教育)

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
}

免责声明:请注意，这篇文章的主题是教育性的。我知道 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
}