线性表

将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称顺序表）；
数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构（简称链表）；

也就是说，线性表存储结构可细分为顺序存储结构和链式存储结构。

某一元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素”；
某一元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素”；

定义顺序表：

typedef struct Table{
    int * head;//声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length;//记录当前顺序表的长度
    int size;//记录顺序表分配的存储容量
}table;

链表中每个数据的存储都由以下两部分组成：

数据元素本身，其所在的区域称为数据域；
指向直接后继元素的指针，所在的区域称为指针域；

链表中每个节点的具体实现：

typedef struct Link{
    char elem; //代表数据域
    struct Link * next; //代表指针域，指向直接后继元素
}link; //link为节点名，每个节点都是一个 link 结构体

提示，由于指针域中的指针要指向的也是一个节点，因此要声明为 Link 类型（这里要写成 struct Link* 的形式）。

头节点，头指针和首元节点

一个完整的链表需要由以下几部分构成：

头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；

节点：链表中的节点又细分为头节点、首元节点和其他节点：

头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；

首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；

其他节点：链表中其他的节点；

单链表的创建分为头插入法和尾插入法两种，两者并无本质上的不同，都是利用指针指向下一个结点元素的方式进行逐个创建，只不过使用头插入法最终得到的结果是逆序的。

链表插入元素，只需做以下两步操作，即可将新元素插入到指定的位置：

1.将新结点的 next 指针指向插入位置后的结点；
2.将插入位置前结点的 next 指针指向插入结点；

注意：链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行步骤 2，会导致插入位置后续的部分链表丢失，无法再实现步骤 1。

从链表中删除数据元素需要进行以下 2 步操作：

将结点从链表中摘下来;
手动释放掉结点，回收被结点占用的存储空间;

其中，从链表上摘除某节点的实现非常简单，只需找到该节点的直接前驱节点 temp，执行一行程序：
temp->next=temp->next->next;

双向链表中各节点包含以下 3 部分信息：

指针域：用于指向当前节点的直接前驱节点；
数据域：用于存储数据元素；
指针域：用于指向当前节点的直接后继节点。

双链表的节点结构用 C 语言实现为：

typedef struct line{
    struct line * prior; //指向直接前趋
    int data;
    struct line * next; //指向直接后继
}line;

双向链表添加节点

根据数据添加到双向链表中的位置不同，可细分为以下 3 种情况：

1. 添加至表头
   将新数据元素添加到表头，只需要将该元素与表头元素建立双层逻辑关系即可。

换句话说，假设新元素节点为 temp，表头节点为 head，则需要做以下 2 步操作即可：
temp->next=head; head->prior=temp;
将 head 移至 temp，重新指向新的表头；

2. 添加至表的中间位置
   同单链表添加数据类似，双向链表中间位置添加数据需要经过以下 2 个步骤：
   新节点先与其直接后继节点建立双层逻辑关系；
   新节点的直接前驱节点与之建立双层逻辑关系；

3. 添加至表尾
   与添加到表头是一个道理，实现过程如下：
   找到双链表中最后一个节点；
   让新节点与最后一个节点进行双层逻辑关系；