是否可以创建一个带有索引但没有指针的链表? [英] Is it possible to create a single linked list with indexes but without pointers?

问题描述

我有一个问题是否可以做到?

I've got a question if it's possible to do that?

一个人对我说我可以做这样的事情:

One man said to me that i can do something like this:

struct Node
{
  int data;
  int NextIndex;
}

但是我不确定我是否完全不应该使用指针.

But I am not sure if I should not use pointers at all.

推荐答案

我已经做了很多次了(我在嵌入式系统中工作，所以我使用了类似的技巧).使用索引的优点是索引使用的内存少于指针(通常是uint8_t或uint16_t)所使用的内存，因此，如果需要考虑内存，则可以这样做.

I've done that many times (I work in embedded systems, so I use tricks like this). The advantage of using indexes is that an index uses less memory than a pointer (usually a uint8_t or uint16_t), so if memory is a concern, you can do that.

在这种情况下，您只能使用单个数组(因为索引必须是相对于该数组的).因为您没有进行动态分配，所以在这种情况下，插入和删除非常快.请注意，尽管您也可以在数组中使用指针，并且如果您在优化时间，那么它甚至比索引要快(无论如何，我在大多数架构上都是如此).

You are limited to using a single array in that case (because the index has to be relative to that). Because you are not doing dynamic allocation, in this case, insertion and deletion is very quick. Notice though that you can use pointers in an array as well, and if you're optimizing for time, then this is even faster than indexes (on most architectures I've worked on anyways).

就使用下一个指针而言，您将分配一个大数组，并创建一个 free 头，该头指向第一个元素，然后使所有元素指向下一个元素，因此从本质上讲，有一个自由链接列表.如果要使用元素，请从空闲列表中将其弹出，然后将其推入要使用的新列表中.释放元素后，只需将其推回空闲列表即可.

As far as using the next pointers, you allocate a large array, and create a free head which points to the first element, and then make all elements point to the next one, so essentially you have a free-linked-list. If you want to use an element, you pop it from the free list, and push it onto the new list you wish to use. When you free an element, you simply push it back onto the free list.

这篇关于是否可以创建一个带有索引但没有指针的链表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！