c++ - pop_back 中的垃圾值，C++ 中的双向链表

Question

在下面的代码中，我实现了双向链表。我得到的输出为 56 2 3 4 0而不是 56 2 3 4 .但是，如果我删除 lt.erase(5); lt.push_back(46);然后我得到正确的输出。我首先想到的是erase()有一些错误，但通过单独测试每个功能，它们对我来说似乎很好。然而，在这个组合中，我得到了一个额外的 0 .

#include <iostream>
using namespace std;

template <class T>
class LinkedList {
private:
    T data;
    LinkedList *prev, *next, *head, *tail;
public:
    LinkedList() : next(nullptr), head(nullptr), tail(nullptr), prev(nullptr){}
    LinkedList* get_node(T);
    void push_back(T);
    void insert(int, T);
    void pop_bak();
    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 -> prev = nullptr;
    new_node ->next = nullptr;
    return new_node;
}

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

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

template <typename T>
void LinkedList<T>:: pop_bak() {
    LinkedList *temp;
    temp = tail;
    tail = tail->prev;
    tail->next = nullptr;
    delete temp;
}

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;
        }
        if(start->next == tail) {
            temp = tail;
            tail = tail ->prev;
            tail->next = nullptr;
            delete temp;
        } else {
            temp = start -> next;
            start ->next = start ->next->next;
            delete temp;
        }
    }
}

template <typename T>
void LinkedList<T>:: print() {
    LinkedList *start = head;
    while(start != tail->next) {
        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, 56);
    lt.erase(5); // Remove this
    lt.push_back(46); // And this and it works perfectly. Where is the bug?
    lt.pop_bak();
    lt.print();
}

Answer 1

解决方案
static LinkedList *temp;在 push_back似乎是一个懒惰的黑客。不需要它，如果没有这个，你的代码会更短:

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;
        node->prev = tail;
        tail = node;
    }
}

但这只是我为这个特定问题发现的错误。 Zan Lynx 可能是对的，可能还有更多错误。

解释

你会得到未定义的行为，因为你访问了已删除的内存。错误或设计失败是 static LinkedList *temp;在 push_back .注意这个 temp将始终指向最后推送的元素。但是在某些时候你删除了最后一个元素!那么让我们一步一步来:

后 lt.push_back(5);您的列表如下所示:

                         temp (from push_back)
                         |
56 <-> 2 <-> 3 <-> 4 <-> 5 -> nullptr
|                        |
head                     tail               

现在删除 delete s 值为 5 的节点。但是 temp仍然指向被释放的内存1，所以你得到:

                        temp (from push_back)
                        |
56 <-> 2 <-> 3 <-> 4    5 [freed]
|                  |
head               tail               

下一行后 lt.push_back(46);事情变得疯狂。您有以下代码(简化):

void LinkedList<T>::push_back(T element) {
    static LinkedList* temp;
    if (head == nullptr) {...}
    else {
        LinkedList* node = get_node(element);
        tail->next = node;                   
        tail = node;                         
        tail->prev = temp; // prev->temp is now pointing to freed memory
        temp = temp->next; // dereferencing an invalid pointer -> undefined behaviour
    }
}

这导致:

                                          temp (from push_back)
         5 [deleted] <-                   |
56 <-> 2 <-> 3 <-> 4 -> 46  -> nullptr    ????  
|                       |
head                    tail               

然后一切都在与 lt.pop_bak();的手提篮中一起下 hell :

void LinkedList<T>::pop_bak() {
    LinkedList* temp;
    temp = tail;
    tail = tail->prev;    // tail->prev is an invalid pointer, now tail is too
    tail->next = nullptr; // dereferencing invalid pointer (again)
    delete temp;
}

                        temp (from pop_bak)                 
                        |                                   
56 <-> 2 <-> 3 <-> 4 -> 46 [deleted] -> nullptr     5 [deleted] -> nullptr
|                                                   |
head                                                tail               

正如你看到的，你的列表被完全分割了，你有两个指向释放内存的指针(例如，你不拥有的包含垃圾数据的内存)。仅仅因为你在 static LinkedList *temp; 中保存了一个指针在 push_back .

1虽然在 C++ 中你使用 delete而不是 C 函数 free ，我指的是“释放的内存”，因为在我看来它更清楚。内存还在，只是不再属于你的程序