本文共 1455 字，大约阅读时间需要 4 分钟。

1、寻址操作次数链表要多一些。数组只需对 [基地址+元素大小*k] 就能找到第k个元素的地址，对其取地址就能获得该元素。链表要获得第k个元素，首先要在其第k-1个元素寻找到其next指针偏移，再将next指针作为地址获得值，这样就要从第一个元素找起，多了多步寻址操作，当数据量大且其它操作较少时，这就有差距了。

2、CPU缓存会把一片连续的内存空间读入，因为数组结构是连续的内存地址，所以数组全部或者部分元素被连续存在CPU缓存里面，平均读取每个元素的时间只要3个CPU时钟周期。   而链表的节点是分散在堆空间里面的，这时候CPU缓存帮不上忙，只能是去读取内存，平均读取时间需要100个CPU时钟周期。这样算下来，数组访问的速度比链表快33倍！ （这里只是介绍概念，具体的数字因CPU而异）

 

另1：

一般来说数组的查询速度快于链表，原理是什么？

电脑中存在多种不同的存储器，如下表

• 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缓存会把一片连续的内存空间读入， 因为数组结构是连续的内存地址，所以数组全部或者部分元素被连续存在CPU缓存里面， 平均读取每个元素的时间只要3个CPU时钟周期。   而链表的节点是分散在堆空间里面的，这时候CPU缓存帮不上忙，只能是去读取内存，平均读取时间需要100个CPU时钟周期。 这样算下来，数组访问的速度比链表快33倍！ （这里只是介绍概念，具体的数字因CPU而异）

因此，程序中尽量使用连续的数据结构，这样可以充分发挥CPU缓存的威力。

总结一下， 各种存储器的速度差异很大，在编程中绝对有必要考虑这个因素。 比如，内存速度比硬盘快1万倍，所以程序中应该尽量避免频繁的硬盘读写；CPU缓存比内存快几十倍，在程序中尽量多加利用。

 

另2：

1.看待数组时，要把数组看成两部分：一部分是数组引用，即在代码中定义的数组引用变量；另一部分是实际的数组对象，这部分是在堆内存里运行的，通常无法直接访问，只能通过数组引用变量来访问。

2.定义并初始化一个数组之后，在内存中分配了两个空间，一个用于存放数组的引用变量，另一个用于存放引用变量所指向的数组本身。

例如：

         

栈内存中存储所定义并初始化的引用变量arr，堆内存中存储arr指向的4个数组arr[0],arr[1],arr[2],arr[3]

3.如果堆内存中数组不再有任何引用变量指向自己，则这个数组将变成垃圾，会被系统的自动回收机制回收。为了让垃圾回收机制回收一个数组所占用的内存空间，可以将该数组变量赋值为null

附：

栈内存：

     所有方法中定义的局部变量都是放在栈内存中的，随着方法的结束，这个方法的内存栈也将自然销毁

堆内存：

      在程序中创建一个对象时，这个对象会被保存在一运行时的数据区里，以便反复利用，此数据区即为堆内存。

      每一个实体都有内存地址值，此内存地址存储在栈内存里。