【数据结构】顺序表与链表的区别和各自特点
顺序表与链表的区别
- 一、结构上
- 二、使用上
- 随机访问
- 在随机位置插入删除
- 空间利用率
- 缓存利用率
- 应用场景
一、结构上
顺序表：
顺序表的内核是一个数组，所以顺序表在逻辑上，和在物理上都是线性的。
链表：
链表是通过一个个独立的空间链接在一起，所以链表在逻辑上是线性的，而物理上不是线性的。
二、使用上
随机访问
当我们要随机访问元素时，顺序表和链表的侧重点是不同的。
顺序表：
可以直接通过下标访问，所以时间复杂度是O(1)
链表：
没有下标，所以只能通过遍历链表来找，所以时间复杂度是O(N)
在随机位置插入删除
顺序表：
因为顺序表是一个连续的空间，所以如果要插入或者删除，我们需要对其他元素进行移动，时间复杂度是O(N)
链表：
链表的插入删除很简单，只用改变指针的指向就行了，时间复杂度是O(N)
空间利用率
顺序表：
因为内核是数组，所以当空间不够时要开辟空间，一般每次开辟两倍，很容易会出现空间上的浪费，而且当需要开辟空间特别多时很容易开辟失败。
链表：
链表每个节点都可以存在不同的位置，随用随开，空间利用率高。
缓存利用率
首先要明白缓存是如果读取数据的
我们电脑中数据的读取是分内存和缓存的，缓存的传输速度是比内存快的当我们在程序中调用某一数据时，会先从缓存中找，若在缓存中找到了就会很快，不用再从内存中找，这个叫做缓存命中。
而缓存从内存中查找数据时，通常会将与要取出的数据后的一串数都取出，例如数组缓存一次查找就会将数组中的所有数据都取出，而在取链表中的数据时，每一次调用其中一个节点时就会将节点后面的一串数据取到缓存，这样缓存中会就会有一些无用的数，造成缓存污染
顺序表：
缓存利用率高
链表：
缓存利用率低
应用场景
顺序表：
需要快速存储大量数据时，用顺序表，因为顺序表一次开辟就可以用好久，而且可以一次开辟很大空间。
当需要频繁访问时数组的下标可以给我们提供便利。
链表：
当需要在任意位置插入删除时，链表只用改变指针。