单链表的基本操作
单链表的建立头插法建立单链表基本思路
代码实现
尾插法建立单链表方法原理：代码实现尾插法建立单链表最优代码如下：
单链表的插入与删除单链表的插入按位序的插入操作带头结点的按位序插入操作代码实现
不带头节点的按位序插入操作代码实现
按指定结点的插入操作在指定结点之后插入（后插）代码实现后插操作与按位序插入操作的联系
在指定结点之前插入（前插）代码实现
单链表的删除按位序的删除操作带头节点的单链表的删除操作代码实现
不带头节点的单链表的删除操作代码实现
按指定结点的删除操作代码实现
单链表的查找按位查找代码实现
代码封装按值查找
求单链表的表的长度代码实现
总结
提示，可以根据目录，可以从
单链表的插入 删除——单链表的查找——单链表的建立这样的顺序进行学习！！！
单链表的建立
单链表的建立主要包括两种建立方法：头插法与尾插法。 基本步骤如下：
初始化一个单链表每次取一个数据元素，*插入到表尾/表头 *（导致于头插法，尾插法）
头插法建立单链表
（带头结点的的单链表） 该方法从一个空表开始，生成新结点，并将读取到的数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。 本质————是对头结点的后插操作
基本思路
初始化一个单链表利用while循环{每次取一个数据元素e；调用一次后插法——InsertNextNode(L,e)}
代码实现
typedf struct LNode{ //定义单链表结构类型
ElemType data; //每个节点存放一个数据元素
struct LNode *next; //指针指向下一个节点
}LNode,*LinkList;
//函数功能——头插法建立单链表
LinkList List_HeadInsert(LinkList &L){ //逆向建立单链表
LNode *s;
int x;
L = (LinkList)malloc(sizeof(LNode)) //创建头结点
L->next=NUll; //保证头指针是不会指向脏数据的，初始化为空链表
scanf("%d",&x); //输入结点的值
while(x!=99999){//只有当输入x为99999时，循环无法进行，否则可以进行————即输入99999代表着结束
s=（LNode*)malloc(sizeof(LNode)); //申请新结点
s->data=x; //新结点的数据域被x覆盖
s-next=L->next; //将新结点链接在头指针的后继结点
L->next=s; //新结点插入表中，L为头指针
scanf("d",&x);
}
return L;
}
效果：
问题：若没有头结点，该如何理解头插法的修改？ 答：没有了头指针，每次插入新结点后，需要将其指针指向单链表指针L 提示：链表的逆置可以考虑头插法的方法！
尾插法建立单链表
（带头结点的单链表） 法一：
初始化一个单链表；利用按位序插入算法；设置变量length来记录链表长度每次都要循环，每取一个元素，按位序插入算法用一次，length++，时间复杂度为O(
n
2
n^{2}
n2）。
法二： 利用后插操作，设置一个表尾指针，每次更新，使得这个指针指向单链表的最后一个结点。
方法原理：
将新结点插入到当前链表的表尾，为此必须增加一个指针，使其始终指向当前链表的尾结点。
代码实现
typedf struct LNode{ //定义单链表结构类型
ElemType data; //每个节点存放一个数据元素
struct LNode *next; //指针指向下一个节点
}LNode,*LinkList;
//初始化一个空的单链表(带头节点）
bool Initlist(LinkList &L){
L = (LNode *)malloc(sizeof(LNode));//分配一个头节点，此头结点不存储数据。
if(L=NULL) //内存不足，分配失败
return false;
L->next = MULL; //头节点之后暂时还没有节点
return true；
}
//函数：按位序插入，在第i个位置插入元素 e
bool ListInsert(LinkList &L,int i,ElemType e){
if(i<1)
return false; //插入位置不合法
LNode *p; //指针p指向当前扫描的结点；
int j=0； //当前p指向的是第几个结点，利用j来记录；刚开始p指向单链表的头节点；
P=L; //L指向的是头节点，头节点是第0个结点(不存数据)
while(p!=NULL&&j p=p->next; j++; } if(p==NULL) //i值不合法，超出链表长度，说明第i-1个结点不存在 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 s->data=e; //在新结点中存入数据元素e s->next =p->next; //将新结点的指针域发挥与*p的指针域一样的作用：指向第i个结点； p->next=s; //将结点连接到p之后，我们假设的是第i-1个结点为*p； return ture; //插入成功！ } //函数功能:后插操作，在p结点之后插入元素e. bool InsertNextNode(LNode *p,ElemType e){ if(p==NULL) //结点p不合法 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 if(s==NULL)// 内存分配失败 。某些情况有可能分配不足，也可以不考虑这一点 return false; s->data=e; //在新结点中存入数据元素e s->next =p->next; //结点p的下一个结点由新结点s来链接； p->next=s; //将结点s链接到p之后； return ture; //插入成功！ } void test (){ LinkList L; //声明一个指向单链表的指针 //注意到此处并没有创建一个节点 //初始化一个空表 InitList(L); //....后续代码。。。。 } 思路效果： 尾插法建立单链表最优代码如下： typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能——尾插法建立单链表 LinkList List_Tailinsert(LinkList &L){//正向建立单链表 int x; //假设建立链表插入的类型ElemType为整型； L=(LinkList)malloc(sizeof(LNode)); //建立头结点 ——本质 初始化空表 LNode *s,*r=L; //设置两个指针，最开始二者都为头指针，r本质是表尾指针； scanf("%d",&x) ; //要插入结点的数据域的值 while(x!=99999){//只有当输入x为99999时，循环无法进行，否则可以进行————即输入99999代表着结束 s=（LNode*)malloc(sizeof(LNode)); //申请新结点 s->data=x; //新结点的数据域被x覆盖 r-next=s; //将新结点链接在上一个表尾结点之后————本质是尾插法，在r结点之后插入元素x； r=s; //r指向新的表尾结点————永远保证r指向最后一个结点。 scanf("d",&x); } r-next->NULL; //尾结点指针置空 return L; } //该算法的时间复杂度为O(n). 单链表的插入与删除 单链表的插入 单链表的插入分为按位序插入和按指定结点插入两大类。 按位序的插入操作 按位序插入操作也分为带头结点的单链表插入和不带头结点的单链表插入 带头结点的按位序插入操作 ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。 分析：要在第i个位置上插入指定元素，那就应该要找到第i-1个结点，并将新结点插入其后。 我们假设：i=2 主要步骤过程： 要找到第i-1个结点；(若i=2,就需要找到i=1的第一个结点)然后需要用malloc函数申请一个新的结点s;将数据元素e存入到这个结点;假设第i-1的结点为*p;新结点s的指针域指向p的后继结点；令p的指针域指向新插入结点s; (5与6的顺序不能颠倒)按位序插入成功； 进行思考:若在i=1的位置进行插入，即在头结点之后进行插入怎么办？ 答：考虑到因为是带头结点的单链表的插入，我们可以考虑把头节点看作第0个结点。 代码实现 typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能：在第i个位置插入元素e（带头结点） bool ListInsert(LinkList &L,int i,ElemType e){ if(i<1) return false; //插入位置不合法 LNode *p; //指针p指向当前扫描的结点； int j=0； //当前p指向的是第几个结点，利用j来记录；刚开始p指向单链表的头节点； P=L; //L指向的是头节点，头节点是第0个结点(不存数据) while(p!=NULL&&j p=p->next; j++; } if(p==NULL) //i值不合法，超出链表长度，说明第i-1个结点不存在 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 s->data=e; //在新结点中存入数据元素e s->next =p->next; //将新结点的指针域发挥与*p的指针域一样的作用：指向第i个结点； p->next=s; //将结点连接到p之后，我们假设的是第i-1个结点为*p； return ture; //插入成功！ } 不带头节点的按位序插入操作 ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。 分析：要在第i个位置上插入指定元素，那就应该要找到第i-1个结点，并将新结点插入其后。 基本思路：其他结点情况与带头结点的一样，区别于带头结点的单链表，不带头结点的单链表不存在第0个头结点，这就导致在第1个结点位置进行插入时，要进行特殊考虑。 代码实现 typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能：在第i个位置插入元素e（带头结点） bool ListInsert(LinkList &L,int i,ElemType e){ if(i<1) return false; //插入位置不合法 if(i==1){//在第一个结点位置进行插入的操作与其他结点操作不同 LNode *s=(LNode*)malloc(sizeof(LNode)); //申请新结点 s->data=e; //在新结点中存入数据元素e s->next =L; //将新结点的指针域指向单链表的第一个结点L L=s; //头指针指向新的结点； return ture; //插入成功！ } LNode *p; //指针p指向当前扫描的结点； int j=1； //当前p指向的是第几个结点，利用j来记录；刚开始p指向单链表的第一个结点； P=L; //L指向的是第一个结点，不是头结点，不存在头节点！ while(p!=NULL&&j p=p->next; j++; } if(p==NULL) //i值不合法，超出链表长度，说明第i-1个结点不存在 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 s->data=e; //在新结点中存入数据元素e s->next =p->next; //将新结点的指针域发挥与*p的指针 p->next=s; //将结点连接到p之后，我们假设的是第i-1个结点为*p； return ture; //插入成功！ } //函数功能：在第i个位置插入元素e（带头结点） bool ListInsert(LinkList &L,int i,ElemType e){ if(i<1) return false; //插入位置不合法 LNode *p; //指针p指向当前扫描的结点； int j=0； //当前p指向的是第几个结点，利用j来记录；刚开始p指向单链表的头节点； P=L; //L指向的是头节点，头节点是第0个结点(不存数据) while(p!=NULL&&j p=p->next; j++; } if(p==NULL) //i值不合法，超出链表长度，说明第i-1个结点不存在 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 s->data=e; //在新结点中存入数据元素e s->next =p->next; //将新结点的指针域发挥与*p的指针域一样的作用：指向第i个结点； p->next=s; //将结点连接到p之后，我们假设的是第i-1个结点为*p； return ture; //插入成功！ } 按指定结点的插入操作 对于指定结点的插入分为：在结点之后插入（后插），在结点之前插入（前插）两种方法。 在指定结点之后插入（后插） 后插操作：给定一个指定结点，在此结点之后插入一个数据元素e。 分析：由于单链表的结点结构使得单链表的链接指针只能往后寻找，所以如果给定一个指定结点p,那么p结点之后的结点都是可知的，p结点之前的结点都是未知的。 代码实现 typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能:后插操作，在p结点之后插入元素e. bool InsertNextNode(LNode *p,ElemType e){ if(p==NULL) //结点p不合法 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 if(s==NULL)// 内存分配失败 。某些情况有可能分配不足，也可以不考虑这一点 return false; s->data=e; //在新结点中存入数据元素e s->next =p->next; //结点p的下一个结点由新结点s来链接； p->next=s; //将结点s链接到p之后； return ture; //插入成功！ } 实现效果如下： 后插操作与按位序插入操作的联系 不难发现： 后插操作的代码的时间复杂度为O(1)按位序插入操作的代码的平均时间复杂度为O(n) 那是因为相比于按位序插入操作而言，后插操作省去了循环查找i-1结点的情况，一旦按位序插入操作实现目的结点的查找之后，后面的操作二者及其相似。 代码： typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能:后插操作，在p结点之后插入元素e. bool InsertNextNode(LNode *p,ElemType e){ if(p==NULL) //结点p不合法 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 if(s==NULL)// 内存分配失败 。某些情况有可能分配不足，也可以不考虑这一点 return false; s->data=e; //在新结点中存入数据元素e s->next =p->next; //结点p的下一个结点由新结点s来链接； p->next=s; //将结点s链接到p之后； return ture; //插入成功！ } //函数功能：在第i个位置插入元素e（带头结点） bool ListInsert(LinkList &L,int i,ElemType e){ if(i<1) return false; //插入位置不合法 LNode *p; //指针p指向当前扫描的结点； int j=0； //当前p指向的是第几个结点，利用j来记录；刚开始p指向单链表的头节点； P=L; //L指向的是头节点，头节点是第0个结点(不存数据) while(p!=NULL&&j p=p->next; j++; } return InsertNextNode(p,e) ; //插入成功！ } 在指定结点之前插入（前插） 前插操作：顾名思义，在指定某一结点的前面插入一个新的结点。 分析：前面学习的按位序插入操作和后插操作本质是利用单链表结点的指针域——存放指向其后继的指针做到的，由于给定结点p的前面的结点都是未知的，我们如何找到p结点的前驱结点呢？ 方法1： 传入一个头指针，利用头指针循环查找结点p；找到p的前驱结点q，再对结点q进行后插；从而完成结点q的前插操作 时间复杂度：O(n) 方法2： 倘若没有传入的头指针，我们该怎么办呢？ 我们传入头指针的目的是为了循环查找结点p的前驱结点，如果不给我们头指针，那么我们就不找结点p的前驱结点了。 我们利用后插操作，在结点p后插入一个新的结点s；进行数据交换——将p中的元素复制给s，p中的元素被覆盖为e；本质上就从开始的 → \rightarrow →p → \rightarrow →s → \rightarrow →变换成了 → \rightarrow →s → \rightarrow →p → \rightarrow →。这样既满足了逻辑关系，也比方法一的时间复杂度降低到了O(1),这个时间复杂度与后插操作相同。 实现效果： 代码实现 typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能:前插操作，在p结点之前插入元素e. bool InsertPriorNode(LNode *p,ElemType e){ if(p==NULL) //结点p不合法 return false; LNode *s=(LNode*),malloc(sizeof(LNode));//申请新结点 if(s==NULL)// 内存分配失败 。某些情况有可能分配不足，也可以不考虑这一点 return false; s->next=p->next; ; p->next=s; //将新结点连接到p之后 s->data=p->data; //将p中元素复制到s中 p->data=e; //将p中元素被覆盖为e return ture; //插入成功！ } /*倘若交换的数据不是一个简单的元素e呢*/ //我们用 temp变量来作为中间的数据桥梁 s->next=p->next; ; p->next=s; //将新结点连接到p之后 temp=p->data; //交换数据域部分 p->data=s->data; s->data=temp; 单链表的删除 单链表的删除操作与插入操作类似，也分为：按位序删除和指定结点的删除。 按位序的删除操作 ListDelete(&L,i,&e):删除操作——删除表L中的第i个位置的元素，并用e返回删除元素的值。 带头节点的单链表的删除操作 找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点 基本步骤： 检查删除位置的合法性；查找表中的第i-1个结点——被删结点的前驱结点(最浪费时间)修改指针域和返回被删数据域的元素删除成功! 最坏、最好时间复杂度：O(n) 最好时间复杂度：O(1)——不用循环查找结点，被删结点是第一个结点。 代码实现 typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能：在第i个位置插入元素e（带头结点） //头节点被看作第0个结点 bool ListDelete(LinkList &L,int i,ElemType &e){ if(i<1) return false; //插入位置不合法 LNode *p; //指针p指向当前扫描的结点； int j=0； //当前p指向的是第几个结点，利用j来记录；刚开始p指向单链表的头节点； P=L; //L指向的是头节点，头节点是第0个结点(不存数据) while(p!=NULL&&j p=p->next; j++; } if(p==NULL) //i值不合法，超出链表长度，说明第i-1个结点不存在 return false; /*比插入操作多一个判断*/ if(p->next==NULL) //说明第i-1个结点之后已无其他结点，不存在删除的必要 return false; LNode *q=p->next; //找到被删结点q e=q->data //得到被删结点q的数据域,用e返回元素的值 p->next=q->next; //将第i-1个结点指针指向第i+1个结点，*q从链中断开 free(q); //释放结点q的存储空间; return temp; //按位序删除成功！ } 不带头节点的单链表的删除操作 不带头结点的单链表的删除与带头结点的单链表的删除的区别 类似于 不带头结点的单链表的插入与带头结点的单链表的插入的区别 必须要考虑如果删除的是第一个结点会怎么处理，其他结点的情况不需要改变，而且也不会存在第0个结点这种情况。 代码实现 typedf struct LNode{ //定义单链表结构类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //函数功能：在第i个位置删除结点，并用e返回被删结点的数据 bool ListDelete(LinkList &L,int i,ElemType &e){ if(i<1) return false; //插入位置不合法 if(i==1){//在第一个结点位置进行删除的操作与其他结点操作不同 LNode *q; q=L; //单链表的指针通常指向链表的第一个结点 L=q->next; //修改指针域，把第二个结点作为修改后的第一个结点 e=q->data; //用e返回第一个结点数据域 free(q) //释放第一个结点 return ture; //删除成功！ } LNode *p; //指针p指向当前扫描的结点； int j=1； //当前p指向的是第几个结点，利用j来记录；刚开始p指向单链表的头节点； P=L; // while(p!=NULL&&j p=p->next; j++; } if(p==NULL) //i值不合法，超出链表长度，说明第i-1个结点不存在 return false; /*比插入操作多一个判断*/ if(p->next==NULL) //说明第i-1个结点之后已无其他结点，不存在删除的必要 return false; LNode *q=p->next; //找到被删结点q e=q->data //得到被删结点q的数据域,用e返回元素的值 p->next=q->next; //将第i-1个结点指针指向第i+1个结点，*q从链中断开 free(q); //释放结点q的存储空间; return temp; //按位序删除成功！ } 按指定结点的删除操作 删除指定结点*p，一般有两个方法： 方法一： 我们要删除指定结点，就行按位序删除操作一样，要先找到自己的前驱结点。 从链表的头指针开始，顺序找到被删结点*p的前驱指针；执行删除操作； 时间复杂度：O(n) 方法二： 删除结点p的操作也可用删除p的后继结操作实现 将被删结点的后继结点的数据域赋予自身；删除自己的后继结点；（让后继节点替自己死亡的过程） 时间复杂度：O(1) 由于方法二的时间复杂度低，我们一般采用方法二。 效果过程： 代码实现 //函数功能：删除指定结点p //被删结点p不是最后一个结点 bool DeleteNode(LNode *p){ if(p==NULL) return false; LNode *q=p->next;//令q指向*p的后继结点 p->data=q->data; //得到后继节点的数据域 p-next=q->next; // 将后继节点*q从链中断开 free(q); // 释放后继节点q的存储空间 return true; } 时间复杂度：O(1) 然而，如果被删结点p的后继结点为NULL（被删结点是尾结点），成为了没有替身的情况，上述代码的*q也是一个空指针！那么就不能使用方法二，只能使用方法一，从表头开始依次寻找p的前驱，时间复杂度就为O(n)。从中也能体现单链表的局限性，无法逆向检索。 单链表的查找 我们默认讨论——带头单链表的查找 单链表的查找方法有两种：按序号查找结点值(也称按位查找)，按值查找表结点（也称按值查找） 按位查找 基本思路：从单链表中的第一个结点出发，顺时针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。 平均时间复杂度：O(n) 代码实现 //函数功能：返回第i个元素（带头结点） LNode *GetElem(LinkList L,int i){ if(i<0) return NULL; //查找结点不存在 LNode *p; //指针p指向当前扫描的结点； int j=0； //当前p指向的是第几个结点，利用j来记录；刚开始p指向单链表的头节点； P=L; //L指向的是头节点，头节点是第0个结点(不存数据) while(p!=NULL&&j p=p->next; j++; } return p； } //因此只要判断函数返回值是否为NULL，就能做出查找成功的反应判断！ //结点不存在或者结点位置超出链表有效程度都会返回NULL 代码封装 当学完按位查找这个算法之后，我们发现，在前面的单链表的插入以及单链表的删除都有用到按位查找算法，但是我们当时并没有对其进行一个封装。 比如在单链表的按位插入的情况，我们可以直接通过**LNode *GetElem（L，i-1）**直接找到第i-1个结点，其他情况也是一样。对函数，对基本重复的操作进行代码封装是不错的选择。 同样之前出现的，后插算法函数直接放到插入函数的代码中，也是一种封装。 代码封装的优点：避免重复代码，简洁，容易维护 按值查找 从单链表的第一个结点开始，由前往后一次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表都没有这样的结点，则返回NULL。 //函数功能：按值查找 LNode *LocateElem(LinkList L.Elemtype e){ LNode *p=L->next;//从链表的第一个结点 while(p!MULL&&p->data!=e){ p=p->next; } return p;//找到后，返回该结点指针，否则返回NULL } 平均时间复杂度：O(n) 应该注意到，倘若数据元素e的数据类型不是简单的int，或者char类型，不能像上述代码那样进行比较。比如struct类型的数据元素，只有定义相同的结构体才能进行比较，不同定义的结构体之间比较无意义。 求单链表的表的长度 我们要知道单链表的长度是不包括头结点的！ 求表长操作就是计算单链表中数据结点（不含头结点）的个数。 基本步骤： 需要从第一个结点开始顺序依次访问表中的每个结点；为此需要设置一个计数器变量，每访问一个结点，计数器加1；知道访问到空结点为止； 算法时间复杂度O(n) 代码实现 int Length(LinkList L){ int len =0;//初始访问结点数为0 LNode *p=L; while(p->next !=NULL){ p=p->next; len++; } return len; } 总结 单链表是学习链表的基础，应该要熟练掌握。这些整理大多借鉴于数据结构严蔚敏版本以及王道考研网课的学习。 第一次发布这么多字的博客，我自己对单链表的理解和掌握也精进了许多，希望大家加油呀！ 如有错误多多指正！希望下次能有更好的博客发布！ 参考阅读
发表评论