线性表

线性表： 一个有限序列，每个表项是相继排列的，每两个相邻表项都有直接前驱和直接后继关系。

按存储方式分类

顺序表： 基于数组的存储表示，结点逻辑顺序和物理顺序一致。 单链表： 每个结点有data和link两个域。用link域（指针）表示结点间的逻辑关系，结点逻辑顺序和物理顺序不一定一样。

线性链表的其它变形

• 循环链表：最后一个结点的link域指向开始结点。【单链表是指向NULL】
• 双向链表：每个结点有前驱指针（左指针）和后继指针（右指针）两个link域。

重要相关概念

• 附加头结点：在链表第一个结点前增加“附加头结点”，它的data域可以不存放数据，也可以存放特殊标致或者表长。这样使空表与非空表第一个结点插入数据可以不作为特殊情况处理。