链表 pop_back 实现忽略指向 nullptr 的指针

Question

让我们假设在我的实现中只允许使用 new 和 delete 而没有智能指针。我没有使用哨兵节点。

下面是我对 pop_back 的实现：

void sLinkedList::pop_back()
{

  if(begin == nullptr)
  {
    std::cerr << "There is nothing to pop." << std::endl;
  }
  else
  {
    node* nodeToDelete = begin;
    while(nodeToDelete->next != nullptr)
    {
      nodeToDelete = nodeToDelete->next;
    }
    delete nodeToDelete;
    nodeToDelete = nullptr;
    --mSize;
  }

}

它所做的是创建一个指向节点的指针 nodeToDelete 并遍历整个列表，直到它到达最后一个节点（指向 nullptr 的节点）。然后我删除最后一个节点，将其设置为 nullptr，一切都应该没问题，因为在此之前的节点（以前是倒数第二个节点）现在指向一个 nullptr，标记列表的末尾。

当我运行主要使用以下指令时：

int main()
{
  sLinkedList newList;
  std::cout << "Length is " << newList.length() << std::endl;
  newList.print();
  newList.push_front(4);
  std::cout << "Length is " << newList.length() << std:: endl;
  newList.print();
  newList.pop_back();
  std::cout << "Length is " << newList.length() << std::endl;
  newList.print();
}

我得到输出：

Length is 0
The list is empty.
Length is 1
4
Length is 0
4 // should print "There is nothing to pop."

在第一个结果后直接添加另一个 pop_back 会产生 Aborted (core dumped) 信号。

为什么这个想法行不通？

Answer 1

everything should be fine because the node before this (previously the second-to-last node) now points to a nullptr, marking the end of the list.

好的，但是是吗？

当您分配 nodeToDelete = nodeToDelete->next; 时，您是说您的本地指针 nodeToDelete 现在与 nodeToDelete->next 指向内存中的相同位置。两个指针之间没有其他关系。因此，当您随后分配 nodeToDelete = nullptr; 时，您实际上什么也没做：该本地指针再也不会被使用，因此它指向哪个内存区域并不特别重要。

不幸的是，即使您 deleted 那个节点，应该是最终节点仍然指向它过去的位置，因此您的下一个 pop_back 调用愉快地迭代到无法访问的内存。

我假设这是家庭作业，所以我可能不应该为您重写它。但是你可以通过实际修改应该是最后一个节点来修复它，而不仅仅是它的 next 指针的本地副本。

当然，如果这是一个真实的项目，std::forward_list 可能会有所帮助。 :v

Answer 2

好的，但是是吗？

当你分配nodeToDelete = nodeToDelete->next;你是说你的本地指针 nodeToDelete 现在指的是内存中与 nodeToDelete->next 相同的位置。两个指针之间没有其他关系。因此，当您随后分配 nodeToDelete = nullptr;你实际上什么都没做：那个本地指针再也不会被使用，所以它指向哪个内存区域并不特别重要。

不幸的是，即使您删除了该节点，最终节点仍然指向它原来的位置，因此您的下一个 pop_back 调用愉快地迭代到无法访问的内存中。

我假设这是家庭作业，所以我可能不应该为您重写它。但是你可以通过实际修改应该是最后一个节点来修复它，而不仅仅是它的下一个指针的本地副本。

当然，如果这是一个真实的项目，std::forward_list 可能会有所帮助。 :v

链表 pop_back 实现忽略指向 nullptr 的指针

Linked list pop_back implementation ignores pointer-to-nullptr

c++

pointers

dynamic-data