1.链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

---

2.链表分类

链表的结构多种多样有三个大分类：

1.单向、双向

2.带头、不带头

3.循环、不循环

而三组之间又可以互相组合，使得链表的结构多达8种，本篇的单链表主要是指单向不带头不循环链表，这也是本篇的重点。

2.1单向链表

单向链表：指链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始，只能通过前一个结点找到后一结点，而不能从后一结点找到前一结点。

2.2双向链表

双向链表：指链表的每个数据中结点都有两个指针，分别指向直接后继和直接前驱，它能从双向链表中的任意一个结点开始，并且可以方便地访问它的前驱结点和后继结点。

2.3不带头链表

不带头链表：指链表以一个结点结构的指针开头，我们存储的数据直接从该指针指向的位置存储，该链表实现相较于带头结点稍微复杂，是各oj题与面试题的常客。

2.4带头链表

带头链表：指链表的以一个不存任何数据的结点开始，我们称之为头结点，而我们存储的数据则从头节点的下一结点开始存储，这样就能有效地避免因链表为空带来的各种问题。

2.5不循环链表

不循环链表：指链表的最后一个结点指向空，使得当链表走到空时我们就可以知道链表已经走到了尽头。

2.6循环链表

循环链表：指链表的最后一个结点指向链表的头结点，从而在逻辑形态中就像一个完整的闭环。

---

3.双向带头循环链表

3.1双向带头循环链表概念

顾名思义，双向带头循环链表就是每个结点有两个指针（双向链表特征），链表最后一个结点指向链表的头结点（循环链表的特征）且拥有哨兵位的链表（带头链表特征）。实际上就是一个简单的组合，但这样的组合所带来的优点相比于单链表来说呈几何被增长。

3.2双向带头循环链表与单链表对比

注：这里的单链表指（不带头不循环单向链表）

1.单链表无法通过后一指针找到前一指针，而双向带头循环链表可以

2.单链表找到尾结点需要遍历链表复杂度是O(n)，而双向带头循环链表的头结点的前一结点就是链表的尾结点复杂度是O(1)。

3.单链表的头插等操作会对链表指针进行频繁操作，因此我们需要传二级指针，而单链表因为有头结点的存在，所以不需要对创建的链表指针更改，传参只用传一级指针即可。

---

4.双向带头循环链表实现

4.1双向带头循环链表结构

typedef int ListDataType;
typedef struct ListNode {								ListDataType val;struct ListNode* prev;struct ListNode* next;
}ListNode;

ListNode:链表头结点代称。

ListDataType:指链表中每个结点存储的数据类型，只需要改动typedef int SListDataType 中的int就能该变节点内存放的数据类型。

val：存放类型结构体变量名。

next：指向下一结点的指针。

prev：指向前一结点的指针。

4.2双向带头循环链表功能实现

文件："List.c"

4.2.1双向带头循环链表初始化

ListNode* ListInit()					//双向链表初始化
{ListNode* head = (ListNode*)malloc(sizeof(ListNode));assert(head);head->next = head;                  //下一结点的指针指向自己head->prev = head;                  //前一结点的指针指向自己  
}

4.2.2双向带头循环链表打印

void ListPrint(ListNode* plist)			//双向链表打印
{assert(plist);ListNode* cur = plist->next;while (cur != plist)				//遍历打印{printf("%d ", cur->val);cur = cur->next;}printf("\n");
}

4.2.3双向带头循环链表尾插

void ListPushBack(ListNode* plist, ListDataType x)		//双向链表尾插
{assert(plist);ListNode* tail = plist->prev;ListNode* head = plist;ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));	//开辟新结点assert(newnode);newnode->val = x;tail->next = newnode;					//尾结点的next指向新结点newnode->prev = tail;					//新节点的prev指向尾结点newnode->next = head;					//新节点的next指向链表头head->prev = newnode;					//表头的prev指向新结点
}

4.2.4双向带头循环链表尾删

void ListPopBack(ListNode* plist)			//双向链表尾删
{assert(plist);ListNode* tail = plist->prev;assert(plist != tail);ListNode* tailprev = tail->prev;ListNode* head = plist;tailprev->next = plist;					//尾部前一结点的next指向链表头head->prev = tailprev;					//表头的prev指向尾部前一结点free(tail);
}

4.2.5双向带头循环链表头插

void ListPushFront(ListNode* plist, ListDataType x)			//双向链表头插
{assert(plist);ListNode* head = plist;ListNode* headnext = plist->next;ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));assert(newnode);newnode->val = x;head->next = newnode;					//链表头的next指向新节点newnode->prev = head;					//新节点的prev指向链表头newnode->next = headnext;				//新节点的next指向原来链表头的nextheadnext->prev = newnode;				//原来链表头的prev指向新节点
}

4.2.6双向带头循环链表头删

void ListPopFront(ListNode* plist)			//双向链表头删
{assert(plist);ListNode* head = plist;ListNode* headnext = plist->next;assert(plist != headnext);ListNode* newnext = headnext->next;newnext->prev = head;					//链表头的下下结点的prev指向链表头head->next = newnext;					//链表头的next指向链表头的下下结点free(headnext);
}

4.2.7双向带头循环链表查找

ListNode* ListFind(ListNode* plist, ListDataType x)			//双向链表查找
{assert(plist);ListNode* head = plist;ListNode* cur = head->next;while (cur != head)						//遍历链表查找val{if (cur->val == x){return cur;						//找到返回所在位置的指针}cur = cur->next;}return NULL;							//找不到返回NULL
}

4.2.8双向带头循环链表按位插入

void ListInsert(ListNode* pos, ListDataType x)				//双向链表位插
{assert(pos);ListNode* posnext = pos->next;ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));assert(newnode);newnode->val = x;			pos->next = newnode;					//插入位置的next指向新结点newnode->prev = pos;					//新结点的prev指向插入位置newnode->next = posnext;				//新结点的next指向插入位置结点的下一结点posnext->prev = newnode;				//插入位置结点的下一结点的prev指向新结点
}

4.2.9双向带头循环链表按位删除

void ListErase(ListNode* pos)				//双向链表位删
{assert(pos);ListNode* posprev = pos->prev;assert(pos != posprev);ListNode* posnext = pos->next;posprev->next = posnext;				//删除位置的前一结点的next指向删除位置的后一结点posnext->prev = posprev;				//删除位置的后一结点的prev指向删除位置的前一结点free(pos);
}

4.2.10双向带头循环链表销毁

void ListDestroy(ListNode* plist)				//双向链表销毁
{assert(plist);ListNode* head = plist;ListNode* cur = head->next;while (cur != head)							//遍历销毁每个存储结点{ListNode* next = cur->next;free(cur);cur = next;}	free(head);									//销毁哨兵位结点		
}

4.3双向带头循环链表头文件

文件："List.h"

#define _CRT_SECURE_NO_WARNINGS 1#pragma once											//防止重定义#include<stdio.h>										//头文件
#include<malloc.h>
#include<assert.h>typedef int ListDataType;								//双向链表存储数据类型typedef struct ListNode {								//双向不带头循环链表结构ListDataType val;struct ListNode* prev;struct ListNode* next;
}ListNode;ListNode* ListInit();									//初始
void ListPrint(ListNode* plist);						//打印
void ListPushBack(ListNode* plist, ListDataType x);		//尾插
void ListPopBack(ListNode* plist);						//尾删
void ListPushFront(ListNode* plist, ListDataType x);	//头插
void ListPopFront(ListNode* plist);						//头删
ListNode* ListFind(ListNode* plist, ListDataType x);	//查找
void ListInsert(ListNode* pos, ListDataType x);			//位插
void ListErase(ListNode* pos);							//位删
void ListDestroy(ListNode* plist);						//销毁

4.4双向带头循环链表测试

文件："List.h"

#include"List.h"void test2()
{ListNode* list;list = ListInit();				//双向链表初始化ListInsert(list, 1);			//双向链表插入ListInsert(list, 2);ListInsert(list, 3);ListInsert(list, 4);ListPrint(list);				ListNode* pos = ListFind(list, 2);		//双向链表查找和删除ListErase(pos);ListPrint(list);pos = ListFind(list, 1);ListErase(pos);ListPrint(list);pos = ListFind(list, 4);ListErase(pos);ListPrint(list);pos = ListFind(list, 3);ListErase(pos);ListPrint(list);//ListErase(list);			//过量删除测试ListDestroy(list);			//双向链表销毁
}void test1()
{ListNode* list;list = ListInit();			//双向链表初始化ListPushBack(list, 0);		//双向链表尾插ListPushBack(list, 1);ListPushBack(list, 2);ListPushBack(list, 3);ListPrint(list);ListPopBack(list);			//双向链表尾删ListPrint(list);ListPopBack(list);ListPrint(list);ListPopBack(list);ListPrint(list);ListPopBack(list);ListPrint(list);//ListPopBack(list);		//过量删除报错ListPushFront(list, 1);		//双向链表头插ListPushFront(list, 2);ListPushFront(list, 3);ListPushFront(list, 4);ListPrint(list);ListPopFront(list);			//双向链表头删ListPrint(list);ListPopFront(list);ListPrint(list);ListPopFront(list);ListPrint(list);ListPopFront(list);ListPrint(list);//ListPopFront(list);		//过量删除报错ListDestroy(list);			//双向链表销毁
}int main()
{test1();test2();return 0;
}

---

✨写在最后

⏱笔记时间：2021_10_3

🌐代码：Gitee:朱雯睿 (zhu-wenrui) - Gitee.com

               Github:Zero0Tw0 · GitHub

💻代码平台：Visual Studio2019