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

Question

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

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

为什么不将指针存储到数组中的下一项，这样我们就可以直接访问任何节点？并且我们可以制作一个数组的链接列表，以确保我们有类似的灵 active 来向列表中添加新项目，例如:

struct Name
    {
      int element1;
      float element2;
    };

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

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

Answer 1

why not store the pointer to next item in array so we can access any node directly?

因为这会将您的链表数据结构转换为数组。

本质上，这将使您的数据结构以几种不同的方式表现:

• 在中间插入将是 O(n) 而不是 O(1)
• 删除将是 O(n) 而不是 O(1)
• 插入需要重新分配和复制“尾部”
• 删除需要“尾部”的副本

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

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

不需要 next 链接，因为数据会按顺序位于内存中