如何将元素添加到链接列表的前面

Question

这就是节点的设置方式：

struct Node {
    Node *next;
    Node *prev;
    T datum;
};

这是我的代码

    //MODIFIES: this
    //EFFECTS:  inserts i into the front of the list
    void push_front(const T &datum)
    {
        Node newfirst = first; // set newnode to first
        &first = &datum;
        datum = newfirst;
    }

  Node *first;   // points to first Node in list, or 0 if list is empty
  Node *last;    // points to last Node in list, or 0 if list is empty

出于某种原因，我认为这是不对的。

Answer 1

您似乎需要以下

//this is my code
    //MODIFIES: this
    //EFFECTS:  inserts i into the front of the list
void push_front(const T &datum)
{
    first = new Node { first, nullptr, datum };
    if ( !last ) last = first;
}

如果您的编译器不支持运算符new的初始值设定项列表，那么您可以编写

//this is my code
    //MODIFIES: this
    //EFFECTS:  inserts i into the front of the list
void push_front(const T &datum)
{
    Node *tmp = new Node();
    tmp->datum = datum;
    tmp->next = first;
    first = tmp;
    if ( !last ) last = first;
}

Answer 2

您想要（i）创建一个具有有效内容的新节点，并且（ii）将is设置为列表的第一个节点。你可以像下面的例子那样做：

void push_front(const T &datum)
{
    Node* newFirst = new Node;  //construct new Node
    newFirst->next = first;     // set newFirst's next node
    newFirst->datum = datum;   //set the content
    first = newFirst;          //assign new first node;
}

这只是一个草图；有关更多详细信息，您应该发布更多的代码（例如在其中一条评论中提到的）。

还有一件事要提：我更喜欢使用unique_ptr作为其中一个Node指针，例如

struct Node {
    std::unique_ptr<Node> next;
    Node *prev;
    T datum;
};

这可以非常容易地销毁列表（还可以避免现代C++中经常推荐的new命令）。