RAII风格的C ++类的链表节点 [英] RAII-style C++ class for linked list Nodes

问题描述

我用链表发挥作为一个练习的时刻。

我看在破解编码采访的书都没有链表（经理）类，只是节点，你挂在头节点在主函数。

我抬起头，C ++实现，但大多数似乎是更多的C-款式比C ++，即不是面向对象的。他们利用结构，没有课，并有一个静态方法用于删除列表，这需要明确记得打电话。我想写一个明智的RAII（资源获得即初始化）风格的C ++类明智的析构函数来处理内存释放，我想只使用一个节点类（无LinkedList类）。

我看到有这样的工作的唯一办法是让节点的析构函数删除的下一个节点，如果有一个，但我读过，这种递归删除是一个坏主意，因为你最终建立一个调用堆栈的长度相同的链表。

总结一下我的问题：

• 如果写一个面向对象的类来处理在C ++中链表，你必须有一个链表（经理）类，在处理其析构函数删除列表中的节？
• 如果没有，你会如何处理破坏的节点？

谢谢！

解决方案

  

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

没有，该结构由节点之间的链路所定义，所以没有必要为一个单独的管理器对象。它有时是有一个更方便，特别是如果你喜欢设计的STL库，并希望所有的容器具有相似的界面，但你一定可以实现只是一个节点类型的链接列表。

  

如果没有，你会如何处理破坏的节点？

要避免递归的一种方法是删除它之前删除列表中的每个节点，是这样的：

 〜节点（）{
    而（节点*受害人=下一个）{
        接下来=被害人＆gt;接着，
        被害人＆gt;接下来= nullptr;
        删除受害者;
    }
}
 

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屋！