简介

线性表的定义

线性表是日常生活中非常常见的例子。 我们在第一章已经见过线性表的定义了，就是前后相邻串接在一起的形式：

还是要注意，这里的箭头并不代表指针，只是说明存在前后关系。

显然除去第一个节点和最后一个节点，顺序表中的任意一个节点都有前驱(prev)和后继(next)。 一般的我们也允许空表的存在。

线性表的这种结构和数组很像，所以大家应该对其并不会陌生。

线性表的基本操作

我们对线性表的要求会比数组更复杂一些。一般来说数组创建并初始化之后，我们很少会在中间插入一个元素，或者删除某个元素；但对线性表我们可能会有类似的要求。此外数组一般我们不考虑销毁和创建的问题，而为了体现完整的ADT实现，我们也需要考虑线性表的初始化和销毁。此外我们可能需要在线性表中搜索某个元素，这种搜索可能是搜索第N号元素，也可能是搜索值等于V的元素。

我们总结一下，基本需要以下操作：

1. 初始化和销毁
2. 在整体元素的最后添加数据
3. 在任意位置插入新元素
4. 删除指定位置的新元素
5. 获得第N位的元素
6. 获得值为V的元素

具体的实现我们会在顺序表和链表的章节讨论。