数据结构——双向循环链表（C语言实现）_双向循环链表c语言代码

目录

双向循环链表：结构复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势

这是双向循环链表的示意图（注意第一个为哨兵卫头节点）

头文件及定义

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int LTDataType;
typedef struct ListNode
{
	LTDateType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;
 
LTNode* ListInit();//初始化
 
void ListDestroy(LTNode* phead);//销毁
 
void ListPrint(LTNode* phead);//打印
 
LTNode* BuyListNode(LTDataType x);//创建新节点
 
void ListPushBack(LTNode* phead, LTDataType x);//尾插
 
void ListPopBack(LTNode* phead);//尾删
 
void ListPushFront(LTNode* phead, LTDataType x);//头插
 
void ListPopFront(LTNode* phead);//头删
 
LTNode* ListFind(LTNode* phead, LTDataType x);//查找
 
void ListInsert(LTNode* pos, LTDataType x);//在pos之前位置插入
 
void ListErase(LTNode* pos);//删除pos元素

双链表初始化

头节点不存储有效数据，自己指向自己

LTNode* ListInit()//采用返回指针的方式，不需要用二级指针了
{
	// 哨兵位头结点（不存储有效数据）
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

双链表打印

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

双链表创建新节点

LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

双链表尾插

void ListPushBack(LTNode* phead, LTDataType x)
//不改变plist,改变的是plist指向的结构体，不需要二级指针了
{
	assert(phead);//头节点不能为空，
    
    //这段注释为第一种方法
	//LTNode* tail = phead->prev;
	//LTNode* newnode = BuyListNode(x);
	//tail->next = newnode;
	//newnode->prev = tail;
	//newnode->next = phead;
	//phead->prev = newnode;
 
	ListInsert(phead, x);//第二种方法，复用插入接口
}

双链表尾删

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
 
	第一种方法
	//LTNode* tail = phead->prev;
	//phead->prev = tail->prev;
	//tail->prev->next = phead;
	//free(tail);
 
	ListErase(phead->prev);//复用
}

双链表头插

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	第一种方法
	//LTNode* newnode = BuyListNode(x);
	//LTNode* next = phead->next;
	//phead->next = newnode;
	//newnode->prev = phead;
	//newnode->next = next;
	//next->prev = newnode;
 
	ListInsert(phead->next, x);//复用
}

双链表头删

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);// 链表空了就不删
 
	//第一种方法
	//LTNode* next = phead->next;
	//LTNode* nextNext = next->next;
	//phead->next = nextNext;
	//nextNext->prev = phead;
	//free(next);
 
	ListErase(phead->next);//复用
}

双链表查找

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;//找不到返回NULL
}

双链表删除元素

需要配合查找才能使用

// 删除pos位置
void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
	pos = NULL;
}

双链表在pos位置之前插入

void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyListNode(x);
 
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

双链表销毁

void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;//由于没传二级指针，需要在外面让plist = NULL才有用
}

---

代码测试

void TestList1()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPrint(plist);
 
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
}
 
void TestList2()
{
	LTNode* plist = ListInit();
	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	ListPrint(plist);
 
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
 
	LTNode* pos1 = ListFind(plist, 2);
	if (pos1)
	{
		ListErase(pos1);
	}
	ListPrint(plist);
 
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);
 
	ListDestroy(plist);
	plist = NULL;
}
 
int main()
{
	TestList1();
	TestList2();
	return 0;
}