什么错误的逻辑导致我的链表的这个 push_back(...) 函数失败？

Question

出于某种原因

template <typename T> void SinglyLinkedList<T>::push_back ( T v )
{
   node * newNode = new node;
   newNode->val = v;
   newNode->next = NULL;
   if (_root != NULL)
   {
     node * thisNode = _root; 
     while (thisNode->next != NULL) thisNode = thisNode->next;
     thisNode->next = newNode;
   }
   else
   {
     _root = newNode;
   }    
}

逻辑不正确，我需要一些帮助来弄清楚它是什么。我测试的时候

int myArray [] = { 1, 69, -23942, 69, 56, 67 };
SinglyLinkedList<int> myList(myArray, sizeof(myArray)/sizeof(int));
myList.push_back(33);
myList.print();

它打印了

1->69->-23942->69->56->33->33->33->33->33-> ...

直到程序崩溃。

我将解释我的逻辑，以便您可以查明我错在哪里：

node * newNode = new node;
newNode->val = v;
newNode->next = NULL;

在堆上创建一个新的 node 对象并将其值初始化为 v 并将指向下一个节点的指针初始化为 NULL。这是将添加到列表末尾的节点。列表的末尾将是

(1) next 为 NULL

的最终元素

或

(2) 不存在，意味着没有元素，因此没有最终元素

为了微观优化，因为我希望情况 (1) 更频繁地发生，所以我将其放在要遵循的 if 子句中，并将情况 (2) 放在 else 子句中.

当且仅当 _root node 为 NULL 时，情况 (2) 才会发生，这意味着列表为空，对其的处理只是使 _root 是 newNode:

   else
   {
     _root = newNode;
   }

情况 (1) 需要找到最终节点并将其 next 设置为 newNode，只需 3 行

即可轻松完成

     node * thisNode = _root; 
     while (thisNode->next != NULL) thisNode = thisNode->next;
     thisNode->next = newNode;

这个逻辑有什么缺陷？

Answer 1

错误出在您的构造函数中。这一行：

delete lastNode;

正在删除您仍在使用的内存（lastnode 指向的节点刚刚放入您的列表中）。

删除该行。

编辑：进一步解释。一旦 lastnode 指向的内存被释放，运行时就可以再次使用该内存来调用 new。在您的情况下，您可能最终 newNode 和 thisNode 指向同一位置，导致节点指向自身。

Answer 2

当你删除最后一个节点时，它的下一个节点为空的节点被删除，而前一个下一个指针不为空所以当你解析链表时你指向了未知的内存位置！！！

什么错误的逻辑导致我的链表的这个 push_back(...) 函数失败？

What faulty logic is causing this push_back(...) function of my linked list to fail?

c++

algorithm

linked-list

data-structures