phi*_*mue 49
两者都存储一系列元素,但使用不同的技术.
一个阵列存储在连续顺序元素存储器,即它看起来像如下:
--------------------------------------------------------------------------------------
| item 1 | item 2 | item 3 | ... ... | item x | //here comes other stuff
--------------------------------------------------------------------------------------
这意味着,元素在内存中是一个接一个连续的.
另一方面,((双重)链接)列表以下列方式存储项目:它为每个元素创建一个自己的"列表项"; 这个"列表项"将实际元素和指针/引用/提示/等保存到下一个"列表项".如果它是双向链接,它还包含指向前一个"列表项"的指针/引用/提示/ etc:
------------
------------ ---------- | item 4 |
| item 1 | | item 2 | | next ---+----...
| next ---+------->| next | ------------
------------ ---+------ ^
| |
| |
v |
---------- |
| item 3 | |
| next --+---+
----------
这意味着,元素可以遍布整个存储器,而不是存储在特定的存储位置.
现在我们知道这一点,我们可以比较一些元素序列的常规操作:
访问特定索引处的元素:使用数组,我们只需计算此索引的偏移量,并将元素放在索引处.
这很便宜.另一方面,使用列表,我们不知道存储索引元素的先验(因为所有元素都可以在内存中的任何位置),所以我们必须逐项遍历列表,直到我们在索引处找到元素.这是一项昂贵的操作.
在序列的末尾添加一个新元素:使用数组可能会导致以下问题:数组通常具有固定大小,因此如果我们的数组已经完全填充(请参阅//here comes other stuff参考资料),我们可能无法放置那里的新元素因为可能已经存在其他东西了.所以,也许我们必须复制整个数组.但是,如果未填充数组,我们可以简单地将元素放在那里.
使用列表,我们必须生成一个新的"列表项",将元素放入其中,并将next当前最后一个元素的指针设置为此新列表项.通常,我们存储对当前最后一个元素的引用,这样我们就不必搜索整个列表来查找它.因此,插入新元素对列表来说不是问题.
在中间的某处添加一个新元素:让我们首先考虑数组:在这里,我们可能会遇到以下情况:我们有一个元素为1到1000的数组:
1 | 2 | 3 | 4 | 5 | 6 | ... | 999 | 1000 | free | free
现在,我们要插入4.5之间4和5:这意味着,我们必须移动所有的元素5到1000一个合适的位置,以腾出空间为4.5:
1 | 2 | 3 | 4 | free | 5 | 6 | ... | 999 | 1000 | free
||
vv
1 | 2 | 3 | 4 | 4.5 | 5 | 6 | ... | 999 | 1000 | free
移动所有这些元素是一项非常昂贵的操作.所以最好不要经常这样做.
现在我们考虑一下列表如何执行此任务:假设我们目前有以下列表:
1 -> 2 -> 3 -> 4 -> 5 -> ... -> 999 -> 1000
同样,我们想4.5在4和之间插入5.这可以很容易地完成:我们生成一个新的列表项并更新指针/引用:
1 -> 2 -> 3 -> 4 5 -> ... -> 999 -> 1000
| ^
+-> 4.5 -+
我们只是创建了一个新的列表元素并生成了一种"旁路"来插入它 - 非常便宜(只要我们有一个指向列表项的指针/引用,之后将插入新元素).
所以,让我们总结一下:链接列表在随机位置插入时非常好(只要你有一个指向适当列表项的指针).如果您的操作涉及动态添加大量元素并且无论如何遍历所有元素,那么列表可能是一个不错的选择.
一个数组是非常好的,当谈到索引来访问.如果您的应用程序需要经常访问特定位置的元素,则应该使用数组.
值得注意的事情:
解决数组的固定大小问题:如前所述,(原始)数组通常具有固定大小.然而,现在这个问题已不再是真正的问题,因为几乎所有的编程语言都提供了生成数据的机制,这些数据可以根据需要动态增长(并可能缩小).这个增长和收缩可以被实现为使得我们已经摊销用于插入和移除元件(在阵列的端部),并使得程序员不必调用O(1)的运行时间grow和shrink明确.
由于列表为插入提供了很好的属性,因此它们可以用作搜索树的基础数据结构等.即,您构建一个搜索树,其最低级别由链表组成.
数组具有固定的大小但访问速度更快:它们分配在一个地方,每个元素的位置都是已知的(您可以跳转到正确的元素).
列表的大小不受限制,但可用内存量不受限制.它们访问速度较慢,因为要查找必须遍历列表的元素.
这是一个非常简短的解释:我建议你拿一本关于数据结构的书并阅读它.这些是您需要完全理解的基本概念.
小智 5
由于您使用"数据结构"标记了问题,我将在该上下文中回答这个问题.
声明/创建数组时,数组的大小是固定的,这意味着您无法向其中添加更多元素.因此,如果我有一个数组,比如5个元素,你可以用它做任何你想做的事情,但你不能添加更多的元素.
链表基本上是一种表示列表的方式,您可以在其中拥有尽可能多的"项目".它由列表中的头(第一个元素),尾部(最后一个元素)和元素(称为节点)组成.
您可能会在任何数据结构类中遇到许多类型的链接列表.
在学习如何在类中创建指向其他对象的字段时,您将学习链接列表的关键是熟练,这就是链接列表的情况,您需要构建列表,使每个节点指向下一个节点.
显然,这是一个非常普遍的答案.它应该为你的课程提供一个想法.