为什么不能在不创建节点作为指针的情况下创建链表?



在不将节点声明为指针的情况下创建链表中有一个答案。但我想知道是否有其他原因导致无法将节点创建为指针,只是为了清楚起见。

其中一个原因是,新节点的范围将在功能之外消亡。你没有办法解决这个问题吗?,和还有其他原因吗?

我一直在使用许多链表(甚至更复杂的结构(,其中没有在堆上单独分配节点,但所有节点都是单个数组中的元素。

拥有指向节点的指针并在堆上分配单个节点是很常见的,但这并不是唯一的选择。例如,对于某些应用程序来说,为了提高效率或简化处理,在"页面"中分配节点可能会更好。

另一个非常常见且经常有用的选项是通过在数组中使用数字索引来创建完全没有指针(甚至在节点内部也没有(的链表或树。例如

struct Tree {
struct Node {
double value;
int left, right; // Index of left/right child, -1 if missing
};
int root = -1;
std::vector<Node> nodes;
};

链表从字面上定义为对象相互指向的结构:

在计算机科学中,链表是数据元素的线性集合,其顺序不是由它们在内存中的物理位置决定的。相反,每个元素都指向下一个元素

在C++中,一个对象可以使用指针或引用指向另一个对象。

引用是可能的,但不方便,因为它必须在创建对象时设置,并且不能修改。

任何其他可以在不跟随指针的情况下从一个对象导航到另一个对象的结构都不是链表。一个典型的例子是数组:您可以通过计算其相对于当前元素的地址来导航到下一个元素。

现在,如何分配节点完全取决于您-您可以在动态内存、自动存储(堆栈上(、静态、共享内存等中分配节点。如果使用指针或引用链接节点,则仍然具有链表结构。

我能想到的另一个原因是遍历链表会更方便。例如:

Node* current;
while (current != nullptr) {
// Do something
current = current->next;
}

如果current不是指针,那么您可能会复制链接列表中的每个节点,这真的是个坏主意。

如果共享内存或反射内存中有一个链表,那么指针的世界就不存在了。你回到了20世纪70年代,使用数组索引而不是指针。

对于那些习惯指针的人来说,这是一个完全不同的世界,也是一个文化冲击。没有堆,您必须管理自己的垃圾收集。

为什么不创建节点作为指针就不能创建链表

你可以,但你肯定需要某种间接的方式。

为什么指针通常用于实现链表?正如@6502在他的回答中已经指出的,你可以通过数组或任何其他容器来实现同样的事情,这些容器作为列表的页面/内存。但为了参数的目的,让我们比较一个由指针实现的List和一个保持节点为成员的List。主要的答案是:实现列表的功能更容易。列表的好处是,您可以很容易地前后推送/弹出并快速删除项目。列表中的删除是如何实现的?您只需将指向"待删除对象"的指针更改为下一个节点(或者在数组的情况下,您分配另一个索引(。但是,如果你的"待删除对象"将另一个对象定义为真实对象,而不是通过指针,那么在删除它之前,你必须先move它,否则它和列表的其余部分都会消失。

此外,您只能实现单个链表,因为只有一个节点可以容纳另一个节点。如果Node A具有NodeB,则NodeB不可能也具有NodeA。但是使用指针NodeB可以毫无问题地指向NodeA,反之亦然。

TL;DR如果你使用指针或数组,你的列表操作,比如删除、推送等等,都是在切换指针或索引。如果您的节点包含数据,则需要通过移动/复制来更新这些数据。而且这很难实现,而且比指针/引用间接方式更难掌握。

相关内容

  • 没有找到相关文章

最新更新