• 【数据结构与算法】链表

    🔥一个人走得远了，就会忘记自己为了什么而出发，希望你可以不忘初心，不要随波逐流，一直走下去🎶
    🦋 欢迎关注🖱点赞👍收藏🌟留言🐾
    🦄 本文由 程序喵正在路上 原创，CSDN首发！
    💖 系列专栏：数据结构与算法
    🌠 首发时间：2022年9月1日
    ✅ 如果觉得博主的文章还不错的话，希望小伙伴们三连支持一下哦

    阅读指南

    链表简介

    数组和链表是所有数据结构的基础，链表是很重要的两种线性结构之一

    链表可以分为单链表、双链表、循环单链表、循环双链表四种，每一种又可以分为有头和无头两种

    单链表就是相邻两个节点之间只有一个指针连接，而有头单链表就是第一个节点（也就是头节点）不存储数据，后面才存储数据的链表，无头单链表就是头节点存储有数据

    在这里插入图片描述

    请注意：实际运用中，有头链表是不用的

    在这里插入图片描述

    至于循环单链表和循环双链表，区别就在于循环链表的尾节点会指向第一个节点

    无头单链表准备工作

    创建一个后缀为 .c 的文件，你可能为问为什么要写成 C语言 的？

    如果我们是写成 C++ 的话，那风格就完全不一样了，我们得把这个链表写成一个类

    我们一般将链表的节点分为两部分：数据域和指针域，前者用来存储数据，后者用来存储指针

    其实，指针域也不一定要存储指针，我们用数组下标也是可以的，这同样是一个链表，是为什么呢？

    首先，你要明白，指针是指向一块内存段的变量，那么只要能指向一个内存段的，就可以称为指针，它不需要一定是一个指针变量

    #include 

//链表节点类型
struct Node{
	int				data;
	struct Node*	pNext;
};

//链表类型
struct List{
	struct Node*	pRoot;
};

//初始化链表
void initList(struct List* list);

//创建链表节点并返回
struct Node* createNode(int newData);

int main(){
	 //创建一个链表，两种方法
	struct List list;

	struct Node* pHead = NULL;
	

	while (1);
	return 0;
}

//初始化链表
void initList(struct List* list){
	list->pRoot = NULL;	
}

//创建链表节点并返回
struct Node* createNode(int newData){
	//开内存
	struct Node* pNew = (struct Node*)malloc(sizeof(struct Node));
	//判断内存是否申请成功
	if (NULL == pNew) {	//防御性编程
		printf("申请内存失败");
		return NULL;
	}
	//数据赋值
	pNew->data = newData;
	pNew->pNext = NULL;
	//返回
	return pNew;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    无头单链表尾插法实现一

    给链表添加节点有三种方式：头插法、尾插法、中间插法，我们先来实现尾插法

    尾插法实现一的思路为：

    1. 判断链表是否为空
    2. 创建新节点
    3. 找到原链表的尾节点
    4. 原尾节点的 pNext 指向新节点
    #include 

#define IS_LIST 1


//链表节点类型
struct Node{
	int				data;
	struct Node*	pNext;
};

#if IS_LIST
//链表类型
struct List{
	struct Node*	pRoot;
};
#endif

#if IS_LIST
//初始化链表
void initList(struct List* list);
#endif

//创建链表节点并返回
struct Node* createNode(int newData);

#if IS_LIST
//增，尾插法	push_back   两种方法
void appendNode(struct List* pList, int appendNodeData);
#else
void appendNode(struct Node* pHead, int appendNodeData);
#endif



//主函数
int main(){
#if IS_LIST
	 //创建一个链表
	struct List list;
	initList(&list);
	//测试尾插法
	for (int i = 0; i < 10; i++){
		appendNode(&list, i);
	}
#else
	struct Node* pHead = NULL;
	//测试第一个尾插法
	for (int i = 0; i < 10; i++){
		appendNode(pHead, i);
	}
#endif

	
	while (1);
	return 0;
}

#if IS_LIST
//初始化链表
void initList(struct List* list){
	list->pRoot = NULL;	
}
#endif

//创建链表节点并返回
struct Node* createNode(int newData){
	//开内存
	struct Node* pNew = (struct Node*)malloc(sizeof(struct Node));
	//判断内存是否申请成功
	if (NULL == pNew) {	//防御性编程
		printf("申请内存失败");
		return NULL;
	}
	//数据赋值
	pNew->data = newData;
	pNew->pNext = NULL;
	//返回
	return pNew;
}

#if IS_LIST
//增，尾插法
void appendNode(struct List* pList, int appendNodeData){
	//如果链表为空
	if (NULL == pList) return;		//防呆

	//1、创建新节点
	struct Node* pNew = createNode(appendNodeData);
	if (NULL == pNew) return;		//防呆

	if (pList->pRoot){	//如果链表不为空
		//2、找到尾节点
		struct Node* pTemp = pList->pRoot;
		while (pTemp->pNext != NULL){
			pTemp = pTemp->pNext; 
		}
		//3、pNext指向新节点
		pTemp->pNext = pNew;
	}
	else {
		//2、pList的成员指向新节点
		pList->pRoot = pNew;
	}
}
#else
void appendNode(struct Node* pHead, int appendNodeData){

}
#endif

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110

    在主函数的 for 循环这里打个断点，然后运行程序，再将 list 拖到监视窗口中：

    在这里插入图片描述

    按 F10 运行几次，发现没有问题：

    在这里插入图片描述

    无头单链表尾插法实现二

    尾插法实现二的思路差不多：

    1. 注意函数参数要传地址进去，不能传值，比如原来的 void appendNode(struct Node* head, int appendNodeData); 其实是单向值传递
    2. 判断链表是否为空
    3. 创建新节点
    4. 找到尾节点
    5. 原尾节点的 pNext 指向新节点
    #include 

#define IS_LIST 0


//链表节点类型
struct Node{
	int				data;
	struct Node*	pNext;
};

#if IS_LIST
//链表类型
struct List{
	struct Node*	pRoot;
};
#endif

#if IS_LIST
//初始化链表
void initList(struct List* list);
#endif

//创建链表节点并返回
struct Node* createNode(int newData);

#if IS_LIST
//增，尾插法	push_back   两种方法
void appendNode(struct List* pList, int appendNodeData);
#else
void appendNode(struct Node** head, int appendNodeData);
#endif



//主函数
int main(){
#if IS_LIST
	 //创建一个链表
	struct List list;
	initList(&list);
	//测试第一个尾插法
	for (int i = 0; i < 10; i++){
		appendNode(&list, i);
	}
#else
	struct Node* pHead = NULL;
	//测试第二个尾插法
	for (int i = 0; i < 10; i++){
		appendNode(&pHead, i);
	}
#endif

	
	while (1);
	return 0;
}

#if IS_LIST
//初始化链表
void initList(struct List* list){
	list->pRoot = NULL;	
}
#endif

//创建链表节点并返回
struct Node* createNode(int newData){
	//开内存
	struct Node* pNew = (struct Node*)malloc(sizeof(struct Node));
	//判断内存是否申请成功
	if (NULL == pNew) {	//防御性编程
		printf("申请内存失败");
		return NULL;
	}
	//数据赋值
	pNew->data = newData;
	pNew->pNext = NULL;
	//返回
	return pNew;
}

#if IS_LIST
//增，尾插法
void appendNode(struct List* pList, int appendNodeData){
	//如果链表为空
	if (NULL == pList) return;		//防呆

	//1、创建新节点
	struct Node* pNew = createNode(appendNodeData);
	if (NULL == pNew) return;		//防呆

	if (pList->pRoot){	//如果链表不为空
		//2、找到尾节点
		struct Node* pTemp = pList->pRoot;
		while (pTemp->pNext != NULL){
			pTemp = pTemp->pNext; 
		}
		//3、pNext指向新节点
		pTemp->pNext = pNew;
	}
	else {
		//2、pList的成员指向新节点
		pList->pRoot = pNew;
	}
}
#else
void appendNode(struct Node** head, int appendNodeData){
	//1、创建新节点
	struct Node* pNew = createNode(appendNodeData);
	if (NULL == pNew) return;		//防呆

	if (*head){	//如果链表不为空
		//2、找到尾节点
		struct Node* pTemp = *head;
		while (pTemp->pNext != NULL){
			pTemp = pTemp->pNext;
		}
		//3、pNext指向新节点
		pTemp->pNext = pNew;
	}
	else {
		//2、pList的成员指向新节点
		*head = pNew;
	}
}
#endif

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126

    在主函数的 for 循环这里打个断点，然后运行程序，再将 pHead 拖到监视窗口中：

    在这里插入图片描述

    按 F10 运行几次，发现没有问题：

    在这里插入图片描述

    遍历

    借鉴尾插法中的思路，很简单就可以写出遍历的函数

    //遍历声明
#if IS_LIST
void travel(struct List* pList);
#else
void travel(struct Node* head);
#endif

int main(){
#if IS_LIST
	struct List list;
	initList(&list);
	for (int i = 0; i < 10; i++){
		appendNode(&list, i);
		travel(&list);
	}
#else
	struct Node* pHead = NULL;
	for (int i = 0; i < 10; i++){
		appendNode(&pHead, i);
		travel(pHead);
	}

#endif

	while (1);
	return 0;
}

//遍历实现
#if IS_LIST
void travel(struct List* pList){
	struct Node* pTemp = pList->pRoot;
	printf("list:");
	while (pTemp){
		printf("%d ", pTemp->data);
		pTemp = pTemp->pNext;
	}
	printf("\n");
}
#else
void travel(struct Node* head){
	struct Node* pTemp = head;
	printf("list:");
	while (pTemp){
		printf("%d ", pTemp->data);
		pTemp = pTemp->pNext;
	}
	printf("\n");
}
#endif

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    测试结果如下：

    在这里插入图片描述

    无头单链表头插法

    头插法的思路很简单：

    1. 创建新节点 pNew
    2. 新节点的 pNext 指向链表的头节点
    3. 头节点被 pNew 赋值
    //头插法  push_front
#if IS_LIST
void addNode(struct List* pList, int addNodeData);
#else
void addNode(struct Node** head, int addNodeData);
#endif

int main(){
#if IS_LIST
	struct List list;
	initList(&list);
	for (int i = 0; i < 10; i++){
		addNode(&list, i);
		travel(&list);
	}
#else
	struct Node* pHead = NULL;
	for (int i = 0; i < 10; i++){
		addNode(&pHead, i);
		travel(pHead);
	}

#endif

	while (1);
	return 0;
}

//头插法  push_front
#if IS_LIST
void addNode(struct List* pList, int addNodeData){
	if(NULL == pList) return;  //防呆
	//1、创建新节点
	struct Node* pNew = createNode(addNodeData);
	if (NULL == pNew) return;  //防呆
	//2、新节点的pNext指向链表的头节点
	pNew->pNext = pList->pRoot;
	//3、头节点被pNew赋值
	pList->pRoot = pNew;
}
#else
void addNode(struct Node** head, int addNodeData){
	if (NULL == head) return;//防呆
	//1 创建新节点
	struct Node* pNew = createNode(addNodeData);
	//2 新节点的pNext指向head指向的节点
	pNew->pNext = *head;
	//3 *head 被pNew赋值
	*head = pNew;
}
#endif

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    测试结果如下，将 IS_LIST 的值改为 0 后，另一种方法同样测试成功：

    在这里插入图片描述

    无头单链表中间插入

    在这里插入图片描述

    //中间插入 insert，新节点插入到pos（下标）位置的后面
#if IS_LIST
void insertNode(struct List* pList, int pos, int insertNodeData);
#else
void insertNode(struct Node** head, int pos, int insertNodeData);
#endif

//从head链表中找到pos节点并返回，找不到返回NULL
struct Node* findPos(struct Node* head, int pos);


int main(){
#if IS_LIST
	struct List list;
	initList(&list);
	for (int i = 0; i < 10; i++){
		addNode(&list, i);
		travel(&list);
	}

	insertNode(&list, 2, 666);
	travel(&list);
	insertNode(&list, 0, 999);
	travel(&list);
	insertNode(&list, 22, 5678);
	travel(&list);
#else
	struct Node* pHead = NULL;
	for (int i = 0; i < 10; i++){
		addNode(&pHead, i);
		travel(pHead);
	}

	insertNode(&pHead, 2, 666);
	travel(pHead);
	insertNode(&pHead, 0, 999);
	travel(pHead);
	insertNode(&pHead, 22, 5678);
	travel(pHead);

#endif

	while (1);
	return 0;
}

//从head链表中找到pos节点并返回，找不到返回NULL
struct Node* findPos(struct Node* head, int pos){
	if (NULL == head) return;
	struct Node* pTemp = head;
	for (int i = 0; i < pos; i++){
		if (NULL == pTemp) return NULL;
		pTemp = pTemp->pNext;
	}
	return pTemp;
}

//中间插入 insert，新节点插入到pos（下标）位置的后面
#if IS_LIST
void insertNode(struct List* pList, int pos, int insertNodeData){
	if (NULL == pList) return;
	if (NULL == pList->pRoot || 0 == pos) {
		addNode(pList, insertNodeData);
		return;
	}

	struct Node* pPrev = findPos(pList->pRoot , pos - 1);	//找到
	if (NULL == pPrev) return;
	//创建新节点
	struct Node* pNew = createNode(insertNodeData);
	//新节点的pNext指针指向pPrev的pNext
	pNew->pNext = pPrev->pNext;
	//pPrev的pNext指向新节点
	pPrev->pNext = pNew;
}
#else
void insertNode(struct Node** head, int pos, int insertNodeData){
	if (NULL == head) return;
	if (NULL == *head || 0 == pos) {
		addNode(head, insertNodeData);
		return;
	}

	struct Node* pPrev = findPos(*head, pos - 1);	//找到
	if (NULL == pPrev) return;
	//创建新节点
	struct Node* pNew = createNode(insertNodeData);
	//新节点的pNext指针指向pPrev的pNext
	pNew->pNext = pPrev->pNext;
	//pPrev的pNext指向新节点
	pPrev->pNext = pNew;
}
#endif

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93

    测试结果如下：

    在这里插入图片描述

    无头单链表删除

    删除的思路为：

    1. 临时保存要删除的节点，方便后面删除，不保存的话后面无法删除会造成内存泄漏
    2. 目标节点的前一个节点的 pNext 要指向目标节点的后一个节点
    3. 释放目标节点
    //删除链表中第pos个节点
void deleteNodePos(struct Node** head, int pos);

//删除链表中第一个节点
void deleteHead(struct Node** head);


int main(){
#if IS_LIST
	struct List list;
	initList(&list);
	for (int i = 0; i < 10; i++){
		addNode(&list, i);
		travel(&list);
	}

	insertNode(&list, 2, 666);
	travel(&list);
	insertNode(&list, 0, 999);
	travel(&list);
	insertNode(&list, 22, 5678);
	travel(&list);
#else
	struct Node* pHead = NULL;
	for (int i = 0; i < 10; i++){
		addNode(&pHead, i);
		travel(pHead);
	}

	insertNode(&pHead, 2, 666);
	travel(pHead);
	insertNode(&pHead, 0, 999);
	travel(pHead);
	insertNode(&pHead, 22, 5678);
	travel(pHead);

	deleteNodePos(&pHead, 0);
	travel(pHead);
	deleteNodePos(&pHead, 10);
	travel(pHead);

#endif

	while (1);
	return 0;
}

//删除链表中第一个节点
void deleteHead(struct Node** head){
	if (NULL == head) return;
	//临时存储要删的节点
	struct Node* pDel = *head;
	//*head的下一个是要成为新的头节点的
	*head = (*head)->pNext;
	//释放内存
	free(pDel); 
}

//删除链表中第pos个节点
void deleteNodePos(struct Node** head, int pos){
	if (NULL == head || pos < 0) return;
	if (0 == pos){
		deleteHead(head);
		return;
	}
	//临时存储pos节点地址
	struct Node* pDel = findPos(*head, pos);
	if (NULL == pDel) return;

	//找到pos-1节点
	struct Node* pDelPrev = findPos(*head, pos - 1);
	if (NULL == pDelPrev) return;

	//pos-1节点的next指针指向pos的下一个节点
	pDelPrev->pNext = pDel->pNext;

	//释放pos节点内存
	free(pDel);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79

    删除链表中第 pos 个节点测试成功：

    在这里插入图片描述

    无头单链表模板类

    接下来我们用 C++ 的风格将上面的功能实现一遍

    新建一个项目，创建一个 MyList.h 的文件，在其中实现所有的功能：

    #pragma once 
#include 
using namespace std;

template <class T>
class MyList{
	struct Node{
		T		data;
		Node*	pNext;
		Node(){
			this->data = NULL;
			pNext = NULL;
		}
		Node(const T& data){
			this->data = data;
			pNext = NULL;
		}
	};

	Node* pHead;
public:
	MyList(){
		pHead = NULL;
	}

	//尾插法
	void appendNode(const T& data);
	//头插法
	void addNode(const T& data);
	//中间插入
	void insertNode(int pos, int insertNodeData);
	//遍历
	void travel();
	//删除链表中第pos个节点
	void deleteNodePos(int pos);
	//删除链表中第一个节点
	void deleteHead();
private:
	//找某一个节点
	Node* _findPos(int pos);
};

//找某一个节点
template <class T> //返回泛型类型要加typename
typename MyList<T>::Node* MyList<T>::_findPos(int pos){
	Node* pTemp = pHead;
	for (int i = 0; i < pos; i++){
		if (NULL == pos) return NULL;
		pTemp = pTemp->pNext;
	}
	return pTemp;
}

//尾插法
template <class T>
void MyList<T>::appendNode(const T& data){
	//1、创建新节点
	Node* pNew = new Node(data);
	//2、找到尾节点
	Node* pTemp = pHead;
	if (pTemp){
		while (pTemp->pNext){
			pTemp = pTemp->pNext;
		}
		//3、新节点插入到尾节点之后
		pTemp->pNext = pNew;
	}
	else{
		pHead = pNew;
	}
}

//头插法
template <class T>
void MyList<T>::addNode(const T& data){
	//1、创建新节点
	Node* pNew = new Node(data);
	if (NULL == pNew) return;
	//2、新节点的next指针指向原来头节点
	pNew->pNext = pHead;
	//3、新节点成为头节点
	pHead = pNew;
}

//中间插入,新节点插入到pos（下标）位置的后面
template <class T>
void MyList<T>::insertNode(int pos, int insertNodeData){
	if (pos < 0) return;
	if (NULL == pHead || 0 == pos){
		addNode(insertNodeData);
		return;
	}
	//找到pos节点
	Node* pPrev = _findPos(pos);
	//新建节点
	Node* pNew = new Node(insertNodeData);
	//新节点成为pos节点后面的节点
	pNew->pNext = pPrev->pNext;
	pPrev->pNext = pNew;
}

//遍历
template <class T>
void MyList<T>::travel(){
	Node* pTemp = pHead;
	cout << "list:";
	while (pTemp){
		cout << pTemp->data << " ";
		pTemp = pTemp->pNext;
	}
	cout << endl;
}

//删除链表中第pos个节点
template <class T>
void MyList<T>::deleteNodePos(int pos){
	if (NULL == pHead || pos < 0) return;
	if (0 == pos){
		deleteHead();
		return;
	}

	Node* pDelPrev = _findPos(pos - 1);
	if (NULL == pDelPrev) return;

	Node* pDel = _findPos(pos); 
	if (NULL == pDel) return;

	pDelPrev->pNext = pDel->pNext;	//断开
	delete pDel;
}

//删除链表中第一个节点
template <class T>
void MyList<T>::deleteHead(){
	if (NULL == pHead) return;
	Node* pDel = pHead;
	pHead = pDel->pNext;
	delete pDel; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140

    新建一个 main.cpp 的测试文件：

    #include "MyList.h"

int main(){
	MyList<int> l;

	for (int i = 0; i < 10; i++){
		l.addNode(i);
		l.travel();
	}

	cout << "插入666到第6个后面后：" << endl;
	l.insertNode(5, 666);	//插入666到第6个后面
	l.travel();

	cout << "删除第一个后：" << endl;
	l.deleteHead();		//删第一个
	l.travel();

	cout << "删除下标为5的节点后：" << endl;
	l.deleteNodePos(5);
	l.travel();

	while (1);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    测试成功：

    在这里插入图片描述

    循环双链表

    在这里插入图片描述
    新建一个项目，创建一个 list.h 的文件，这里只实现了尾插法和遍历的功能，你可以自己尝试写一下其他功能

    #pragma once 
#include 
using namespace std;

template <class T>
class MyList{
	struct Node{
		T		data;
		//两个指针
		Node*	pNext; //指向下一个节点
		Node*	pPrev; //指向前一个节点
		Node(){
			this->data = NULL;
			pNext = pPrev = NULL;
		}
		Node(const T& data){
			this->data = data;
			pNext = pPrev = NULL;
		}
	};

	Node* pHead;
	Node* pTail;
public:
	MyList(){
		pHead = pTail = NULL;
	}

	//尾插法
	void appendNode(const T& data);
	//头插法
	void addNode(const T& data);
	//中间插入
	void insertNode(int pos, int insertNodeData);
	//遍历
	void travel();
	//删除链表中第pos个节点
	void deleteNodePos(int pos);
	//删除链表中第一个节点
	void deleteHead();
private:
	//找某一个节点
	Node* _findPos(int pos);
};

//找某一个节点
template <class T> //返回泛型类型要加typename
typename MyList<T>::Node* MyList<T>::_findPos(int pos){
	Node* pTemp = pHead;
	for (int i = 0; i < pos; i++){
		if (NULL == pos) return NULL;
		pTemp = pTemp->pNext;
	}
	return pTemp;
}

//尾插法
template <class T>
void MyList<T>::appendNode(const T& data){
	//1、创建新节点
	Node* pNew = new Node(data);
	if (pTail){ //不是空链表
		//新节点连接到尾节点后头
		pTail->pNext = pNew;
		pNew->pPrev = pTail;
		//更新pTail
		pTail = pNew;
		//维持循环双链表结构
		pTail->pNext = pHead;
		pHead->pPrev = pTail;
	}
	else{
		pHead = pTail = pNew;
	}
}

//头插法
template <class T>
void MyList<T>::addNode(const T& data){
	
}

//中间插入,新节点插入到pos（下标）位置的后面
template <class T>
void MyList<T>::insertNode(int pos, int insertNodeData){
	
}

//遍历
template <class T>
void MyList<T>::travel(){
	Node* pTemp = pHead;
	cout << "list:";
	if (NULL == pHead){
		cout << endl;
		return;
	}

	if (pHead == pTail){
		cout << pHead->data << endl;
		return;
	}

	while (pTemp != pTail){
		cout << pTemp->data << " ";
		pTemp = pTemp->pNext;
	}
	cout << pTail->data << endl;
}

//删除链表中第pos个节点
template <class T>
void MyList<T>::deleteNodePos(int pos){
	
}

//删除链表中第一个节点
template <class T>
void MyList<T>::deleteHead(){
	
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121

    新建一个 main.cpp 的测试文件：

    #include "list.h"

int main(){
	MyList<int> l;

	for (int i = 0; i < 10; i++){
		l.appendNode(i);
		l.travel();
	}


	while (1);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    测试成功：

    在这里插入图片描述

  • 相关阅读:
    【操作系统 | Linux】 文件管理四件套（切换,创建删除，复制移动）
    遥感图像分割 | 基于一种类似UNet的Transformer算法实现遥感城市场景图像的语义分割_适用于卫星图像+航空图像+无人机图像
    网卡mac地址的设置
    C#毕业设计——基于C#+asp.net+sqlserver二手交易系统设计与实现（毕业论文+程序源码）——二手交易系统
    IoC 思想和实现
    JavaIO进阶系列——BIO day1-2
    uniApp 引入iview
    DataTable扩展 列转行方法（2*2矩阵转换）
    初识面向对象&网络&并发编程
    Android开发学习——2.Android开发环境准备
  • 原文地址：https://blog.csdn.net/weixin_62511863/article/details/126551706