双链表的实现（数据结构）

链表总体可以分为三大类

一、无头和有头

二、单向和双向

三、循环和不循环

从上面分类得知可以组合成8种不同类型链表，其中单链表最为简单，双联表最为复杂，两种链表都实现后其余链表都不成问题。

我们前期博客已将完成了单向无头不循环链表（单链表）的实现，本期博客我们实现双向有头循环链表的实现。

————————————————————————————

说明：

因为此双链表有头结点，（头结点不存储任何有效数据，双链表中只有头结点时为空链表）

因此我们无需修改头结点的地址，只需要改变头结点中前驱指针和后面指针的指向即可，所以传参时只需要传头结点的地址即可。

代码实现：

List.h

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

typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDataType data;
}LTNode;

//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDestroy(LTNode* phead);//为了保持接口一致性，需要在外部将phead置空。

//保留头节点其他的删去
void LTClear(LTNode* phead);
LTNode* BuyNode(LTDataType x);

void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);//判断是否为空

void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);

void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);

LTNode* LTFind(LTNode* phead, LTDataType x);

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"


LTNode* LTInit()
{
	LTNode* phead = BuyNode(-1);
	return phead;
}

LTNode* BuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->prev = newnode->next = newnode;
	newnode->data = x;
	return newnode;
}

void LTDestroy(LTNode* phead)
{
	//哨兵位不能为空
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur!=phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}
//清除链表的内容
void LTClear(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	phead->next = phead;
	phead->prev = phead;
}
void LTPrint(LTNode* phead)
{
	//链表不能为空
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur!=phead)
	{
		printf("%d->",pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
bool LTEmpty(LTNode* phead)
{
	if (phead->next = phead)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyNode(x);
	LTNode* ptail = phead->prev;
	ptail->next = newnode;
	newnode->prev = ptail;
	newnode->next = phead;
	phead->prev = newnode;
}
void LTPopBack(LTNode* phead)
{
	assert(phead);
	//链表不能为空
	assert(phead->next!=phead);
	LTNode* ptail = phead->prev;
	LTNode* prev = ptail->prev;
	phead->prev = prev;
	prev->next = phead;
	free(ptail);
	ptail = NULL;
}

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyNode(x);
	LTNode* next = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;

}
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* pos = phead->next;
	LTNode* next = pos->next;
	phead->next = next;
	next->prev = phead;
	free(pos);
	pos = NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyNode(x);
	LTNode* next = pos->next;
	//pos newnode next
	pos->next = newnode;
	newnode->prev = pos;
	newnode->next = next;
	next->prev = newnode;
}
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur->data!=x && pcur!=phead)
	{
		pcur = pcur->next;
	}
	if (pcur->data == x)
	{
		return pcur;
	}
	else
	{
		return NULL;
	};
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"


int main()
{
	LTNode* phead = LTInit();
	if(LTEmpty(phead))
	{
		printf("链表为空\n");
	}
	LTPushBack(phead,1);
	LTPushBack(phead,2);
	LTPushBack(phead,3);
	LTPushBack(phead,4);
	LTPrint(phead);

	LTPopBack(phead);
	LTPopBack(phead);
	LTPrint(phead);

	LTPopFront(phead);
	LTPrint(phead);

	LTPushFront(phead,100);
	LTPushFront(phead,200);
	LTPushFront(phead,300);
	LTPrint(phead);

	LTNode* ret= LTFind(phead,200);
	if (ret)
	{
		LTErase(ret);
	}
	else
	{
		printf("未找到，无法删除\n");
	}
	LTPrint(phead);

	LTNode* ret2 = LTFind(phead, 2);
	if (ret2)
	{
		LTInsert(ret2, 3);
	}
	else
	{
		printf("未找到，无法插入\n");
	}
	LTPrint(phead);

	LTDestroy(phead);
	phead = NULL;
	return 0;
}