目录
2.3线性表的链式表示
2.3.1单链表的定义
【单链表的应用(2009、2012、2013、2015、2016、2019)】
2.3.2单链表上基本操作的实现
【单链表插入操作后地址或指针的变化(2016)】
2.3.3双链表
【双链表中插入操作的实现(2023)】
【循环双链表中删除操作的实现(2016)】
2.3.4循环链表
【循环单链表中删除首元素的操作(2021)】
2.3线性表的链式表示
2.3.1单链表的定义
【单链表的应用(2009、2012、2013、2015、2016、2019)】
线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。
为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息之外，还需要存放一个指向其后继的指针。
单链表中结点类型的描述如下:
typedef struct INode{ //定义单链表结点类型
ElemType data; //数据域
struct LNode *next; //指针域
}LNode, *LinkList;
利用单链表可以解决顺序表需要大量连续存储单元的缺点，但附加的指针域，也存在浪费存储空间的缺点。
由于单链表的元素离散地分布在存储空间中，因此是非随机存取的存储结构，即不能直接找到表中某个特定结点。查找特定结点时，需要从表头开始遍历，依次查找。
2.3.2单链表上基本操作的实现
【单链表插入操作后地址或指针的变化(2016)】
插入结点操作将值为x的新结点插入到单链表的第i个位置。
先检查插入位置的合法性，然后找到待插入位置的前驱，即第i-1个结点，再在其后插入。其操作过程如图 2.5 所示。
首先査找第 i-1 个结点，假设第 i-1 个结点为*p，然后令新结点*s的指针域指向*p的后继，再令结点*p的指针域指向新插入的结点*s。
bool ListInsert(linklist &L,int i,ElemType e)
LNode *p=L; //指针p指向当前扫描到的结点
int j=0; //记录当前结点的位序，头结点是第0个结点
while(p!=NULL&&j<i-1){ //循环找到第i-1个结点
p=p->next;
j++;
}
if(p==NULL) //i值不合法
return false;
LNode *s=(LNode*)malloc(sizeof(LNode));
s->data=e;
s->next=p->next; //①
p->next=s; //②
return true;
}
插入时，①和②的顺序不能颠倒，否则，先执行p->next=s 后，指向其原后继的指针就不存在了，再执行 s->next=p->next 时，相当于执行了 s->next=s，显然有误。
本算法主要的时间开销在于查找第 i-1 个元素，时间复杂度为 O(n)。
若在指定结点后插入新结点，则时间复杂度仅为 O(1)。
需注意的是，当链表不带头结点时，需要判断插入位置i是否为1，若是，则要做特殊处理，将头指针工指向新的首结点。
当链表带头结点时,插入位置i为1时不用做特殊处理。
扩展:对某一结点进行前插操作。
前插操作是指在某结点的前面插入一个新结点，后插操作的定义刚好与之相反。
在单链表插入算法中，通常都采用后插操作。以上面的算法为例，先找到第 i-1 个结点，即插入结点的前驱,再对其执行后插操作。由此可知，对结点的前插操作均可转化为后插操作，前提是从单链表的头结点开始顺序查找到其前驱结点，时间复杂度为O(n)。
此外，可采用另一种方式将其转化为后插操作来实现，设待插入结点为*s，将*s插入到*p的前面。我们仍然将*s插入到*p的后面，然后将p->data与 s->data 交换，这样做既满足逻辑关系，又能使得时间复杂度为O(1)。该方法的主要代码片段如下:
s->next=p->next; //修改指针域，不能颠倒
p->next=s;
temp=p->data; //交换数据域部分
p->data=s->data;
s->data=temp;2.3.3双链表
【双链表中插入操作的实现(2023)】
在双链表中p所指的结点之后插入结点*s，其指针的变化过程如图 2.10 所示。
插入操作的代码片段如下：
s->next=p->next; //将结点*s插入到结点*p之后
p->next->prior=s;
s->prior=p;
p->next=s;上述代码的语句顺序不是唯一的，但也不是任意的，①步必须在④步之前，否则*p的后继结点的指针就会丢掉，导致插入失败。
【循环双链表中删除操作的实现(2016)】
删除双链表中结点*p的后继结点*q，其指针的变化过程如图 2.11所示。
删除操作的代码片段如下：
删除双链表中结点*p的后继结点*q；
删除操作的代码片段如下：
p->next=q->next;
q->next->prior=p;
free(q); //释放结点空间
在建立双链表的操作中，也可采用如同单链表的头插法和尾插法，但在操作上需要注意指针的变化和单链表有所不同。
2.3.4循环链表
【循环单链表中删除首元素的操作(2021)】
循环单链表的插入、删除算法与单链表的几乎一样，所不同的是若操作是在表尾进行，则执行的操作不同，以让单链表继续保持循环的性质。当然，正是因为循环单链表是一个“环”，所以在任何位置上的插入和删除操作都是等价的，而无须判断是否是表尾。
在单链表中只能从表头结点开始往后顺序遍历整个链表，而循环单链表可以从表中的任意一个结点开始遍历整个链表。有时对循环单链表不设头指针而仅设尾指针，以使得操作效率更高其原因是，若设的是头指针，对在表尾插入元素需要O(n)的时间复杂度，而若设的是尾指针r，r->next即为头指针，对在表头或表尾插入元素都只需要 O(1)的时间复杂度。
