小菜学编程
在计算机程序中，有很多场景都需要用到有序序列：从数据库查出来的一组记录、UI 上供用户选择的下拉选项、内存管理器中的空闲内存块等等。
我们将这种由若干具有相同特性的元素组成的有序集合，称为 线性表（ linear list ）。线性表可以说是一种最简单的数据结构，却又很常用。
线性表本质上就是一个有序序列，序列元素可以是简单的基本数据类型，例如整数；也可以是复杂的数据记录，例如包含多个字段的结构体；甚至可以是指向具体数据的内存地址，例如指针。
线性表存储可以分为顺序存储和链式存储两种，存储方式则决定操作效率。
顺序存储
顺序存储顾名思义，就是分配一块连续的内存，将元素依次保存在里面。
大部分编程语言都支持的 数组（ array ），就是一种顺序存储线性表。数组内存是连续的，每个元素依次保存，并可以通过下标来访问。根据实现方式不同，数组又可以分为两类：
- 普通数组，数组分配后，大小就保持不变；
- 动态数组（ dynamic array ），数组大小可以根据需要动态调整（既可扩容，又可缩容）；
链式存储
由于顺序存储结构不利于插入和删除，这时我们可以采用另一种存储方式—— 链式存储（ linked storage ）。链式存储将数据组织成一个个 节点（ node ），节点保存指向下一个节点的指针，由此串成一个有序序列。
这种存储结构被形象地称为 链表（ linked list ），根据实现细节又可进一步分为：
- 单链表（ single linked list ），每个节点只有一个 后向指针（ back pointer ）；
- 双向链表（ double linked list ），每个节点 前向指针（ forward pointer ）和 后向指针 各有一个；
- 循环链表（ circular linked list ），头部节点和尾部节点节点连在一起构成一个环；
【小菜学算法】系列文章首发于公众号【小菜学编程】，敬请关注：
