一般面试大概率会问到数组与链表的比较，那大家一定都知道数组的查找效率优于链表，那么为什么会这样呢，我们今天来仔细分析下原因。
一、什么是数组？
我想大家应该都知道答案：数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
有两个关键词：
线性表顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。
内存连续，数据类型相同因为这两个特性，数组才有了一个强大的特性：随机访问
这也是面试中常用的回答，数组直接根据下标地址定位到元素，链表要遍历元素找到指定的元素！
二、说到数据的访问，那你知道数组是如何实现根据下标随机访问数组元素的吗？
我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：
a[i]_address = base_address + i * data_type_size当我们要找a[2]的时候，直接根据公式就可以定位到地址（1000 + 2*4）这也是内存连续带来的好处。而链表则要先拿到第一个元素，在通过next指向的地址找到第二个元素，依次操作。。。
三、还有一种解释！
CPU缓存会把一片连续的内存空间读入，因为数组结构是连续的内存地址，所以数组全部或者部分元素被连续存在CPU缓存里面，平均读取每个元素的时间只要3个CPU时钟周期。 而链表的节点是分散在堆空间里面的，这时候CPU缓存帮不上忙，只能是去读取内存，平均读取时间需要100个CPU时钟周期。这样算下来，数组访问的速度比链表快33倍！（这个数据我也没试过，不清楚哈）
https://blog.csdn.net/islandww/article/details/72511737
ps:（图片来源：《数据结构与算法之美》）
