【数据结构与算法】链表

港控/mmm° 2024-04-26 03:25 77阅读 0赞

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

#### 阅读指南 ####

*  链表简介
 *  无头单链表准备工作
 *  无头单链表尾插法实现一
 *  无头单链表尾插法实现二
 *  遍历
 *  无头单链表头插法
 *  无头单链表中间插入
 *  无头单链表删除
 *  无头单链表模板类
 *  循环双链表

## 链表简介 ##

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

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

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

![在这里插入图片描述][bd1bcb00cd164b96a24d57730d2eec38.png]

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

![在这里插入图片描述][65be5e82afe2499f93a4a4318ca0c0f8.png]

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

## 无头单链表准备工作 ##

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

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

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

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

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

#include <stdio.h>
    
    //链表节点类型
    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.  原尾节点的 **pNext** 指向新节点

#include <stdio.h>
    
    #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

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

![在这里插入图片描述][d38744b34cf3461994ebca4079f763b2.png]

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

![在这里插入图片描述][8517488641854a018add4261302061d6.png]

## 无头单链表尾插法实现二 ##

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

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

#include <stdio.h>
    
    #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

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

![在这里插入图片描述][1833c844eb194ebc91f8abfb5cb9a764.png]

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

![在这里插入图片描述][efdc0b342bf74c1983e8f248976b3479.png]

## 遍历 ##

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

//遍历声明
    #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

测试结果如下：

![在这里插入图片描述][463bea8dbae6408e87c85b287c715873.png]

## 无头单链表头插法 ##

头插法的思路很简单：

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

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

![在这里插入图片描述][61e66f1d57e24e0c870b76f0fd8dfc42.png]

## 无头单链表中间插入 ##

![在这里插入图片描述][319e3bab4e284038a468dee64114dfa7.png]

//中间插入 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

测试结果如下：

![在这里插入图片描述][55122027604c436381a04a9d43ad4d6a.png]

## 无头单链表删除 ##

删除的思路为：

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);
    }

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

![在这里插入图片描述][1ec0032351154e88bb4acf3f2ce835bd.png]

## 无头单链表模板类 ##

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

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

#pragma once 
    #include <iostream>
    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; 
    }

新建一个 **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;
    }

测试成功：

![在这里插入图片描述][c47ed82ba91b45e9b0feb23d11578b18.png]

## 循环双链表 ##

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

#pragma once 
    #include <iostream>
    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(){
        
    	
    }

新建一个 **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;
    }

测试成功：

![在这里插入图片描述][e6d8947751f9462f93289e49987e77cf.png]

[Link 1]: https://blog.csdn.net/weixin_62511863?spm=1011.2421.3001.5343
[Link 2]: https://blog.csdn.net/weixin_62511863/category_11984530.html?spm=1001.2014.3001.5482
[bd1bcb00cd164b96a24d57730d2eec38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/dc3349960b13451cab5b0f971fa2bede.png
[65be5e82afe2499f93a4a4318ca0c0f8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/26932bd15cda4186966f6eb9389d61d9.png
[d38744b34cf3461994ebca4079f763b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/743af43167b04689ac3f6ed7c533aa1b.png
[8517488641854a018add4261302061d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/50470b5cf6174317b47625b5ff5a9b7c.png
[1833c844eb194ebc91f8abfb5cb9a764.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/622e7fb236ae4142ba6fe0825f425ec1.png
[efdc0b342bf74c1983e8f248976b3479.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/217ecb1d006f48ed94939e360089d552.png
[463bea8dbae6408e87c85b287c715873.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/baa6d159ca31465aa35861a15f8725c0.png
[61e66f1d57e24e0c870b76f0fd8dfc42.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/feaef1d56d5f4b35848970a618c0b5da.png
[319e3bab4e284038a468dee64114dfa7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/eb4cb751ceab4af28c603ae174b7dd67.png
[55122027604c436381a04a9d43ad4d6a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/621c98da0893485e9d8f77534c73a36c.png
[1ec0032351154e88bb4acf3f2ce835bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/868f7ce76b464ec7b25657ddca5eb0f6.png
[c47ed82ba91b45e9b0feb23d11578b18.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/028c0852227448e29f8f0acfe70a47d5.png
[0197a8dd13ad49249cd888129994f769.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/59752eb06e8742fca34ecb42c5a6eb17.png
[e6d8947751f9462f93289e49987e77cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/a20b6ad7d9fc452ca0f598015650eaae.png