指针与数组链表的比较
一个常见的编程问题：遍历同样大小的数组和链表，哪个比较快？如果按照某些教科书上的分析方法，你会得出结论，这二者一样快，因为时间复杂度都是O（n）。但是在实践中，这二者却有极大的差异。通过下面的分析你会发现，其实数组比链表要快很多。
首先介绍一个概念：memory hierarchy（存储层次结构），计算机中存在多种不同的存储器，各存储器的平均存取速度相差很大，如表1.1所示。
表1.1
各级别的存储器速度差异非常大，CPU寄存器速度是内存速度的100倍！这就是为什么CPU生产厂家发明了CPU缓存的原因。而这个CPU缓存，就是数组链表和指针链表区别的关键所在。
CPU缓存会把一片连续的内存空间读入，因为数组结构是连续的内存地址，所以数组全部或者部分元素被连续存在CPU缓存里面，平均读取每个元素的时间只要3个CPU时钟周期。而链表的结点是分散在堆空间里面的，这时候CPU缓存帮不上忙，只能是去读取内存，平均读取时间需要100个CPU时钟周期。这样算下来，数组访问的速度比链表快33倍！（以上皆为理论数字，具体的数字视CPU型号及环境不同而略有差异）
因此，程序中尽量使用连续的数据结构，这样可以充分发挥CPU缓存的威力。这种对缓存友好的算法称为Cache-oblivious algorithm，有兴趣可以参考相关资料。再举一个简单例子，如表1.2所示。
表1.2
虽然两者执行结果一样，算法复杂度也一样，但是你会发现第二种写法要快很多。
总结一下，各种存储器的速度差异很大，在编程中绝对有必要考虑这个因素。比如，内存速度比硬盘快1万倍，所以程序中应该尽量避免频繁的硬盘读写；CPU缓存比内存快几十倍，在程序中尽量多加利用。
为了验证理论的正确性，可以通过随机化读写的测试来比较两者的差异。
测试数据如下：
data1 100000次随机插入删除操作，数据在［0，32767］之间；（删除操作较少）
data2 100000次随机插入删除操作，数据在［0，256］之间；（删除较多）
data3 100000次随机插入删除操作，数据在［0，32］之间；（删除比较频繁）
data4 1000次随机插入删除操作，数据在［0，32767］之间；
data5 1000次随机插入删除操作，数据在［0，256］之间；
data6 1000次随机插入删除操作，数据在［0，32］之间；
data7 10次随机插入删除操作，数据在［0，32767］之间；
data8 10次随机插入删除操作，数据在［0，25 6］之间；
data9 10次随机插入删除操作，数据在［0，32］之间；
Cena测试结果如图1.3所示。
图1.3
以上测试在Thinkpad T60:2.0GHz Dou CPU，1GB RAM windows XP SP3系统环境下进行。