c++ - C++中的单链接列表中的pop_back()

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

您不能只用一个链表，而要实现您的

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)，这是单链表的诅咒。