pop_back() 在 C++ 中的单链表

Question

我写了以下单链表的实现。我面临的一个问题是我希望 pop_back() 删除最后一个节点，然后将 tail 设置为 O(1) 中倒数第二个节点。现在，问题是它不是双向链表，所以如果没有运行循环，我无法访问倒数第二个节点。我在 O(1) 中完成了 push_back()。如何在这段代码中在 O(1) 中制作 pop_back() ？

#include <iostream>
using namespace std;

template <class T>
class LinkedList {
private:
    T data;
    LinkedList *next, *head, *tail;
public:
    LinkedList() : next(nullptr), head(nullptr), tail(nullptr){}
    LinkedList* get_node(T);
    void push_back(T);
    void insert(int, T);
    void pop_back();
    void erase(int);
    void print();
};

template <typename T>
LinkedList<T>* LinkedList<T>:: get_node(T element) {
    auto* new_node = new LinkedList;
    new_node -> data = element;
    new_node ->next = nullptr;
    return new_node;
}

template <typename T>
void LinkedList<T>:: push_back(T element) {
    if(head == nullptr) {
        head = get_node(element);
        tail = head;
    } else {
        LinkedList *node = get_node(element);
        tail->next = node;
        tail = node;
    }
}

template <typename T>
void LinkedList<T>:: insert(int position, T element) {
    LinkedList *node = get_node(element);
    if(position == 1){
        node->next = head;
        head = node;
    } else {
        LinkedList *start = head;
        int it = 1;
        while (it < position - 1) {
            start = start->next;
            ++it;
        }
        node->next = start->next;
        start->next = node;
    }
}
template <typename T>
void LinkedList<T>:: pop_back() {

}


template <typename T>
void LinkedList<T>:: erase(int position) {
    LinkedList *temp;
    if(position == 1){
        temp = head;
        head = head ->next;
        delete temp;
    } else {
        LinkedList *start = head;
        int it = 1;
        while (it < position - 1) {
            start = start->next;
            ++it;
        }
        temp = start -> next;
        start ->next = start ->next->next;
        delete temp;
    }
}

template <typename T>
void LinkedList<T>:: print() {
    LinkedList *start = head;
    while(start != nullptr) {
        cout << start->data << " ";
        start = start->next;
    }
}

int main() {
    LinkedList<int> lt;
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    lt.insert(1, 34);
    lt.print();
}

Answer 1

遗憾的是，你不能在 O(1) 时间内完成，因为没有办法做到这一点，你必须为性能补偿内存并使用双链表。如果您可以选择使用其他数据结构，我建议您使用 Deque

Answer 2

你不能使用单个链表，让我们实现你的

template <typename T>
void LinkedList<T>:: pop_back() {
   tail = find(pos); 
   erase_next(tail); // erase tail's next.
}

您需要一个函数来查找位置，这意味着您还需要知道其中有多少个，在这种情况下 pos 的大小为 1（如果使用零偏移，则为 -2）或搜索一个节点将 pos 作为其下一个节点。您可以使用erase中的大部分代码来实现它。

现在这个新发现的复杂度为 O(n)，这是单链表的诅咒。

Answer 3

不可能。

说明

如果你真的想在O(1) 中做到这一点并且想要保持列表单链接，你可以考虑存储除了最后一个节点之外的倒数第二个节点。

但是，除了成为组织上的恐惧之外，它仍然行不通。当然，在 pop_back 中，您可以简单地 delete tail; 并将尾部设置为倒数第二个元素。但是现在您仍然需要一个循环来确定新的倒数第二个元素。

这还很糟糕吗？

我不这么认为。每种数据结构都有其优点和缺点。在我看来，一个数据结构在某些事情上做得确实很好，但在其他事情上却很糟糕，而不是在所有事情上都以中等速度快速完成的数据结构。最好保持你的 class 苗条，针对特定场景优化它并接受它的缺点。

Answer 4

正如其他答案中提到的，添加到单链表的末尾是一个 O(N) 操作。因此，我的 API 中根本没有包含 pop_back。如果用户需要像双端队列一样从同一个链表的两端弹出，他们应该改用双向链表。

然而，这并不是一个完全失败的原因，因为对于 O(1) FIFO 和 LIFO 行为，您仍然可以反向使用单链表：

对于堆栈，不使用 push_back 和 pop_back，而是使用 push_front 和 pop_front，这是 O(1) 操作。
对于队列，不使用 push_front 和 pop_back，而是使用 push_back 和 pop_front，这是 O(1) 操作。

总而言之，push_front、pop_front 和 push_back 是 O(1) 操作，但 pop_back 不是——它是 O(N)。

pop_back() 在 C++ 中的单链表

pop_back() in Singly Linked List in C++

c++

linked-list

data-structures

singly-linked-list

说明

这还很糟糕吗？