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