8

我知道如何使用数组实现链表。例如我们定义一个结构如下：

struct Node{
    int data;
    int link;
}

“data”存储信息，“link”存储下一个节点数组中的索引。

谁能告诉我与“普通”链表相比，使用数组实现链表的优点和缺点是什么？任何建议将不胜感激。

4

4 回答 4

10

如果你用一个数组来支持一个链表，你最终会遇到两者的缺点。因此，这可能不是一个很好的实现方式。

一些直接的缺点：

  1. 您将在数组中有死空间（当前未用于项目的条目）占用内存
  2. 您必须跟踪免费条目 - 在几次插入和删除之后，这些免费条目可能在任何地方。
  3. 使用数组将对链表的大小施加上限。

我想一些优点是：

  1. 如果您在 64 位系统上，您的“指针”将占用更少的空间（尽管免费条目所需的额外空间可能超过了这个优势）
  2. 您可以将阵列序列化到磁盘并通过mmap()调用轻松将其读回。不过，您最好使用某种协议缓冲区来实现可移植性。
  3. 您可以保证数组中的元素在内存中彼此接近。
于 2012-05-07T07:14:23.820 回答
2

谁能告诉我与“普通”链表相比，使用数组实现链表的优缺点是什么？

链表具有以下复杂性：

  • 缺点 x xs : O(1)
  • 附加纳米： O（n）
  • 指数 i xs : O(n)

如果您的表示使用严格的连续数组，您将有不同的复杂性：

  • 缺点将需要复制旧数组：O(n)
  • append 需要将两个数组复制到一个新的连续空间中：O(n + m)
  • 索引可以实现为数组访问：O(1)

也就是说，以数组形式实现的链表 API 的行为类似于数组。

您可以通过使用严格数组的链表或树来缓解这种情况，从而导致绳索或手指树或惰性序列。

于 2012-05-08T11:51:43.493 回答
0

堆栈实现两种方式。首先是使用数组，其次是使用链表。

使用数组的一些缺点，然后大多数程序员在堆栈实现中使用链表。

首先是使用链表的堆栈首先不声明堆栈大小并且不限制堆栈中的数据存储。其次是指针式中的链表来声明和使用它。

链表中只使用一个指针。它称为顶部指针。

堆栈是 lifo 方法使用。但在链表程序实现中存在一些缺点。

大多数程序员使用喜欢列表使用堆栈实现。

于 2012-06-21T08:13:03.310 回答
0

使用数组实现，您可以对列表的节点进行顺序和更快的访问，另一方面，如果您使用指针实现链接列表，您可以随机访问节点。当您处理固定编号时，数组实现很有帮助。元素，因为就性能而言，调整数组的大小是昂贵的，因为如果需要从列表中间插入/删除节点，则必须在之后移动每个节点。与此相反，当您不知道否时，您应该使用指针实现。您想要的节点，因为这样的列表可以有效地增长/缩小并且您不需要移动任何节点，它可以通过简单地取消引用和引用指针来完成。

于 2013-10-19T23:01:58.840 回答