线性表之双链表

具体的链表分类和单链表，前文已经论述过了：【数据结构】线性表之链表
但是，单链表并不能完全弥补顺序表的缺陷，因此有了双向带头循环链表。
本文论述的就是双向带头循环链表，可以完全弥补顺序表的缺陷。

1. 双向带头循环链表

1.1 结构

在这里插入图片描述

1.2 结点定义

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;//数据域
	struct ListNode* next;//指向下一个结点
	struct ListNode* prev;//指向前一个结点
}ListNode;

1.3 函数声明

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入 任意位置之前都可以
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
// 判断链表是否为空
bool ListEmpty(ListNode* phead);
//计算链表长度
size_t ListSize(ListNode* phead);

2. 基本功能的实现

2.1 创建返回链表的头结点

// 创建链表的头结点.
ListNode* ListCreate()
{
	ListNode* guard = (ListNode*)malloc(sizeof(struct ListNode));
	if (!guard)
	{
		perror("malloc fail");
		exit(-1);
	}
	guard->next = guard;
	guard->prev = guard;
	guard->data = 0;

	return guard;
}

2.2 创建新节点

//创建新节点
static ListNode* BuyListNode(LTDataType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(struct ListNode));
	if (!node)
	{
		perror("malloc fail");
		exit(-1);
	}
	
	node->next = NULL;
	node->prev = NULL;
	node->data = x;

	return node;
}

static 修饰函数，使得该函数只能在该源文件中使用。也就不用声明。
（详细了解可浏览之前的文章：C语言关键字——static详解）

2.3 双向链表尾插

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	/*ListNode* newNode = BuyListNode(x);
	ListNode* tail = pHead->prev;

	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = pHead;
	pHead->prev = newNode;*/
	ListInsert(pHead, x);
}

2.4 双向链表头插

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	//ListNode* newNode = BuyListNode(x);
	code-1  须先链接newNode和pHead->next
	///*newNode->next = pHead->next;
	//pHead->next->prev = newNode;
	//pHead->next = newNode;
	//newNode->prev = pHead;*/

	code-2推荐   不用考虑先后顺序
	//ListNode* first = pHead->next;

	//pHead->next = newNode;
	//newNode->prev = pHead;
	//newNode->next = first;
	//first->prev = newNode;
	ListInsert(pHead->next, x);
}

2.5 双向链表尾删

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(!ListEmpty(pHead));

	/*ListNode* tail = pHead->prev;
	ListNode* tailprev = tail->prev;

	tailprev->next = pHead;
	pHead->prev = tailprev;
	free(tail);*/
	ListErase(pHead->prev);
}

2.6 双向链表头删

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(!ListEmpty(pHead));

	/*ListNode* first = pHead->next;
	ListNode* second = first->next;

	pHead->next = second;
	second->prev = pHead;

	free(first);*/
	ListErase(pHead->next);
}

2.7 双向链表打印

// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);

	printf("pHead<->");
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d<->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.8 判断链表是否为空

// 判断链表是否为空
bool ListEmpty(ListNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

2.9 计算链表长度

//计算链表长度
size_t ListSize(ListNode* phead)
{
	assert(phead);

	ListNode* cur = phead->next;
	size_t n = 0;
	while (cur != phead)
	{
		n++;
		cur = cur->next;
	}
	return n;
}

2.10 双向链表查找

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
			return cur;

		cur = cur->next;
	}

	return NULL;
}

2.11 在pos的前面进行插入

// 双向链表在pos的前面进行插入  任意位置之前都可以
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);

	ListNode* newNode = BuyListNode(x);
	ListNode* prev = pos->prev;
	
	prev->next = newNode;
	newNode->next = pos;
	pos->prev = newNode;
	newNode->prev = prev;
}

2.12 删除pos位置的节点

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);
}

2.13 双向链表销毁

// 双向链表销毁
// 可以使用二级指针，将空头置NULL
// 建议：一级指针，保持头部的接口性
void ListDestory(ListNode* pHead)
{
	assert(pHead);

	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		/*pHead->next = next;
		next->prev = pHead;*/ //因为是销毁 这里可不写
		free(cur);

		cur = next;
	}
	free(pHead);
}

3 源文件

DList.h：相关声明

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入 任意位置之前都可以
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
// 判断链表是否为空
bool ListEmpty(ListNode* phead);
//计算链表长度
size_t ListSize(ListNode* phead);

DList.c：功能实现

#include "DList.h"

// 创建链表的头结点.
ListNode* ListCreate()
{
	ListNode* guard = (ListNode*)malloc(sizeof(struct ListNode));
	if (!guard)
	{
		perror("malloc fail");
		exit(-1);
	}
	guard->next = guard;
	guard->prev = guard;
	guard->data = 0;

	return guard;
}
//创建新节点
static ListNode* BuyListNode(LTDataType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(struct ListNode));
	if (!node)
	{
		perror("malloc fail");
		exit(-1);
	}
	
	node->next = NULL;
	node->prev = NULL;
	node->data = x;

	return node;
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	/*ListNode* newNode = BuyListNode(x);
	ListNode* tail = pHead->prev;

	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = pHead;
	pHead->prev = newNode;*/
	ListInsert(pHead, x);
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	//ListNode* newNode = BuyListNode(x);
	code-1  须先链接newNode和pHead->next
	///*newNode->next = pHead->next;
	//pHead->next->prev = newNode;
	//pHead->next = newNode;
	//newNode->prev = pHead;*/

	code-2推荐   不用考虑先后顺序
	//ListNode* first = pHead->next;

	//pHead->next = newNode;
	//newNode->prev = pHead;
	//newNode->next = first;
	//first->prev = newNode;
	ListInsert(pHead->next, x);
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(!ListEmpty(pHead));

	/*ListNode* tail = pHead->prev;
	ListNode* tailprev = tail->prev;

	tailprev->next = pHead;
	pHead->prev = tailprev;
	free(tail);*/
	ListErase(pHead->prev);
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(!ListEmpty(pHead));

	/*ListNode* first = pHead->next;
	ListNode* second = first->next;

	pHead->next = second;
	second->prev = pHead;

	free(first);*/
	ListErase(pHead->next);
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);

	printf("pHead<->");
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d<->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
// 判断链表是否为空
bool ListEmpty(ListNode* phead)
{
	assert(phead);

	return phead->next == phead;
}
//计算链表长度
size_t ListSize(ListNode* phead)
{
	assert(phead);

	ListNode* cur = phead->next;
	size_t n = 0;
	while (cur != phead)
	{
		n++;
		cur = cur->next;
	}
	return n;
}

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);

	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
			return cur;

		cur = cur->next;
	}

	return NULL;
}

// 双向链表在pos的前面进行插入  任意位置之前都可以
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);

	ListNode* newNode = BuyListNode(x);
	ListNode* prev = pos->prev;
	
	prev->next = newNode;
	newNode->next = pos;
	pos->prev = newNode;
	newNode->prev = prev;
}

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;

	prev->next = next;
	next->prev = prev;

	free(pos);
}
// 双向链表销毁
// 可以使用二级指针，将空头置NULL
// 建议：一级指针，保持头部的接口性
void ListDestory(ListNode* pHead)
{
	assert(pHead);

	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		/*pHead->next = next;
		next->prev = pHead;*/ //因为是销毁 这里可不写
		free(cur);

		cur = next;
	}
	free(pHead);
}

test.c：功能测试

#define _CRT_SECURE_NO_WARNINGS

#include "DList.h"

void Test1()
{
	// 初始化
	ListNode* DList = ListCreate();
	//尾插
	ListPushBack(DList, 1);
	ListPushBack(DList, 2);
	ListPushBack(DList, 3);
	ListPushBack(DList, 4);
	//打印
	ListPrint(DList);
	//头插
	ListPushFront(DList, 10);
	ListPushFront(DList, 20);
	ListPushFront(DList, 30);
	ListPushFront(DList, 40);
	//打印
	ListPrint(DList);
}
void Test2()
{
	// 初始化
	ListNode* DList = ListCreate();
	//尾插
	ListPushBack(DList, 1);
	ListPushBack(DList, 2);
	ListPushBack(DList, 3);
	ListPushBack(DList, 4);
	//打印
	ListPrint(DList);
	//尾删
	ListPopBack(DList);
	//ListPopBack(DList);
	//ListPopBack(DList);
	//ListPopBack(DList);
	//ListPopBack(DList);
	//头删
	ListPopFront(DList);
	//ListPopFront(DList);
	//ListPopFront(DList);
	//ListPopFront(DList);
	//ListPopFront(DList);

	//打印
	ListPrint(DList);

	//销毁
	ListDestory(DList);
	DList = NULL;
}
void Test3()
{
	// 初始化
	ListNode* DList = ListCreate();
	//尾插
	ListPushBack(DList, 1);
	ListPushBack(DList, 2);
	ListPushBack(DList, 3);
	ListPushBack(DList, 4);
	//打印
	ListPrint(DList);
	//pos位置插入  
	ListNode* pos = ListFind(DList, 1);
	ListInsert(pos, 100);
	//打印
	ListPrint(DList);
	//pos位置删除  
	pos = ListFind(DList, 2);
	//ListErase(pos);
	ListErase(DList->next);
	ListErase(DList->next);
	ListErase(DList->next);
	ListErase(DList->next);
	ListErase(DList->next);
	//ListErase(DList->next);

	//打印
	ListPrint(DList);
}
int main()
{
	//Test1();
	//Test2();
	Test3();

	return 0;
}