链表和数组的区别
参考链接：
https://techdifferences.com/difference-between-array-and-linked-list.html
https://www.2cto.com/kf/201605/507830.html
数组 和 链表 之间的主要区别在于它们的结构。
- 数组是基于 索引（index）的数据结构，其中每个元素都与索引相关联。
- 链表依赖于 引用（reference），其中每个节点都由数据以及对上一个和下一个元素的引用组成。
比较
比较依据 数组 链表 大小 声明时指定 无需指定，在执行时变化 储存分配 编译时分配 运行时分配 元素顺序 连续的 随机的 访问元素 使用数组索引（下标）访问：更快 从头节点遍历：比较慢 元素的插入和删除 相对较慢 更简单、更快速、更高效 搜索 二分搜索（有序）或线性搜索 线性搜索 所需内存 少 多
数组和链表之间的区别
- 数组的大小是固定的。相比之下，链表是动态和灵活的，可以扩展和收缩其大小。
- 在数组中，内存是在编译时分配的，而在链接列表中，内存是在执行或运行时分配的。
- 存储位置上，数组逻辑上相邻的元素在物理存储位置上也相邻，而链表不一定。
- 访问数组元素很快，即，如果要进入第四个元素，则必须在方括号内写入变量名称及其索引或位置。即，如果要访问第四个元素，则可以直接通过索引访问。但是，在链表中，必须从头部开始，然后一直工作到第四个元素。
- 插入和删除时，数组平均需要移动n/2个元素，而链表只需修改指针即可。
- 按序号查找时，数组可以直接用索引进行随机访问，时间复杂度为O(1) ，而链表不支持随机访问，平均需要O(n)。
- 按值查找时，若数组无序，数组和链表时间复杂度均为O(N)，但是当数组有序时，可以采用二分查找将时间复杂度降为O(logN)。
- 由于实际数据存储在数组的索引中，因此内存需求较少。相反，由于链表额外存储了下一个和上一个节点的引用，因此在链表中需要更多的内存。
Original: https://www.cnblogs.com/QY428/p/16032838.html
Author: QY428
Title: 链表和数组的区别
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583624/
转载文章受原作者版权保护。转载请注明原作者出处！