为什么需要在链表中存储下一个项目指针

Question

当我在我的简单虚拟机中处理某些链表数据结构时,这个问题突然浮现在脑海中,那么为什么我们需要在数据结构本身中存储指向下一个元素的指针,如下所示:

struct Name
    {
       int element1;
       float element2;
       void *nextItem;
    };

为什么不存储指向数组中下一项的指针,以便我们可以直接访问任何节点？我们可以创建一个链接的数组列表,以确保我们在列表中添加新项目具有类似的灵活性,例如:

struct Name
    {
      int element1;
      float element2;
    };

struct arrayOfpointers
 {
   void *Items[FIXED_SIZE];
   void *nextArray;
 };

其中arrayOfpointers-> Items [1]是指向Name数据结构的第二个元素的指针？这种技术到达链表的具体项目比普通项目快得多吗？

Answer 1

为什么不将指针存储到数组中的下一个项目,以便我们可以直接访问任何节点？

因为这会将链表数据结构转换为数组.

从本质上讲,这将使您的数据结构以多种不同的方式运行:

• 在中间插入将是O(n)而不是O(1)
• 删除将是O(n)而不是O(1)
• 插入需要重新分配和复制"尾巴"
• 删除需要一份"尾巴"

如果您的系统可以使用O(n)插入和删除的数据结构,则可以使用数组:

struct Name {
    int element1;
    float element2;
} nameArray[FIXED_SIZE];

不需要next链接,因为数据将按顺序位于存储器中