链表和数组的区别

链表和数组的区别

参考链接：
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. 由于实际数据存储在数组的索引中，因此内存需求较少。相反，由于链表额外存储了下一个和上一个节点的引用，因此在链表中需要更多的内存。