CSDN话题挑战赛第2期
参赛话题：学习笔记

 前言

为分清带结点与不带头结点的单链表操作，本文以图文和表格形式描述了两者之间的区别。考研中，数据结构的单链表操作是重要考点，其中，比较常考带头结点的链表操作。

所以，本文只描述了带头结点的插入、删除、查找、用前插法和后插法创建单链表等基本操作。

可结合以下链接一起学习：

【考研】数据结构考点——直接插入排序_住在阳光的心里的博客-CSDN博客

【考研】单链表相关算法（从基础到真题）_住在阳光的心里的博客-CSDN博客

一、区别

// 单链表的存储结构
typedef struct LNode{ElemType data;   //结点的数据域struct LNode *next;   //结点的指针域
}LNode, *LinkList;// LinkList 为指向结构体 LNode 的指针类型

 

 针对上图，在分清带头结点与不带头结点的单链表之前，需弄清头指针与首元结点。

（一）针对头指针

LNode * 与 LinkList ，两者本质上是等价的。

通常习惯上用 LinkList 定义单链表，强调定义的是某个单链表的头指针；用 LNode * 定义指向单链表中任意结点的指针变量。例如：

（1）若定义 LinkList L，则 L 为单链表的头指针。（简称该链表为表L）

（2）若定义 LNode *p，则 p 为指向单链表中某个结点的指针，表示该结点的地址；用 *p 表示该结点。

LinkList p 的定义形式完全等价于 LNode *p。

所以，头指针是指向链表中第一个结点的指针。

（3）若链表设有头结点，则头指针所指结点为该线性表的头结点；

（4）若链表不带头结点，则头指针所指结点为该线性表的首元结点。

（二） 针对首元结点

（1）一般，在单链表的第一个结点之前附设一个结点，称为头结点。而链表中存储第一个数据元素的结点，则称为首元结点。

（2）头结点与首元结点的关系：头结点的指针域指向首元结点。

（三） 头结点的数据域

可以不存储任何信息，也可存储与数据元素类型相同的其他附加信息，例如：当数据元素为整数型时，头结点的数据域可存放该线性表的长度。

二、链表增加头结点的作用

（一） 便于首元结点的处理

增加了头结点后，首元结点的地址保存在头结点（即其 “ 前驱 ” 结点）的指针域中，则对链表的第一个数据元素的操作与其他数据元素相同，无需进行特殊处理。

（二） 便于空表和非空表的统一处理

当链表不设头结点时，假设 L 为单链表的头指针，它应该指向首元结点，则当单链表为长度 n 为 0的空表时，L 指针为空（判定空表的条件可记为: L == NULL）。

增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。如图2.10(a) 所示的非空单链表，头指针指向头结点。若为空表，则头结点的指针域为空（判定空表的条件可记为:
L->next == NULL)，如图2.10 (b)所示。

单链表	不带头结点	带头结点
判定空表的条件	L == NULL	L->next == NULL
LinkList L;（ L 为单链表的头指针）	L指向首元结点	L指向头结点，头结点指向首元结点

三、带头结点的单链表的基本操作

（一）初始化

// （为更好理解清楚，博主会在每个操作前面放上单链表的结构定义）
// 单链表的存储结构
typedef struct LNode{ElemType data;   //结点的数据域struct LNode *next;   //结点的指针域
}LNode, *LinkList;    // LinkList 为指向结构体 LNode 的指针类型// 构造一个空的带头结点的单链表L
Status InitList(LinkList &L){L = new LNode;    //生成新结点作为头结点，用头指针L指向头结点 (C++)L->next == NULL;    //头结点的指针域置空return OK;
}// 也可以用以下方式
// 构造一个空的带头结点的单链表L
Status InitList(LinkList &L){L = (LNode *)malloc(sizeof(LNode));    //生成新结点作为头结点，用头指针L指向头结点 (C语言)L->next == NULL;    //头结点的指针域置空return OK;
}

（二）插入【设单链表表长为 n ，时间复杂度：O(n)】

 【算法步骤】
将值为 e 的新结点插入到表的第 i 个结点的位置上，即插入到结点  与  之间，具体插入过程如上图所示，图中对应的 5 个步骤说明如下。
① 查找结点  并由指针 p 指向该结点。
② 生成一个新结点 *s。
③ 将新结点 *s 的数据域置为 e。
④ 将新结点 *s 的指针域指向结点  。
⑤ 将结点 *p 的指针域指向新结点 *s。

// 单链表的存储结构
typedef struct LNode{ElemType data;   //结点的数据域struct LNode *next;   //结点的指针域
}LNode, *LinkList;    // LinkList 为指向结构体 LNode 的指针类型// 在带头结点的单链表 L 中第 i 个位置插入值为 e 的新结点
Status ListInsert (LinkList &L, int i, ElemType e)
{p = L;j = 0;while(p && (j < i - 1)){    //查找第 i-1 个结点，P指向该结点p = p->next;++j;}if(!p || j > i - 1)     // i > n+1 或者 i < 1return ERROR;s = new LNode;    //生成新结点 *ss->data = e;    //将结点 *s 的数据域置为 es->next = p->next;   //将结点 *s 的指针域指向结点aip->next = s;   //将结点 *p 的指针域指向结点 *sreturn OK;
}

（三）删除【时间复杂度：O(n)】

// 单链表的存储结构
typedef struct LNode{ElemType data;   //结点的数据域struct LNode *next;   //结点的指针域
}LNode, *LinkList;    // LinkList 为指向结构体 LNode 的指针类型//在带头结点的单链表 L 中，删除第 i 个元素
Status ListDelete(LinkList &L, int i){p = L;j = 0;while((p->next) && (j < i-1)){     //查找第 i-1 个个结点，p指向该结点p = p->next;++j;}//注意与插入操作的区别，因为合法的插入位置有 n+1 个，而合法的删除位置只有 n 个if(!(p->next) || (j > i-1))     //当 i > n 或 i < 1 时，删除位置不合理return ERROR;q = p->next;    //临时保存被删结点的地址以备释放p->next = q->next;   //改变删除结点前驱结点的指针域delete q;   //释放删除结点的空间return OK;
}

（四）查找【时间复杂度：O(n)】

注意：单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。所以在查找某个特定的结点，需要从表头开始遍历，依次查找。

// 单链表的存储结构
typedef struct LNode{ElemType data;   //结点的数据域struct LNode *next;   //结点的指针域
}LNode, *LinkList;    // LinkList 为指向结构体 LNode 的指针类型// 在带头结点的单链表 L 中查找值为 e 的元素
LNode *LocateElem(LinkList L, ElemType e){p = L->next;    //初始化，p指向首元结点while(p && p->data != e){    //顺链域向后扫描，直到 p 为空或 P 所指结点的数据域等于 ep = p->next;   //p指向下一个结点}return p;   //查找成功返回值为e的结点地址p，查找失败p为NULL
}// 在带头结点的单链表 L 中查找序号为 i 的结点
LNode *LocateElem(LinkList L, int i){int j = 1;   //计数，初始为1LNode *p = L->next;   //头结点指针赋给pif(i == 0) return L;    //若 i 等于 0，则返回头结点if(i < 1) return NULL;    //若 i 无效，则返回 NULLwhile(p && j < i){   //从第一个结点开始找，查找第 i 个结点p = p->next;j++;}return p;    //返回第 i 个结点的指针，若 i 大于表长，则返回 NULL
}

（五）前插法创建单链表【时间复杂度：O(n)】

前插法：通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。

注意：输入顺序与线性表中的逻辑顺序是相反。

例如：输入顺序：5，4，3，2，1                   线性表：1，2，3，4，5   

// 单链表的存储结构
typedef struct LNode{ElemType data;   //结点的数据域struct LNode *next;   //结点的指针域
}LNode, *LinkList;    // LinkList 为指向结构体 LNode 的指针类型//逆位序输入 n 个元素的值，用前插法创建带头结点的单链表L
void CreatList_H(LinkList &L, int n){L = new LNode;    L->next = NULL;   // 建立一个带头结点的空链表for(int i = 0; i < n; ++i){      p = new LNode;    //生成新结点 *pcin>>p->data;    //输入元素值赋给新结点 *p 的数据域//将新结点 *p 插入到头结点之后p->next = L->next;    L->next = p;}    
}

（六）后插法创建单链表【时间复杂度：O(n)】

后插法：通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样，每次申请一个新结点，读入相应的数据元素值。不同的是，为了使新结点能插入到表尾，需增加一个尾指针 r 指向链表的尾结点。 

注意：输入顺序与线性表中的逻辑顺序是相同的。

例如：输入顺序：1，2，3，4，5                      线性表：1，2，3，4，5

// 单链表的存储结构
typedef struct LNode{ElemType data;   //结点的数据域struct LNode *next;   //结点的指针域
}LNode, *LinkList;    // LinkList 为指向结构体 LNode 的指针类型//顺序输入 n 个元素的值，用后插法创建带头结点的单链表L
void CreatList_R(LinkList &L, int n){L = new LNode;L->next = NULL;    //建立一个带头结点的空链表r = L;     //尾指针 r 指向头结点for(int i = 0; i < n; ++i){p = new LNode;     //生成新结点 *p cin>>p->data;     //输入元素值赋给新结点 *p 的数据域//将新结点 *p 插入尾结点 *r 之后p->next = NULL;    r->next = p;r = p;    // r 指向新的尾结点 *p
}