链表/双向循环链表（C/C++）

? ? ? ? 本篇将给出双向循环链表的有关操作，以及对应的一些解释，大多都以注释给出。本篇给出的双向循环链表全称为带头双向循环链表。即如下图所示：

? ? ? ? 在本篇中一共包含三个代码片段，分别为：双向链表需要实现的内容、双向链表函数的实现、双向链表的全部代码与测试。如有需要，可直接在对应位置查找。

? ? ? ? 其中的head，为头结点，我们也称之为哨兵位，该位置不会存放任何的有效数据，但这个结点是真实存在的。

? ? ? ? 注意：对于头结点（哨兵位）来说，由图我们可以得出：

? ? ? ? 1.哨兵位的下一位才是第一个结点，即head->next是第一个结点;

? ? ? ? 2.?哨兵位的前一个结点为尾结点，即head->prior为最后一个结点。

? ? ? ? 对于哨兵为的意义来说就是：遍历循环链表的时避免死循环。

1.双向链表的实现内容

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct ListNode {
	DataType data;
	struct ListNode* prior;
	struct ListNode* next;
}LTNode;

//双向链表初始化
LTNode* LTInit();
//双向链表的销毁
void LTDestroy(LTNode* phead);
//判断链表是否为NULL
void LTEmpty(LTNode* phead);
//遍历双向链表
void LTPrint(LTNode* phead);

//尾插/头插
void LTPushBack(LTNode* phead,DataType x);
void LTPushFront(LTNode* phead, DataType x);

//尾删/头删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

//查找结点位置
LTNode* LTFind(LTNode* phead, DataType x);  

//在指定位置之前/之后插入数据
void LTInsert(LTNode* pos, DataType x);
void LTInsertBefore(LTNode* pos, DataType x);

//删除指定位置
void LTErase(LTNode* pos);

2.双向链表函数的实现?

? ? ? ? 在以下的实现内容中的每个函数，都会有一定的注释，便于读者理解：

//创建一个头结点
LTNode* CreateNode(DataType x) {
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	//判断开辟空间是否成功，但其实一般情况下都是可以申请成功（以下判断条件可有可无）
	if (newNode == NULL) {
		perror("malloc:");
		exit(1);
	}
	newNode->data = x;
	//创建一个新结点的同时，将新节点的前驱和后继指向自己
	newNode->next = newNode->prior = newNode;
	return newNode;
}

//双向链表初始化
LTNode* LTInit() {
	LTNode* head = (LTNode*)malloc(sizeof(LTNode));
	if (head == NULL) {
		perror("malloc:");
		exit(1);
	}
	head->data = -1;
	head->prior = head->next = head;
	//可以用创建结点函数来获取头结点
	//head = CreateNode(-1);
	return head;
}

//尾插，在尾结点插入一个元素
void LTPushBack(LTNode* phead,DataType x) {
	//传过来的头结点不能为NULL
	assert(phead);
	LTNode* newNode = CreateNode(x);
	//尾结点的下一个结点指向的是头结点
	newNode->next = phead;
	//头结点的prior结点为尾结点，将新节点的前驱指向原来的尾结点
	newNode->prior = phead->prior;
	
	//phead->prior为原来的尾结点,将原来的尾结点指向newNode
	phead->prior->next = newNode;
	//phead->prior指向新节点
	phead->prior = newNode;
}

//头插，在第一个结点处插入元素
void LTPushFront(LTNode* phead, DataType x) {
	//传过来的头结点不能为NULL
	assert(phead);
	LTNode* newNode = CreateNode(x);
	//将新节点的前驱指向头结点
	newNode->prior = phead;
	//新节点的后继指向原来的第一个结点
	newNode->next = phead->next;

	//phead->next为原来的头结点
	phead->next->prior = newNode;
	phead->next = newNode;
}

//尾删，删除链表的尾结点
void LTPopBack(LTNode* phead) {
	assert(phead);
	//第一个结点也不能为NULL，因为这是删除
	assert(phead->next != phead);
	//哨兵位的前一个结点为尾结点
	LTNode* delete = phead->prior;
	//prior为尾结点的前一个结点
	LTNode* prior = delete->prior;

	//将尾结点的前一个结点指向头结点
	prior->next = phead;
	//更新头结点的前驱（尾结点）
	phead->prior = prior;

	//释放空间，同时指针置为NULL
	free(delete);
	delete = NULL; 
}

//头删，删除链表的第一个结点
void LTPopFront(LTNode* phead) {
	assert(phead);
	//第一个结点也不能为NULL，因为这是删除
	assert(phead->next != phead);

	//phead->next为第一个结点
	LTNode* delete = phead->next;
	LTNode* next = delete->next;

	//将第二节点的前驱指向phead(delete->prior)
	next->prior = delete->prior;
	//更新第一个结点
	phead->next = next;

	//释放空间，同时指针置为NULL
	free(delete);
	delete = NULL;
}

//遍历链表
void LTPrint(LTNode* phead) {
	assert(phead);
	if (phead->next == phead) {
		printf("该链表为NULL\n");
		return;
	}
	//将current指向第一个结点
	LTNode* current = phead->next;
	printf("head->");
	//当current为头结点时，停止遍历
	while (current!= phead) {
		printf("%d->", current->data);
		current = current->next;
	}
	printf("head\n");
}

//判断链表是否为NULL
void LTEmpty(LTNode* phead) {
	assert(phead);
	//头结点的后继指向自己或者前驱指向自己时，链表为NULL
	if (phead->next == phead) {
		printf("空链表\n");
	}
	else {
		printf("非空链表\n");
	}
}

//链表的销毁
void LTDestroy(LTNode* phead) {
	assert(phead);
	//从第一个结点开始删除
	LTNode* current = phead->next;
	while (current != phead) {
		//先找到下一个结点
		LTNode* next = current->next;
		free(current);
		//更新current
		current = next;
	}
	//删除尾结点
	free(phead);
	//注：由于phead与传入的指针head同为一级指针，
	//free(phead)只能释放head存放的东西，
	//但不能改变head的地址，在函数外还需要将head置为NULL
}

//找元素
LTNode* LTFind(LTNode* phead, DataType x) {
	assert(phead);
	//从第一个结点开始遍历
	LTNode* current = phead->next;
	while (current != phead) {
		if (current->data == x) {
			return current;
		}
		current = current->next;
	}
	return NULL;
}

//在指定位置尾插
void LTInsert(LTNode* pos, DataType x) {
	assert(pos);
	LTNode* newNode = CreateNode(x);
	//改变新节点的前驱和后继指向
	newNode->next = pos->next;
	newNode->prior = pos;

	//将pos位置的后继的proir指针指向新节点
	pos->next->prior = newNode;
	//pos的next指针指向新节点
	pos->next = newNode;
}

//在指定位置之前插入元素
void LTInsertBefore(LTNode* pos, DataType x) {
	assert(pos);
	LTNode* newNode = CreateNode(x);
	//改变新节点的前驱和后继指向
	newNode->prior = pos->prior;
	newNode->next = pos;

	//将pos位置的前驱的next指针指向新节点
	pos->prior->next = newNode;
	//将pos的prior指针指向新节点
	pos->prior = newNode;
}

//删除指定位置的元素
void LTErase(LTNode* pos) {
	assert(pos);
	//将pos位置的前驱结点和后继结点记录下来
	LTNode* prior = pos->prior;
	LTNode* next = pos->next;

	//前驱结点的next指针指向后继结点
	prior->next = next;
	//后继结点的proir指针指向前驱结点
	next->prior = prior;
	free(pos);
	pos = NULL;
}

3.双向链表的全部代码与测试

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct ListNode {
	DataType data;
	struct ListNode* prior;
	struct ListNode* next;
}LTNode;

//创建一个头结点
LTNode* CreateNode(DataType x) {
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	//判断开辟空间是否成功，但其实一般情况下都是可以申请成功（以下判断条件可有可无）
	if (newNode == NULL) {
		perror("malloc:");
		exit(1);
	}
	newNode->data = x;
	//创建一个新结点的同时，将新节点的前驱和后继指向自己
	newNode->next = newNode->prior = newNode;
	return newNode;
}

//双向链表初始化
LTNode* LTInit() {
	LTNode* head = (LTNode*)malloc(sizeof(LTNode));
	if (head == NULL) {
		perror("malloc:");
		exit(1);
	}
	head->data = -1;
	head->prior = head->next = head;
	//可以用创建结点函数来获取头结点
	//head = CreateNode(-1);
	return head;
}

//尾插，在尾结点插入一个元素
void LTPushBack(LTNode* phead,DataType x) {
	//传过来的头结点不能为NULL
	assert(phead);
	LTNode* newNode = CreateNode(x);
	//尾结点的下一个结点指向的是头结点
	newNode->next = phead;
	//头结点的prior结点为尾结点，将新节点的前驱指向原来的尾结点
	newNode->prior = phead->prior;
	
	//phead->prior为原来的尾结点,将原来的尾结点指向newNode
	phead->prior->next = newNode;
	//phead->prior指向新节点
	phead->prior = newNode;
}

//头插，在第一个结点处插入元素
void LTPushFront(LTNode* phead, DataType x) {
	//传过来的头结点不能为NULL
	assert(phead);
	LTNode* newNode = CreateNode(x);
	//将新节点的前驱指向头结点
	newNode->prior = phead;
	//新节点的后继指向原来的第一个结点
	newNode->next = phead->next;

	//phead->next为原来的头结点
	phead->next->prior = newNode;
	phead->next = newNode;
}

//尾删，删除链表的尾结点
void LTPopBack(LTNode* phead) {
	assert(phead);
	//第一个结点也不能为NULL，因为这是删除
	assert(phead->next != phead);
	//哨兵位的前一个结点为尾结点
	LTNode* delete = phead->prior;
	//prior为尾结点的前一个结点
	LTNode* prior = delete->prior;

	//将尾结点的前一个结点指向头结点
	prior->next = phead;
	//更新头结点的前驱（尾结点）
	phead->prior = prior;

	//释放空间，同时指针置为NULL
	free(delete);
	delete = NULL; 
}

//头删，删除链表的第一个结点
void LTPopFront(LTNode* phead) {
	assert(phead);
	//第一个结点也不能为NULL，因为这是删除
	assert(phead->next != phead);

	//phead->next为第一个结点
	LTNode* delete = phead->next;
	LTNode* next = delete->next;

	//将第二节点的前驱指向phead(delete->prior)
	next->prior = delete->prior;
	//更新第一个结点
	phead->next = next;

	//释放空间，同时指针置为NULL
	free(delete);
	delete = NULL;
}

//遍历链表
void LTPrint(LTNode* phead) {
	assert(phead);
	if (phead->next == phead) {
		printf("该链表为NULL\n");
		return;
	}
	//将current指向第一个结点
	LTNode* current = phead->next;
	printf("head->");
	//当current为头结点时，停止遍历
	while (current!= phead) {
		printf("%d->", current->data);
		current = current->next;
	}
	printf("head\n");
}

//判断链表是否为NULL
void LTEmpty(LTNode* phead) {
	assert(phead);
	//头结点的后继指向自己或者前驱指向自己时，链表为NULL
	if (phead->next == phead) {
		printf("空链表\n");
	}
	else {
		printf("非空链表\n");
	}
}

//链表的销毁
void LTDestroy(LTNode* phead) {
	assert(phead);
	//从第一个结点开始删除
	LTNode* current = phead->next;
	while (current != phead) {
		//先找到下一个结点
		LTNode* next = current->next;
		free(current);
		//更新current
		current = next;
	}
	//删除尾结点
	free(phead);
	//注：由于phead与传入的指针head同为一级指针，
	//free(phead)只能释放head存放的东西，
	//但不能改变head的地址，在函数外还需要将head置为NULL
}

//找元素
LTNode* LTFind(LTNode* phead, DataType x) {
	assert(phead);
	//从第一个结点开始遍历
	LTNode* current = phead->next;
	while (current != phead) {
		if (current->data == x) {
			return current;
		}
		current = current->next;
	}
	return NULL;
}

//在指定位置尾插
void LTInsert(LTNode* pos, DataType x) {
	assert(pos);
	LTNode* newNode = CreateNode(x);
	//改变新节点的前驱和后继指向
	newNode->next = pos->next;
	newNode->prior = pos;

	//将pos位置的后继的proir指针指向新节点
	pos->next->prior = newNode;
	//pos的next指针指向新节点
	pos->next = newNode;
}

//在指定位置之前插入元素
void LTInsertBefore(LTNode* pos, DataType x) {
	assert(pos);
	LTNode* newNode = CreateNode(x);
	//改变新节点的前驱和后继指向
	newNode->prior = pos->prior;
	newNode->next = pos;

	//将pos位置的前驱的next指针指向新节点
	pos->prior->next = newNode;
	//将pos的prior指针指向新节点
	pos->prior = newNode;
}

//删除指定位置的元素
void LTErase(LTNode* pos) {
	assert(pos);
	//将pos位置的前驱结点和后继结点记录下来
	LTNode* prior = pos->prior;
	LTNode* next = pos->next;

	//前驱结点的next指针指向后继结点
	prior->next = next;
	//后继结点的proir指针指向前驱结点
	next->prior = prior;
	free(pos);
	pos = NULL;
}

void Test01() {
	LTNode* head = LTInit();
	LTPushBack(head, 1);
	LTPushBack(head, 2);
	LTPushBack(head, 3);
	LTPushBack(head, 4);
	LTPrint(head); // 1 2 3 4

	LTPushFront(head, 5);
	LTPushFront(head, 6);
	LTPushFront(head, 7);
	LTPrint(head); // 7 6 5 1 2 3 4

	LTPopBack(head);
	LTPrint(head); // 7 6 5 1 2 3 

	LTPopFront(head);
	LTPrint(head); // 6 5 1 2 3 


	LTNode* Find = LTFind(head, 3);
	if (Find == NULL) {
		printf("没有找到\n");    //找到了
	}
	else {
		printf("找到了\n");   
	}

	LTInsert(Find, 5); 
	LTInsertBefore(Find, 6); 
	LTPrint(head); // 6 5 1 2 6 3 5

	LTErase(Find);
	LTPrint(head); // 6 5 1 2 6 5
	LTDestroy(head);
	head = NULL;
}

int main() {
	Test01();
	return 0;
}

? ? ? ? 测试结果：

? ? ? ? 这些所有操作即为带头双向循环链表的所有操作了。?