1. 遍历速度
虽然遍历数组和链表的时间复杂度都是O(n),但是在实际中数组的速度要比链表快,这是为什么呢?
数组在内存中的地址是连续相邻的,而链表在内存的地址是散列的,不连续的
-
CPU缓存会把一片连续的内存空间读入, 因为数组结构是连续的内存地址, 所以数组全部或者部分元素被连续存
在CPU缓存里面,而链表的节点是分散在堆空间里面的,这时候CPU缓存帮不上忙,只能是去读取内存,
而缓存的速率要比内存快。
2. 插入删除比较
- 数组的中间插入(或删除)一个元素,那么这个元素后的所有元素的内存地址都要往后(前)移动(数组的内存地址是连续的),对最后一个元素插入(或删除)时才比较快
- 而链表不需要改变内存的地址,只需要修改节点的信息即可(包括指针指向,节点值)。
- 链表的扩展性较好,定义数组时所占用的空间大小都是固定的,如果存储满了,无法扩展,只能新建一个更大空间的数组。
所以可得知:
数组大小固定,不适合动态存储,动态添加,内存为一连续的地址,可随机访问,查询较快,
而链表大小可变,扩展性强,只能顺着指针的方向查询,速度较慢。