什么是数组和列表的区别？
6个回答
7
尽管在C语言中并没有类似于列表的东西，但您肯定可以谈论关于链表实现的内容。
数组：随机访问，预定义大小。 链表：顺序访问，运行时大小。
其他编程语言，比如Python，可能内置了列表和数组，并且它们的含义可能不同。
下面的有用评论：
您可以添加数组列表。列表内部是一个数组，需要时加倍，只有1/4满时减半。这使得添加、删除和获取（索引）的平摊时间复杂度为O(1)。 - lasseespeholt Python的
数组：随机访问，预定义大小。 链表：顺序访问，运行时大小。
其他编程语言，比如Python，可能内置了列表和数组，并且它们的含义可能不同。
下面的有用评论：
您可以添加数组列表。列表内部是一个数组，需要时加倍，只有1/4满时减半。这使得添加、删除和获取（索引）的平摊时间复杂度为O(1)。 - lasseespeholt Python的
list不是一个链表。Python list和array之间的区别在于，list可以存储任何东西，而数组只能存储原始类型（int、float等）。- KennyTM
- Jungle Hunter
4
5Python的
list不是链表。Python中list和array的区别在于list可以存储任何类型的数据，而array只能存储基本类型（int，float等）。 - kennytm你可以添加数组列表。列表内部是一个数组，需要时会加倍，只有1/4满时会减半。这样做可以使添加、删除和获取（按索引）的时间复杂度为O(1)。 - Lasse Espeholt
Python中的“list”实际上是其他语言称为动态大小数组的概念。 - user395760
4伙计们，我只是建议使用Python语言，因为它具有区分和内置类型的语言。 - Jungle Hunter
6
在C语言中，没有标准的列表。在C++中有这样一个东西，被实现为双向链表。
主要区别在于数组具有随机访问——可以在
主要区别在于数组具有随机访问——可以在
O(1)时间内访问数组的任何成员（即如果a是一个数组，a[4]），并且在编译时具有预设大小。链表具有顺序访问——要访问一个元素，必须遍历链表直到找到所需元素（即如果b是一个链表，则要访问b的第5个元素，必须遍历元素0、1、2、3和4），而且大小可以动态增长和缩小。- Stephen
5
@Stephen：虽然我可以指出，数组也可以使用动态内存分配在运行时设置其大小 - 它不必在编译时定义，这取决于程序员的选择。 - bguiz
每个元素的大小在编译时设置，因此您可以动态创建一个元素并不会改变查找是O(1)的事实。 - Ed S.
据我所知，纯数组的大小在编译时设置。你是指像使用
malloc和类型指针进行动态内存分配这样的操作吗？@bguiz - Stephen@Stephen：在C99中也有可变长度数组（VLA）。除了微软以外，C99被认为是“当前”的C，而C89则是“旧”的C。但我认为bguiz只是想说
malloc。 - Steve Jessop@Stephen @Steve Jessop：我不确定C语言，但在C++中，如果你在初始化数组时使用
new运算符，它将在堆上创建，而不是栈上，并且其大小在运行时确定。 - bguiz6
在 C 语言中，数组是一个固定大小的连续存储区域，包含多个对象，一个接一个。这个数组在 C 中是一个“对象”，基本上只是一些代表某个东西的内存。这个对象可以只是一个 int。您可以略微区分数组“对象”和数组“类型”。通常人们使用使用 malloc 分配的数组“对象”，并通过指向第一个元素的指针来使用它们。但是，C 也有针对不同大小的数组以及可变长度数组的特定类型。可变长度数组的名称略微具有误导性：其大小仅在创建时而非编译时被设置，并且在对象的生命周期内无法更改。所以，当我说数组是固定大小的时候，我指的是一旦创建了数组，其大小就不能更改，这包括可变长度数组。有 realloc 函数，逻辑上返回一个代替旧数组的新数组指针，但有时可能会返回传入的相同地址，并在原地更改数组的大小。realloc 只对内存分配操作，而不是一般的数组进行操作。
这就是数组。C编程语言没有定义任何称为列表的东西。不能将一个被明确定义的东西与一个未定义的东西进行比较;-) 通常，“列表”指的是链接列表，但在某些情况下或其他语言中，它可能意味着其他事情。
说到这一点，在其他语言中，“数组”可能意味着其他事情，尽管我无法立即想出一个意思与C数组非常不同的语言。
如果您的问题与C无关，并且是与语言无关的数据结构问题，“数组和链表之间的区别是什么？”，那么它是重复的： Array versus linked-list
这就是数组。C编程语言没有定义任何称为列表的东西。不能将一个被明确定义的东西与一个未定义的东西进行比较;-) 通常，“列表”指的是链接列表，但在某些情况下或其他语言中，它可能意味着其他事情。
说到这一点，在其他语言中，“数组”可能意味着其他事情，尽管我无法立即想出一个意思与C数组非常不同的语言。
如果您的问题与C无关，并且是与语言无关的数据结构问题，“数组和链表之间的区别是什么？”，那么它是重复的： Array versus linked-list
- Steve Jessop
1
我暂时想不到任何一种语言，[array] 的含义与 C 数组有很大不同。看看 PHP 的 "数组" 数据结构吧；那是我能想到的最不同的。 - Jules
2
对于数组，它有一个固定的大小，就像我们写的new int [100]，但列表没有固定的大小...它可以不断增长。
在列表中插入和删除比在数组中更容易。原因是我们可以简单地使用链接列表来更改指针以进行插入和删除，但对于数组，插入和删除需要向右或向左移动。
链接列表使用虚拟头节点来避免将元素插入空列表或从仅包含一个节点的列表中删除最后一个节点时出现特殊情况；并且，它使用双重链接允许双向迭代。当然，其成本是需要额外的空间来保存虚拟节点（最小成本），以及每个节点除了通常的下一个链接之外还需要额外的前一个链接（更显著的成本）。
在链接列表中，对尾节点的引用只需使用header.prev即可，这使我们能够在常数时间内附加到列表（无需迭代查找尾引用，也无需维护单独的尾引用）。但是，在数组中，我们需要在插入之前重新调整数组大小。
数组具有灵活性，可以实现随机访问，而链接列表则不能。
链表存在以下问题:
我们使用的指针会消耗额外的内存存储！
时间复杂度为O(n)，而不是像数组一样的O(1)
单向链表难以进行反向遍历，如果使用双向链表，则需要更多的指针来消耗额外的内存存储
还有堆限制！只有在堆中有足够的空间时才分配内存。如果内存不足，则不会创建内存。
数组存在以下问题：
可能会浪费或短缺内存。
希望这可以帮助！ :)
- Farah Nazifa
0
数组只包含相似的数据类型，即它们是同质的。我们只能有一个字符串、整数等类型的数组，而且数组的大小是预定义的。 但在列表的情况下，我们可以拥有任何类型的元素。无论是字符串、整数还是两者的组合都可以。列表中允许空值或重复元素。列表的示例包括ArrayList、LinkedList。在列表中，大小可以随时增加或缩小。
- Nandhini
0
链式数据结构经常被低估的一个特点是，你可以在内存高度碎片化的情况下使用它们，因为元素之间没有连续的内存保证。例如，你可能有100MB的空闲空间，但只有最大长度为10MB的自由内存运行。在这种情况下，你只能创建一个大小为10MB的数组，但也许可以创建一个潜在更大的链表，因为你能够利用每个足够大以包含单个节点的自由内存运行。
- DuncanACoulter
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接