虽然前面有写到LinkedList与ArrayList的增删改查效率的全面比较，但回想一下还是有必要对这两者的查询效率做一个单独的比较，也能进一步加深理解。这次分底层数据结构和CPU缓存两方面展开它们分别对查询效率的阐述。

一、底层数据结构对查询效率的影响

1.ArrayList底层数据结构

ArrayList底层数据结构是动态数组,创建数组时会给它分配一整段连续的物理内存空间,只要知道数组首地址和数组存储的元素类型,就可以根据指定索引值直接推导得出该索引位置对应的内存地址,进而就可以直接访问得到到该内存地址上存储的具体元素:
 数组存储的元素都是相同类型：
第n个元素地址=首地址+(元素类型类型长度单位)n。
 数组存储的元素是不同类型：
第n个元素地址=首地址+(第1个元素类型类型长度单位) +…+(第n个元素类型类型长度单位)。
代码如下：

public E get(int index) {
   
    rangeCheck(index);
    return elementData(index);
}
E elementData(int index) {
   
    return (E) elementData[index];
}

2.LinkedList底层数据结构

LinkedList底层数据结构是双向链表(因其每个节点Node中同时记录了该节点的的前一个节点prev和后一个节点next),链表在逻辑上是连续的，但在实际物理内存上却不是一整段连续的内存块；这样的底层数据结构限制了其不能像数组一样根据索引值直接推导得出某个索引位置对应的内存地址。而只能通过递进遍历的方式去一步步移动到要查询的索引位置，然后才能访问得到对应索引位置上的元素,递进的开始方向分两种：
 当要检索的索引位置index小于数组长度的一半size>>1时，则从数组头部first开始从前往后next遍历，直到移动到index所在位置：
 当要检索的索引位置index大于数组长度的一半size>>1时，则从数组尾部last开始从后向前prev遍历，直到移动到index所在位置；
代码如下：

public E get(int index) {
   
    checkElementIndex(index);
    return node(index).item;
}
Node<E> node(int index) {
   
    // assert isElementIndex(index);
    if (index < (size >> 1)) {
   
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
   
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

小结1：从上述1、2点可以很明显看出，底层数据结构对两者的查询效率的影响，ArrayList得益于数组结构的随机访问特性，查询的时间复杂度为O(1)；而LinkedList囿于其链表结构，查询的时间复杂度高于ArrayList，达到O(n)。

二、CPU缓存对查询效率的影响

不能单说CPU缓存，要拿CPU中的寄存器/一级缓存/二级缓存/内存/硬盘这些不同的存储器，对比着来说，这样才能看出端倪：
CPU寄存器-immediate access(0-1个CPU时钟周期)
CPU L1缓存-fast access(3个CPU时钟周期)
CPU L2缓存-slightly slower access(10个CPU时钟周期)
内存(RAM)-slow access(100个CPU时钟周期)
硬盘(file system)-very slow(10,000,000个CPU时钟周期)
可以看出，各级别的存储器速度差异很大，CPU寄存器是内存速度的100倍之多！这就是为什么CPU厂商发明CPU缓存的原因,为了弥补内存访问速度过慢和CPU执行速度过快的差异。而这个CPU缓存，会对数组和链表的查询效率产生很不一样的影响。

1. CPU缓存对数组友好

CPU缓存会把一整片连续的内存空间读入，因为数组结构是连续的内存，所以数组全部或部分元素会被连续存在CPU缓里面，平均读取每个元素的时间只要3个CPU时钟周期 。

2. CPU缓存对链表不友好

由于链表结构是非连续的内存，所以这时候CPU缓存帮不上忙，只能去读取内存，而读取内存中元素的平均耗时为100个CPU时钟周期。

小结2：由于CPU缓存对数组的助力，数组的查询效率比链表快了33倍！

三、疑问：CPU缓存会对数组的增加删除操作起到助力么？

尝试解答：应该不会。

因为CPU缓存属于存储性质，应该不可以在其中做增删操作。假设，数组增删操作真的也在CPU缓存中进行，当删除某个数组元素时，需要将该元素所在索引位置后面的连续内存块都应该向前移动一位，增加时则都需要向后移动一位。就是说，需要想办法对缓存内的数据进行修改，而且这还只是在缓存里修改了，修改后还需要将结果取出来，覆盖到实际的内存上，否则只是改了副本，实际的本体却没得到修改。想想就很麻烦。

而且通过查找资料，了解到，CPU缓存只对CPU开放。

只有CPU可以对缓存进行读写操作，当cpu想要访问内存数据时，会先到缓存中查看数据是否已存在，若存在则直接从缓存读取，若缓存中不存在，则会先把数据从内存加载进缓存，再进行读取。就是说，缓存中的数据是来源于内存的，是内存数据的拷贝，内存决定了缓存的内容，但是缓存里缓存的内容无法影响到内存。就像人影被光线拉长，但人的身高还是不会变的。

四、总结

以前只知其一，而不知其二，没有想到数组和链表的查询效率还与CPU缓存有联系。多逛逛技术社区还是收获蛮多的，可以拓展视界，对某个知识点能了解更多，思考的时候也有了方向，不会漫无目的绕很多的弯路,认识也更深刻。
ava