- 概述：
数组，就是用一块连续的内存空间来存储数据，因此拥有可随机访问的特点，所以它访问任何位置的时间复杂度都是O(1)。那如果我申请不到连续的内存空间怎么办？这时候链表就可以派上用场了。
链表可以申请不连续的空间，通过一个指针按顺序将这些空间串起来，形成一条链，链表也正是因此得名。不过，严格意义上来说，这个叫单链表。链表的检索能力偏弱，作为弥补，它在动态调整上会更容易。我们可以以 O(1) 的时间代价完成节点的插入和删除，
数组和链表分别代表了连续空间和不连续空间的最基础的存储方式，它们是线性表（Linear List）的典型代表。其他所有的数据结构，比如栈、队列、二叉树、B+ 树等，都不外乎是这两者的结合和变化。以栈为例，它本质就是一个限制了读写位置的数组，特点是只允许后进先出。
- 特点
数组：检索强、增删弱。因为数组存储空间连续、固定，所以可随机访问 O(1)，而增删时则需要重新申请数组来存储，无法做到动态调整。
链表：增删强、检索弱 O(n)。因为链表空间不连续，是通过指针串联空间，所以访问每个数据的时间复杂度是O(n)。但增删时可直接更改增删位置相邻元素的指针即可，所以做到了动态调整。
- 检索的核心思路
检索的核心思路，其实就是通过合理组织数据，尽可能地快速减少查询范围。对于规模较大的数据集，我们往往是先将它通过排序算法转为有序的数据集，然后通过一些检索算法，比如二分查找算法 O(log n)来完成高效的检索。
- 改造链表提升检索效率
本质上，我们学习链表，就是在学习“非连续存储空间”的组织方案。
改进方案一：让链表每个节点不再只是存储一个元素，而是存储一个小的数组。这样我们就能大幅减少节点的数量，从而减少依次遍历节点带来的“低寻址效率”。如下图：
若有收获，就点个赞吧
0 人点赞
