数据结构学习篇（5）---顺序表和链表的区别

对于顺序表和链表的异同，上面这个表格直观展示了两者的不同之处，有几点可以做一下解释：顺序表和链表在逻辑结构上都是连续的，但是在物理结构，也就是存储空间上，顺序表是连续的，因为他的本质是数组，而链表是不连续的；其次在随机访问方面，顺序表是可以直接通过下标来访问其中的数据的，这个操作对应的时间复杂度为O(N)，但是对于链表而言则无法进行这种操作，它是需要遍历其中的每一个节点才可以对数据进行访问，这就涉及到循环，所以对应的时间复杂度为O(N)；对于两者在插入数据方面，链表是优于顺序表的，因为顺序表在进行扩容操作时，往往是按照原来容量的两倍进行操作，这就可能会导致空间过剩或空间不足，而当空间不足时又要进行下一次的空间扩容，这对时间和空间都会造成损耗，相对于链表而言就没有这一说，想要进行数据增加只需要增加相应节点即可，时间上得到了保证同时空间也不会产生浪费。

对于缓存利用率这点，则需要做一些扩展来进行解释：

这副图片直观展示了计算机存储数据的方式，其中对于寄存器而言，可以理解为是存储一些小的数据，而往下的三个高速储存器则是储存一些大的数据，当然这些数据都是经过缓存的，通常数据存储在内存当中，也就是L4；如果cpu要对数据进行处理，则需要先判断所需数据有没有被缓存，如果已经提前缓存好了，那么“缓存命中”，则可以直接对这些数据进行访问，如果没有进行缓存，说明“缓存不命中”，那么就要把数据从内存加载到缓存中，也就是前四级中，那么这个加载过程并不是对数据进行一个一个的缓存，而是缓存所需数据及其后面跟着的一块数据集，这些数据 的地址都是连续的，所以对于顺序表而言，因为其存储空间是连续的，所以cpu要对一个顺序表里面的数据进行访问时，能够先直接将一整块数据进行缓存然后进行访问，这样的话缓存利用率就很高，但是对于链表而言，因为它的存储空间并不连续，所以对里面的数据进行一整块缓存时，就会缓存一些不必要的数据而导致缓存污染，这也就说明链表的缓存利用率低。