1.1.5　线性链表

1.线性链表的基本概念

线性表的链式存储结构称为线性链表。为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。为此，将存储空间中的每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域，另一部分用于存放下一个数据元素的存储序号，即指向后件结点，称为指针域。在线性链表中，用一个专门的指针head指向线性链表中的第一个数据元素的结点，线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针为空，用NULL或0表示，表示链表终止。

在线性链表中，各数据元素之间的前后件关系是由各结点的指针域来指示的，指向线性表中第一个结点的指针head称为头指针，当head=NULL（或0）时称为空表。对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。

①线性单链表。在这种链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点，即在线性单链表中，只能顺指针向链尾方面进行扫描，如图1-1-10所示。

②双向链表。线性链表中的每个结点设置两个指针，一个称为左指针（Llink），用以指向其前件结点；另一个称为右指针（Rlink），用以指向其后件结点，如图1-1-11所示。

2.线性链表的基本运算

（1）在线性链表中查找指定元素

在线性链表中查找包含指定元素值的前一个结点，当找到包含指定元素的前一个结点时，就可以在该结点后插入新结点或删除该结点后的一个结点。

（2）线性链表的插入

在线性链表中插入一个新元素，首先要给该元素分配一个新结点，以便用于存储该元素的值，新结点可以从可利用栈中取得，然后将存放新元素值的结点链接到线性链表中指定的位置。

【例1-1-6】单链表的插入运算，如图1-1-12所示。

（3）线性链表的删除

在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除的结点放回到可利用栈。

【例1-1-7】单链表的删除运算，要求删除结点ai，如图1-1-13所示。

3.循环链表及其基本运算

循环链表（见图1-1-14）的结构与线性链表相比，具有以下两个特点：

①在循环链表中增加了一个表头结点，循环链表的头指针指向表头结点。

②循环链表中最后一个结点的指针域不是空，而是指向表头结点。

循环链表的基本运算主要有插入和删除，循环链表的插入和删除的方法与线性单链表基本相同。