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; in push_back 似乎是一个懒惰的 hack。它不是必需的，没有这个你的代码会变得更短：

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 可能是对的，可能会有更多的错误。

说明

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

在 lt.push_back(5); 之后，您的列表如下所示：

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

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

                        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();:

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.

¹尽管在 C++ 中您使用 delete 而不是 C 函数 free，但我指的是 "freed memory"，因为在我看来它更清晰。记忆还在，只是不属于你的程序

Answer 2

编写一个函数来测试列表的有效性。每次操作后调用此函数。如果列表无效，请调用 abort() 进入您的调试器。最后一个操作是有bug的

一方面，只要看看你的代码，我就很确定你没有正确地保持双链接。我看到你在调整下一个链接，但从来没有调整上一个链接。

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

Garbage value in pop_back, Doubly Linked List in C++

c++

data-structures

linked-list

doubly-linked-list

解决方案

说明