一、数组的查找速度比链表快的原因

1、内存的连续性

数组在内存中的数据是连续存储的，因此通过索引计算出的内存地址是可预测的，可以直接访问到需要的元素。而链表中的元素则不是连续存储的，需要通过指针进行跳转查找，相对于数组来说，会增加一些时间成本。

2、缓存的友好性

现代计算机的缓存通常使用的是高速缓存（Cache），高速缓存是通过将最近访问的数据复制到缓存中来提高CPU的访问速度。因为数组中的元素在内存中是连续存储的，所以它们可以在一次缓存读取中同时被访问，而链表中的元素则很难做到这一点，因为访问一个节点需要跳转到另一个内存位置，这使得缓存读取变得困难和低效。

综上所述，数组具有内存连续性和缓存友好性等优点，使得它的查找速度比链表更快。而链表的优势则在于插入和删除等操作上，因为这些操作只需要改变节点的链接指针，不需要移动整个元素，所以更加灵活和高效。

二、数组与链表

数据结构主要可以分为两大模块：

线性结构非线性结构

线性结构，顾名思义，就是这些数据所有节点都能被一根线（指针）联系起来的一种结构。

线性结构的存储方式：

连续存储：数组离散存储：链表

1、数组

数组是最常见的链式存储结构，它是一段连续的内存空间。

特点：

数组是相同数据类型的元素的集合。数组中的各元素的存储是有先后顺序的，它们在内存中按照这个先后顺序连续存放在一起。数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如，a[0]表示名字为a的数组中的名列前茅个元素，a[1]代表数组a的第二个元素，以此类推。

基本使用：

初始化添加新元素插入新元素删除某个元素判断是否为空数组是否是满数组排序倒序查询是否包含某个元素

2、链表

链表是一种元素内存空间离散排列的线性数据结构。

特点：

采用动态存储分配，不会造成内存浪费和溢出。链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素。

基本使用：

创建链表遍历查找清空销毁求长度排序删除节点插入节点

3、数组和链表的区别

数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从名列前茅个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

从逻辑结构角度来看：

数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）。

从内存存储角度来看：

(静态)数组从栈中分配空间，对于程序员方便快速，但自由度小。链表从堆中分配空间，自由度大但申请管理比较麻烦。

4、数组与链表的时间复杂度

数组：

头插(vector没有此操作)：O(1)push_back：O(1)insert：O(n)erase：O(n)随机访问：O(1)

链表：

push_front（头插）：O(1)push_back：O(1)insert：O(1)erase：O(1)随机访问：O(n)

延伸阅读1：线性数据结构的概念

线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。线性结构拥有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的，链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。线性结构中存在两种操作受限的使用场景，即队列和栈。栈的操作只能在线性表的一端进行，就是我们常说的先进后出（FILO），队列的插入操作在线性表的一端进行而其他操作在线性表的另一端进行，先进先出（FIFO），由于线性结构存在两种存储结构，因此队列和栈各存在两个实现方式。