c++ - 链表的 Push_front 和 push_back 方法似乎删除了一个节点

Question

我正在编写一个名为 Playlist 的类，它对 PlaylistNodes 执行不同的操作。我在网上看了看并尝试实现push_back和push_front方法，但我没有成功。

PlaylistNode *PlaylistNode::insert_next(PlaylistNode *p) {
    PlaylistNode *tmp = nullptr;

    tmp = this->next;
    this->next = p;
    p->next = tmp;

    return p;
}

Playlist::Playlist() {
    head = new PlaylistNode;
    prevToCurr = head;
    tail = head;
    size = 0;
}

Playlist *Playlist::push_back(PlaylistNode *p) {
    PlaylistNode *tmp;

    tmp = tail;
    tmp->insert_next(p);
    tail = p;

    prevToCurr = tail;

    size++;
    return this;
}

Playlist *Playlist::push_front(PlaylistNode *p) {
    size++;

    PlaylistNode *tmp = head;
    head = p;
    head->insert_next(tmp);

    return this;
}

当我运行时:

play.push_front(node1);
play.push_front(node2);
play.push_front(node2);

然后打印链表，我只得到2个节点:

ID 44: song2
ID 33: song1

Answer 1

您的初始化方法(构造函数)没有按预期执行。在构建这种类型的列表时，head 和 tail 都必须指向 null，因为列表是空的。我不确定“prevToCurr”是做什么的，但我不认为列表使用类似的东西，所以我会摆脱它:

Playlist::Playlist() {
    head = null;
    tail = null;
    size = 0;
}

为简单起见，在两种情况下处理 push_front():当列表为空时以及当列表有节点时。

1. 如果列表为空，您只需将 head 和 tail 指向新节点即可。
2. 当链表不为空时，将之前的表头指向新节点并更新表头。

看起来像这样:

Playlist *Playlist::push_front(PlaylistNode *p) {
    if (size == 0) {
        head = p;
        tail = p;
    }
    else {
        head->insertNext(p);
        head = p;
    }
    size++;
    return this;
}

您的 push_back() 方法的实现方式几乎与 push_front 相同，更新尾部而不是头部，并使新尾部指向旧尾部，我相信您能弄明白。

您没有提供足够的信息，所以我猜测您的 PlaylistNode::insertNext 设置了下一个节点。在这种情况下，您在这里所做的是将下一个指针设置为作为参数提供的节点:

PlaylistNode *PlaylistNode::insert_next(PlaylistNode *p) {
    this->next = p;
    return this;
}

这应该或多或少起作用，只要您正确创建播放列表节点(不要将同一个节点推送 2 次，您最终会得到一个指向自身旁边的节点，如评论中所述)。