引子

顺序存储

假设有一个数组 [1,2,3,4,5], 是一个连续的内存地址

100 | #101 | #102 | #103 | #104

---|--- | ---|--- | ---
1 | 2 | 3 | 4 | 5

设计get/set/insert/delete/update/length API

时间复杂度上:

get(index)： 1，

set(index, val)： 1，

insert(index, val): n - index + 1 (如果内存地址不够了，需要移到一个新的连续内存)

delete(index): n - index + 1

length: 尝试选择几种方法

• 每次找length就遍历一遍，那么就要: n
• 在连续地址前或者后再加一个地址存length，消耗一个空间，但是只要1 （大多数语言是这么做的）

以上的设计连续地址，我们称之为顺序存储，好处就是改查很快，但是要求地址连续

所以我们平时遇到的数组下标是从0开始的，如array[3]就是array的地址(#100)偏移3个位置

链式存储

还是这个数组 [1,2,3,4,5], 这次使用链式存储，不需要连续的内存空间

0	1	2	3	4
1 -- #100	2 -- #233	3 -- #789	4 -- #999	5 -- null

数组的每个单元存着它的值和下一个单元的地址，在遍历的时候，会一直往下一个地址寻址，直到遇到null，表示末端

同样我们设计一些API

get(index)： index，

set(index, val)： index + 1，

insert(index, val): index + 1 + 1 (上一个的地址指向新生成的，新生成的地址指向原本的下一个)

delete(index): index + 1

再一看，链接存储的所有API的时间复杂度都是n，相比顺序存储并没有任何优势。但是业界上我们的确可以看到优秀链式存储例子。这是为什么呢？

假设我们更换一下API，item数组中的一个节点:

get(item)： index，

set(item, val)： 1，

insert(item, val): 1 (直接根据val生成一个节点然后插入item)

delete(item): 1 (删除iterm的下一个)

length: 不变

可以得出一个结论，根据设计的API不同，顺序存储适合查和改，链接存储适合增加和删除

数据结构

数据结构 = 数据 + 逻辑结构 + API

• 数据（不可控）
• 逻辑机构：用结构解释数据，如线性表，树，图
• API：逻辑结构需要搭配合适的API，程序员需要研究存储结构以加速API

逻辑结构举例

• 线性表 linear list
• 树型结构
• 哈希结构
• 图
• 其他

存储结构举例

• 顺序存储
• 链接存储
• 混合存储（一小块一小块的链接，小块是连续的）
• 其他

API举例

• 队列： 如果提供入列enqueue和出列dequeue API，那就是队列
• 栈：如果提供压栈push和弹栈pop的API，那就是栈
• 二叉堆

有些API相对简单，有些则相对复杂，是在基础API上的扩展，
如红黑树拥有树的所有API，再扩展了自己红白和自旋等特征

总结

核心： 数据结构 = 数据 + 逻辑结构 + API

在我写这篇文章前，对数据结构的概念很模糊，堆/栈/队列/哈希/链表 ，大多数情况下把这几个概念混淆了

这次将这几个概念分开来理解，发现每一块都有自己独立的领域，又有互相作用的地方。通过一个数组的存储，可以了解为什么存在存储结构这样的东西。通过对各种API的研究，直到了只有合适的API，特定的存储结构才能发光。

勿混淆