大家好，欢迎来到IT知识分享网。

链表和数组的区别

参考链接：
https://techdifferences.com/difference-between-array-and-linked-list.html
https://www.2cto.com/kf/201605/507830.html

数组和链表之间的主要区别在于它们的结构。

• 数组是基于索引（index）的数据结构，其中每个元素都与索引相关联。
• 链表依赖于引用（reference），其中每个节点都由数据以及对上一个和下一个元素的引用组成。

比较

数组和链表之间的区别

1. 数组的大小是固定的。相比之下，链表是动态和灵活的，可以扩展和收缩其大小。
2. 在数组中，内存是在编译时分配的，而在链接列表中，内存是在执行或运行时分配的。
3. 存储位置上，数组逻辑上相邻的元素在物理存储位置上也相邻，而链表不一定。
4. 访问数组元素很快，即，如果要进入第四个元素，则必须在方括号内写入变量名称及其索引或位置。即，如果要访问第四个元素，则可以直接通过索引访问。但是，在链表中，必须从头部开始，然后一直工作到第四个元素。
5. 插入和删除时，数组平均需要移动n/2个元素，而链表只需修改指针即可。
6. 按序号查找时，数组可以直接用索引进行随机访问，时间复杂度为O(1) ，而链表不支持随机访问，平均需要O(n)。
7. 按值查找时，若数组无序，数组和链表时间复杂度均为O(N)，但是当数组有序时，可以采用二分查找将时间复杂度降为O(logN)。
8. 由于实际数据存储在数组的索引中，因此内存需求较少。相反，由于链表额外存储了下一个和上一个节点的引用，因此在链表中需要更多的内存。