数据结构——线性表
线性表属于数据结构中的线性结构，线性结构具体有以下特征：
- 集合中必存在唯一的一个第一个元素；
- 集合中必存在唯一的一个最后的元素；
- 除最后元素之外，其它数据元素均有唯一的后继；
- 除第一元素之外，其它数据元素均有唯一的前驱；
线性表是一个含有n ≥ 0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1，k2，…，kn，其中k1是开始结点，kn是终端结点。
线性表包含下列基本操作：初始化、销毁、重置为空表、判断是否为空、获取长度、根据位置获取对应元素、查找元素、获取指定元素的前驱和后继元素、插入元素、删除元素、遍历元素。
线性表的顺序表示和实现
线性表的顺序表示指的是用物理上的一段连续的地址来存储数据元素，如下图所示。如果第一个元素的在内存上的地址为a1，每个元素占用的空间是l，那么第n个元素的地址就是a1+(n-1) x l。
| 内存中的存储位置 | Row 1 is |
|---|---|
| a1 | 1 |
| a1 + l | 2 |
| a1 + 2l | 3 |
| … | … |
| … | … |
| … | … |
| a1+(n-1) x l | n |
线性表的链式表示和实现
线性表的顺序存储结构是逻辑位置和物理位置都相邻，而链式存储结构是逻辑位置相邻，但物理位置不一定相邻，相比顺序存储结构，它不能随机存取，但在插入和删除操作时不需要移动元素，大大提高了增加和删除元素的效率。
通常链式存储结构会有一个个结点组成，结点中包含两个域一个是数据域，一个是指针域，数据域中存储数据，指针域中存储下一个后继元素的地址，如下图所示，这一个个结点组成链表，也称线性链表或单链表。
除此之外，还有循环链表和双向链表。