C/C++语言实现单链表（带头结点）
生活随笔
收集整理的这篇文章主要介绍了
C/C++语言实现单链表（带头结点）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
彻底理解链表中为何使用二级指针或者一级指针的引用
数据结构之链表-链表实现及常用操作(C++篇)
C语言实现单链表，主要功能为空链表创建，链表初始化（头插法），链表元素读取，按位置插入，（有序链表）按值插入，按位置删除，按值删除，清空链表，销毁链表。
关键思路：（1）将结点创建结构体；（2）链表中添加头结点，以便统一操作；（3）使用结点一级指针和二级指针的异同点；（4）链表的最小操作单位是结点；（5）操作的起始位置是头结点还是第一个结点，及起始索引是0还是1.
#include <stdio.h>
#include <stdlib.h>
#include <time.h> //涉及到结构体自引用
typedef struct Node{
int data;
struct Node *next;
}Node; //创建空链表
//必须用二级指针，涉及到头指针的创建
int iniList(Node **List){
*List = (Node *)malloc(sizeof(Node));
if (NULL == *List){
return ;
} (*List)->next = NULL; //创建头结点
return ;
} //初始化链表(头插法)
//必须二级指针
int iniListHead(Node **List, int n){
*List = (Node *)malloc(sizeof(Node));
if (NULL == *List){
return ;
}
(*List)->next = NULL;
srand(time()); int i = ;
while (i < n){
Node *tmpNode = (Node *)malloc(sizeof(Node));
if (NULL == tmpNode){
return ;
}
tmpNode->data = rand() % + ;
tmpNode->next = (*List)->next;
(*List)->next = tmpNode; ++i;
}
return ;
} //初始化链表(尾插法)
//必须二级指针
//需要借助辅助变量pCurrent，将每次尾插的新元素当做当前元素
int iniListTail(Node **List, int n){
*List = (Node *)malloc(sizeof(Node));
if (NULL == *List){
return ;
}
(*List)->next = NULL;
srand(time()); Node *pCurrent = *List; int i = ;
while (i < n){
Node *tmpNode = (Node *)malloc(sizeof(Node));
if (NULL == tmpNode){
return ;
}
tmpNode->data = rand() % + ;
tmpNode->next = NULL;
pCurrent->next = tmpNode;
pCurrent = tmpNode; ++i;
}
return ;
} //清空链表(不删除头结点)
//一级，二级指针均可
//首先找到链表地址，然后移动至表尾
//判断条件为指针域是否为空，即到达结尾
int deleteList(Node *List){ //这种方法无法删除尾结点
//Node *p= List;
//Node *q = NULL;
//
//while (p->next){
// q = p;
// free(p);
// p = q->next;
//} Node *p = List->next;
Node *q = NULL; while (p){
q = p->next;
free(p);
p = q;
} List->next = NULL;
return ;
} //销毁链表
//必须使用二级指针，销毁头结点和头指针
//最后将链表头指针置空
int desrotyList(Node **List){ Node *p = *List;
Node *q = NULL; //如果为空链表，直接删除头结点
//如果不是空链表，从头结点开始删除
while (p){
q = p->next;
free(p);
p = q;
}
(*List) = NULL; //下面是从第一个结点开始删除
//最后释放掉头结点
//Node *p = (*List)->next;
//Node *q = NULL;
//
//while (p){
// q = p->next;
// free(p);
// p = q;
//}
//free(*List);
//(*List) = NULL; return ;
} //链表获取元素
//一级，二级指针均可
//头结点无意义，从第一个结点开始遍历，i从1开始
//每次都指向下一结点，到pos-1即可
int getList(Node *List, int pos, int *element){
Node *p = List->next; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
*element = p->data;
return ;
} //链表按位置插入
//一级，二级指针均可
//从头结点开始，有可能插入在第一个位置,遍历从1开始
int insertListPos(Node *List, int pos, int value){
Node *p = List; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
Node *tmpNode = (Node *)malloc(sizeof(Node));
tmpNode->data = value;
tmpNode->next = p->next;
p->next = tmpNode;
return ;
} //有序链表，按值插入
//一二级指针均可
int insertListValue(Node *List, int value){
Node *pCur = List->next;
Node *pPer = List;
while (pCur && pCur->data < value){
pPer = pCur;
pCur = pCur->next;
} Node *tmpNode = (Node *)malloc(sizeof(Node));
if (NULL == tmpNode){
return ;
}
tmpNode->data = value;
tmpNode->next = pPer->next;
pPer->next = tmpNode;
return ;
} //链表按位置删除
//一二级指针均可
//记得释放结点内存
//如果删除第一个结点，需要操纵头结点
int deleteListPos(Node *List, int pos){
Node *p = List; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
if (NULL == p->next)
return ; Node *tmpNode = p->next;
p->next = p->next->next; free(tmpNode);
return ;
} //链表按值删除元素
//一二级指针均可
//从第一个结点开始
int deleteListValue(Node *List, int value){
Node *pCur = List->next;
Node *pPer = List; while (pCur && pCur->data != value){
pPer = pCur;
pCur = pCur->next;
}
if (pCur == NULL){ //空链表不删除任何结点
return ;
}
else{
pPer->next = pCur->next;
free(pCur);
}
return ;
} int main(){ Node *testList = NULL;
iniList(&testList);
//iniListHead(&testList, 3);
//iniListTail(&testList, 3); insertListPos(testList, , );
insertListPos(testList, , );
insertListPos(testList, , );
insertListPos(testList, , );
//insertListPos(testList, 1, 1);
insertListValue(testList, ); //deleteListPos(testList, 1);
//deleteListValue(testList, 4); //deleteList(testList); //printf("%d\n", testList);
//desrotyList(&testList);
//printf("%d\n", testList); Node * tmpNode = testList->next;
while (tmpNode){
printf("%d\n", tmpNode->data);
tmpNode = tmpNode->next;
} printf("----------------------\n"); int a = ;
getList(testList, , &a);
printf("%d\n", a); system("pause"); return ;
}
C语言完整代码
通过C++实现C语言的链表，主要区别：（1）struct可以不通过typedef，直接使用Node；（2）将malloc和free更换为new和delete
#include<iostream>
#include<ctime> using namespace std; struct Node{
int data;
Node *next;
}; //创建空链表
//必须用二级指针，涉及到头指针的创建
int iniList(Node **List){
*List = new Node; (*List)->next = NULL; //创建头结点
return ;
} //初始化链表(头插法)
//必须二级指针
int iniListHead(Node **List, int n){
*List = new Node; (*List)->next = NULL;
srand(time()); int i = ;
while (i < n){
Node *tmpNode = new Node; tmpNode->data = rand() % + ;
tmpNode->next = (*List)->next;
(*List)->next = tmpNode; ++i;
}
return ;
} //初始化链表(尾插法)
//必须二级指针
//需要借助辅助变量pCurrent，将每次尾插的新元素当做当前元素
int iniListTail(Node **List, int n){
*List = new Node; (*List)->next = NULL;
srand(time()); Node *pCurrent = *List; int i = ;
while (i < n){
Node *tmpNode = new Node; tmpNode->data = rand() % + ;
tmpNode->next = NULL;
pCurrent->next = tmpNode;
pCurrent = tmpNode; ++i;
}
return ;
} //清空链表(不删除头结点)
//一级，二级指针均可
//首先找到链表地址，然后移动至表尾
//判断条件为指针域是否为空，即到达结尾
int deleteList(Node *List){ //这种方法无法删除尾结点
//Node *p= List;
//Node *q = NULL;
//
//while (p->next){
// q = p;
// free(p);
// p = q->next;
//} Node *p = List->next;
Node *q = NULL; while (p){
q = p->next;
delete p;
p = q;
} List->next = NULL;
return ;
} //销毁链表
//必须使用二级指针，销毁头结点和头指针
//最后将链表头指针置空
int desrotyList(Node **List){ Node *p = *List;
Node *q = NULL; //如果为空链表，直接删除头结点
//如果不是空链表，从头结点开始删除
while (p){
q = p->next;
delete p;
p = q;
}
(*List) = NULL; //下面是从第一个结点开始删除
//最后释放掉头结点
//Node *p = (*List)->next;
//Node *q = NULL;
//
//while (p){
// q = p->next;
// free(p);
// p = q;
//}
//free(*List);
//(*List) = NULL; return ;
} //链表获取元素
//一级，二级指针均可
//头结点无意义，从第一个结点开始遍历，i从1开始
//每次都指向下一结点，到pos-1即可
int getList(Node *List, int pos, int *element){
Node *p = List->next; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
*element = p->data;
return ;
} //链表按位置插入
//一级，二级指针均可
//从头结点开始，有可能插入在第一个位置,遍历从1开始
int insertListPos(Node *List, int pos, int value){
Node *p = List; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
Node *tmpNode = new Node;
tmpNode->data = value;
tmpNode->next = p->next;
p->next = tmpNode;
return ;
} //有序链表，按值插入
//一二级指针均可
int insertListValue(Node *List, int value){
Node *pCur = List->next;
Node *pPer = NULL;
while (pCur && pCur->data < value){
pPer = pCur;
pCur = pCur->next;
} Node *tmpNode = new Node;
if (NULL == tmpNode){
return ;
}
tmpNode->data = value;
tmpNode->next = pPer->next;
pPer->next = tmpNode;
return ;
} //链表按位置删除
//一二级指针均可
//记得释放结点内存
//如果删除第一个结点，需要操纵头结点
int deleteListPos(Node *List, int pos){
Node *p = List; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
Node *tmpNode = p->next;
p->next = p->next->next; delete tmpNode;
return ;
} //链表按值删除元素
//一二级指针均可
//从第一个结点开始
int deleteListValue(Node *List, int value){
Node *pCur = List->next;
Node *pPer = List; while (pCur && pCur->data != value){
pPer = pCur;
pCur = pCur->next;
}
if (pCur == NULL){
return ;
}
else{
pPer->next = pCur->next;
delete pCur;
}
return ;
}
C++完整代码
结点结构体
将结点创建为结构体，其中包含数据域和指针域成员，指针域涉及结构体自引用。指针域成员之所以为结点类指针，一是为了编译时能明确结构体大小，二是为了指向下一个结点，因此初始化时不用开辟内存，只需要赋值为NULL即可。当然了，开辟内存也是可以的，这样在删除结点，及清空链表时需要记得将其释放，多此一举，不提倡。
//涉及到结构体自引用
typedef struct Node{
int data;
struct Node *next;
}Node;
空链表创建（二级指针）
空链表创建时，建议创建头结点。在插入和删除第一个位置的元素时，需要用结点的二级指针移动头指针，但普通结点的插入和删除并不需要移动头指针。为了便于操作的统一（指插入和删除操作），这里先创建头结点。
另外，在创建空链表时，需要传入二级指针，主要是为了操作头指针，只要涉及操作头指针的都需要使用二级指针。
//创建空链表
//必须用二级指针，涉及到头指针的创建
int iniList(Node **List){
*List = (Node *)malloc(sizeof(Node));
if (NULL == *List){
return ;
} (*List)->next = NULL; //创建头结点，将其指针域置空
return ;
}
链表初始化（二级指针）
链表初始化，即是创建空链表，并对链表中的n个元素进行赋值。一般来说，有头插法、尾插法两种，头插法是在头结点后插入，尾插法是在链表尾插入。
头插法
头插法一般思路：（1）创建带头结点的空链表；（2）创建新结点，对新结点赋值；（3）新结点指向头结点的下一个结点，头结点指向新结点。
//初始化链表(头插法)
//必须二级指针
int iniListHead(Node **List, int n){
*List = (Node *)malloc(sizeof(Node));
if (NULL == *List){
return ;
}
(*List)->next = NULL;
srand(time()); int i = ;
while (i < n){
Node *tmpNode = (Node *)malloc(sizeof(Node));
if (NULL == tmpNode){
return ;
}
tmpNode->data = rand() % + ;
tmpNode->next = (*List)->next;
(*List)->next = tmpNode; ++i;
}
return ;
}
尾插法
尾插法一般思路：（1）创建带头结点的空链表；（2）创建新结点，对新结点数据域赋值，指针域置空；（3）建立临时变量指向头结点，头结点指向新结点；（4）将临时变量往后移动，指向新结点。
//初始化链表(尾插法)
//必须二级指针
//需要借助辅助变量pCurrent，将每次尾插的新元素当做当前元素
int iniListTail(Node **List, int n){
*List = (Node *)malloc(sizeof(Node));
if (NULL == *List){
return ;
}
(*List)->next = NULL;
srand(time()); Node *pCurrent = *List; int i = ;
while (i < n){
Node *tmpNode = (Node *)malloc(sizeof(Node));
if (NULL == tmpNode){
return ;
}
tmpNode->data = rand() % + ;
tmpNode->next = NULL;
pCurrent->next = tmpNode;
pCurrent = tmpNode; ++i;
}
return ;
}
链表元素读取（一、二级指针）
链表元素读取，需要涉及到索引位置。我们知道头结点的数据域没有意义，因此起始位置从第一个结点开始，遍历值从1开始，到pos-1为止，此时p指向pos结点。
//链表获取元素
//一级，二级指针均可
//头结点无意义，从第一个结点开始遍历，i从1开始
//每次都指向下一结点，到pos-1即可
int getList(Node *List, int pos, int *element){
Node *p = List->next; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
*element = p->data;
return ;
}
按位置插入（一、二级指针）
插入时，需要考虑任意位置，由于头结点的设立，我们不需要单独考虑第一个位置的结点插入。
一般思路：（1）起始位置从头结点开始，遍历值从1开始，到pos-1为止，此时指向pos-1结点；（2）创建新结点，给新结点数据域赋值；（3）新结点指向pos位置的下一结点，pos位置指向新结点。
//链表按位置插入
//一级，二级指针均可
//从头结点开始，有可能插入在第一个位置,遍历从1开始
int insertListPos(Node *List, int pos, int value){
Node *p = List; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
Node *tmpNode = (Node *)malloc(sizeof(Node));
tmpNode->data = value;
tmpNode->next = p->next;
p->next = tmpNode;
return ;
}
有序链表按值插入（一、二级指针）
有序链表中涉及到按值插入，按值删除时，需要建立两个临时变量，不同于按位置插入，我们可以在pos前一个停止遍历，按值插入，我们需要遍历找到插入位置，操作插入位置的前一个结点。
一般思路：（1）从第一个结点开始遍历；（2）创建per变量标记当前结点的前一结点；（3）创建新结点，操作per结点；（4）常规插入操作。
//有序链表，按值插入
//一二级指针均可
int insertListValue(Node *List, int value){
Node *pCur = List->next;
Node *pPer = NULL;
while (pCur && pCur->data < value){
pPer = pCur;
pCur = pCur->next;
} Node *tmpNode = (Node *)malloc(sizeof(Node));
if (NULL == tmpNode){
return ;
}
tmpNode->data = value;
tmpNode->next = pPer->next;
pPer->next = tmpNode;
return ;
}
按位置删除（一、二级指针）
删除时，由于头结点的设立，因此不需要特殊考虑第一个位置的操作和头指针的移动。需要设置临时变量是释放p->next后，后面还会使用p->next的结点，这样会造成访问出错。
一般思路：（1）起始位置从头结点开始，遍历从1开始，到pos-1为止，此时指向pos-1结点；（2）创建临时变量，指向pos结点；（3）将pos-1结点指向pos的下一结点，释放掉pos结点。
//链表按位置删除
//一二级指针均可
//记得释放结点内存
//如果删除第一个结点，需要操纵头结点
int deleteListPos(Node *List, int pos){
Node *p = List; int i = ;
while (p && i < pos){
p = p->next;
++i;
}
Node *tmpNode = p->next;
p->next = p->next->next; free(tmpNode);
return ;
}
按值删除（一、二级指针）
按值删除与按值插入一样，需要两个临时变量。
一般思路：（1）起始位置从第一个结点开始，（2）设立per结点指针保存当前结点的上一结点；（3）常规删除操作。
//链表按值删除元素
//一二级指针均可
//从第一个结点开始
int deleteListValue(Node *List, int value){
Node *pCur = List->next;
Node *pPer = List; while (pCur && pCur->data != value){
pPer = pCur;
pCur = pCur->next;
}
if (pCur == NULL){ //空链表不删除任何结点
return ;
}
else{
pPer->next = pCur->next;
free(pCur);
}
return ;
}
清空链表（一、二级指针）
清空链表，只是将链表中的结点删除，并释放掉结点空间，保留头结点，并将头结点的指针域置空。
一般思路：（1）起始位置从第一个结点开始；（2）设置临时变量q指向当前结点p的下一结点，释放掉当前结点p，将临时变量q赋给p；（3）最后将头结点的指针置空。
//清空链表(不删除头结点)
//一级，二级指针均可
//首先找到链表地址，然后移动至表尾
//判断条件为指针域是否为空，即到达结尾
int deleteList(Node *List){ //这种方法无法删除尾结点，当p->next是尾结点上一节点时，走一遍程序
//Node *p= List;
//Node *q = NULL;
//
//while (p->next){
// q = p;
// free(p);
// p = q->next;
//} Node *p = List->next;
Node *q = NULL; while (p){
q = p->next;
free(p);
p = q;
} List->next = NULL;
return ;
}
销毁链表（二级指针）
销毁链表，是在清空链表的基础上，删除头结点，将头指针置空，涉及到头指针的操作，需要二级指针。
思路一：（1）与清空链表操作相同，从第一个结点开始删除；（2）最后释放掉头结点，将头指针置空
思路二：（1）起始位置从头结点开始删除；（2）将头指针置空
//销毁链表
//必须使用二级指针，销毁头结点和头指针
//最后将链表头指针置空
int desrotyList(Node **List){ Node *p = *List;
Node *q = NULL; //如果为空链表，直接删除头结点
//如果不是空链表，从头结点开始删除
while (p){
q = p->next;
free(p);
p = q;
}
(*List) = NULL; //下面是从第一个结点开始删除
//最后释放掉头结点
//Node *p = (*List)->next;
//Node *q = NULL;
//
//while (p){
// q = p->next;
// free(p);
// p = q;
//}
//free(*List);
//(*List) = NULL; return ;
}
二级指针和一级指针插入解析
-------------------------------------------------------------------------------------------------------------
如果上面的资料对你有启发，麻烦点个推荐，让更多人的人看到哦。
关注公众号【两猿社】，懂点互联网，懂点IC的程序猿，带你丰富项目经验哦。
总结
以上是生活随笔为你收集整理的C/C++语言实现单链表（带头结点）的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 闺蜜结婚送一只泰迪熊可以嘛，两只不好拿，
- 下一篇： C++模板学习：函数模板、结构体模板、类