为什么有人想要使用链表而不是数组?

毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。

我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?

这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。


当前回答

链表比数组的维护开销更大,它还需要额外的内存存储,所有这些都是一致的。但是有一些事情是数组做不到的。在很多情况下,假设你想要一个长度为10^9的数组你无法得到它,因为必须有一个连续的内存位置。链表可能是这里的救世主。

假设你想用数据存储多个东西,那么它们可以很容易地扩展到链表中。

STL容器通常在后台有链表实现。

其他回答

Arrays make sense where the exact number of items will be known, and where searching by index makes sense. For example, if I wanted to store the exact state of my video output at a given moment without compression I would probably use an array of size [1024][768]. This will provide me with exactly what I need, and a list would be much, much slower to get the value of a given pixel. In places where an array does not make sense there are generally better data types than a list to deal with data effectively.

数组Vs链表:

由于内存碎片,阵列内存分配有时会失败。 在数组中缓存更好,因为所有元素都分配了连续的内存空间。 编码比数组更复杂。 与数组不同,在链表上没有大小限制 在链表中插入/删除更快,在数组中访问更快。 从多线程的角度来看,链表更好。

当集合不断增加和减少时,链表尤其有用。例如,很难想象尝试使用数组实现一个Queue(添加到末尾,从前面删除)—您将花费所有时间向下移动内容。另一方面,对于链表来说,这是微不足道的。

没有人再编写自己的链表了。那太愚蠢了。使用链表需要更多代码的前提是错误的。

如今,构建链表只是学生们的一个练习,以便他们能够理解这个概念。相反,每个人都使用预先构建的列表。在c++中,根据我们问题中的描述,这可能意味着stl向量(#include <vector>)。

因此,选择链表还是数组完全是权衡每个结构相对于应用程序需求的不同特征。克服额外的编程负担应该对决策没有任何影响。

链表

它更可取的时候,它涉及到插入!基本上它所做的就是处理指针

1 -> 3 -> 4

插入(2)

1... 3... 4 ... 2

最后

1 -> 2 -> 3 -> 4

一个箭头指向3点,另一个箭头指向2点

简单!

但是来自Array

| | 1 | 3 | 4

插入(2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

任何人都可以想象出其中的不同! 对于4个索引,我们执行3个步骤

如果数组长度是一百万呢?数组有效吗? 答案是否定的!:)

删除也是一样! 在链表中,我们可以简单地使用指针并将对象类中的元素和next置空! 但对于数组,我们需要执行shiftLeft()

希望有帮助!:)