本节主要考查线性链表的存储方式和基本操作。

1．线性表的链式存储

在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表，如图1-4所示。

 

在链式存储方式中，要求每个节点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该节点的前一个或后一个节点（即前件节点或后件节点）。

（1）线性链表的存储结构

用一组任意的存储单元来依次存放线性表的节点，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零散分布在内存中的任意位置上的。因此，链表中节点的逻辑次序和物理次序不一定相同。为了能正确表示节点间的逻辑关系，在存储每个节点值的同时，还必须存储指示其后件节点的地址（或位置）信息，这个信息称为指针（Pointer）或链（Link）。这两部分组成了链表中的节点结构，链表正是通过每个节点的链域将线性表的n个节点按其逻辑次序链接在一起。由于上述链表的每一个节点只有一个链域，故将这种链表称为单链表（Single Linked）。

显然，单链表中每个节点的存储地址存放在其前驱节点Next域中，而开始节点无前驱节点，故应设头指针HEAD指向开始节点。同时，由于终端节点无后继节点，故终端节点的指针域为空，即NULL。

（2）线性链表的基本运算

线性链表的基本运算包括在线性链表中查找指定元素、在线性链表中插入元素、在线性链表中删除元素。

1）在线性链表中查找指定元素：在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素的前一个节点。

在链表中，查找是否有节点值等于给定值x的节点，若有的话，则返回首次找到的其值为x的节点的存储位置；否则返回NULL。查找过程从开始节点出发，顺着链表逐个将节点的值与给定值x做比较。

2）在线性链表中插入元素：线性链表的插入是指在链式存储结构下的线性链表中插入一个新元素。

插入运算是将值为x的新节点插入到表的第i-1个节点和第i个节点之间。因此，必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新节点*p，并令节点p的指针域指向新节点，新节点的指针域指向节点ai。

由线性链表的插入过程可以看出，由于插入的新节点取自于可利用栈，因此，只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新节点，不会发生“上溢”的情况。而且，由于可利用栈是公用的，多个线性链表可以共享它，从而可很方便地实现存储空间的动态分配。另外，线性链表在插入过程中不发生数据元素移动的现象，只要改变有关节点的指针即可，从而提高了插入的效率。

3）在线性链表中删除元素：线性链表的删除是指在链式存储结构下的线性链表中删除包含指定元素的节点。

删除运算是将表的第i个节点删去。因为在单链表中节点ai的存储地址是在其直接前驱节点ai-1的指针域Next中，所以必须先找到ai-1的存储位置p，然后令p->Next指向ai的直接后继节点，即把ai从链上摘下，最后释放节点ai的空间。

从线性链表的删除过程可以看出，从线性链表中删除一个元素后，不需要移动表中的数据元素，只要改变被删除元素所在节点的前驱节点的指针域即可。另外，可利用栈收集计算机中所有的空闲节点，当从线性链表中删除一个元素后，该元素的存储节点就变为空闲，应将空闲节点送回到可利用栈。