用于链接列表节点的RAII式C ++类 [英] RAII-style C++ class for linked list Nodes

问题描述

我正在使用链接列表作为练习。

我在 Cracking The Coding Interview book没有LinkedList（manager）类，只是节点，你挂在你的main函数的头节点。

我查找了C ++实现，但大多数似乎是C风格比C ++，即不是面向对象。它们使用struct，没有类，并有一个静态方法删除列表，你需要明确记得调用。我想写一个明智的RAII（资源获取是初始化）风格的C ++类与合理的析构函数来处理内存释放，我想只使用一个Node类（没有LinkedList类）。

我看到有这个工作的唯一方法是使Node的析构函数删除下一个节点，如果有一个，但我已经读到，这种递归删除是一个坏主意，因为你最终创建一个调用堆与链接列表的长度相同。

所以总结我的问题：

• 如果在C ++中编写一个面向对象的类来处理链表，你必须有一个LinkedList（manager）类来处理删除它的析构函数中的列表节点。


• 如果

  >解决方案

  
  

  如果编写一个面向对象的类来处理C ++中的链表，你必须有一个LinkedList（管理器）类来处理删除列表节点在其析构函数中？

  
  

  否，结构由节点之间的链接定义，因此不需要单独的管理器对象。有时可能更方便，有一个，特别是如果你设计一个类似STL的库，并希望所有的容器有一个类似的接口，但你可以肯定实现一个链表只有一个节点类型。

  
  

  如果没有，你如何处理节点的销毁？

  
  

  避免递归的一种方法是在删除每个节点之前删除它，例如：

   〜node ）{
   while（node * victim = next）{
   next = victim-> next; 
   victim-> next = nullptr; 
   delete victim; 
  } 
  } 
    

  
  

  I'm playing with linked lists as an exercise at the moment.

  The examples I'm looking at in the Cracking The Coding Interview book have no LinkedList (manager) class, just Nodes, and you hang on to the head Node in your main function.

  I looked up C++ implementations, but most seem to be more C-style than C++, i.e. not object-oriented. They use structs, no classes, and have a static method for deleting the list, which you need to explicitly remember to call. I wanted to write a sensible RAII (Resource Acquisition Is Initialization) style C++ class with sensible destructors to handle memory deallocation, and I wanted to use only a Node class (no LinkedList class).

  The only way I saw to have this work was to have Node's destructor delete the next Node if there was one, but I've read that this kind of recursive delete is a bad idea, because you end up creating a callstack the same length as the linked list.

  So to summarize my question:

  • If writing an object-oriented class to handle linked lists in C++, do you have to have a LinkedList (manager) class which handles the deletion of the list nodes in its destructor?
  • If not, how would you deal with destruction of Nodes?

  Thanks!

  解决方案

  If writing an object-oriented class to handle linked lists in C++, do you have to have a LinkedList (manager) class which handles the deletion of the list nodes in its destructor?

  No, the structure is defined by the links between nodes, so there's no need for a separate manager object. It can sometimes be more convenient to have one, especially if you're designing a library like the STL and want all the containers to have a similar interface, but you can certainly implement a linked list with just a node type.

  If not, how would you deal with destruction of Nodes?

  One way to avoid recursion is to remove each node from the list before deleting it, something like:

  ~node() {
      while (node * victim = next) {
          next = victim->next;
          victim->next = nullptr;
          delete victim;
      }
  }
  

  这篇关于用于链接列表节点的RAII式C ++类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！