4.双向循环链表的模拟实现，双向循环链表的模拟实现详解

温馨提示：这篇文章已超过460天没有更新，请注意相关的内容是否还可用！

摘要：本篇文章介绍了双向循环链表的模拟实现。双向循环链表是一种数据结构，其节点包含数据元素和指向前后节点的指针。模拟实现过程中，需要定义节点类，并实现节点的插入、删除、查找等操作。还需要实现链表的整体操作，如遍历、反转等。该数据结构的实现对于数据的高效处理和存储具有重要意义。

1.双向链表的实现

4.双向循环链表的模拟实现，双向循环链表的模拟实现详解第1张

1.1双向链表节点的结构声明

typedef int LTDataType;
typedef struct ListNode
{
    struct ListNode* prev;  // 指向该节点的前一个节点
	struct ListNode* next;  // 指向该节点的后一个节点
	LTDataType data;        // 该节点中存储的数据
}LTNode;					// 将这个结构体重新命名为LTNode

1.2链表的初始化

4.双向循环链表的模拟实现，双向循环链表的模拟实现详解第2张

LTNode* ListInit()
{
    // 创建一个节点，这个节点是哨兵位
	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
	if (guard == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
    // 这是一个带头双向循环的链表
    // 此时只有一个哨兵位，因此哨兵位的前一个节点和后一个节点都是哨兵位本身
	guard->next = guard;
	guard->prev = guard;
	return guard;
}

1.3 链表的尾插

// 创建一个新节点
LTNode* BuyListNode(LTDataType x)
{
    // 创建一个新节点
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
    // 初始化这个节点的指针，和数据
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
    
	return node;
}

4.双向循环链表的模拟实现，双向循环链表的模拟实现详解第3张

// 尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
    // 尾插一个数据前，创建一个新节点，将这个数据存储到这个节点中
	LTNode* newnode = BuyListNode(x);
    
    // phead就是头节点，因为是双向循环链表，所以phead->prev就是双向循环链表的尾节点
	LTNode* tail = phead->prev;    
    // 尾插一个新节点，就是将下面三个节点，按照顺序进行连接
    // tail newnode phead 
    // 1.尾节点指向新节点
	tail->next = newnode; 
    // 2.新节点的前指针，指向尾节点
	newnode->prev = tail;
    // 3.新节点的后指针，指向头节点
	newnode->next = phead;
    // 4.头节点的前指针，指向新节点，新节点成为这个双向循环链表的新的尾节点
	phead->prev = newnode;
}

1.4链表的打印

4.双向循环链表的模拟实现，双向循环链表的模拟实现详解第4张

void ListPrint(LTNode* phead)
{
	assert(phead);
	printf("phead");
    
    //不打印哨兵位的头
    // phead就是哨兵位，不存储数据，因此不需要进行打印
	LTNode* cur = phead->next;  
    
    // cur等于phead，说明已经循环了一周，所有的数据都已经被打印了
	while (cur != phead)
	{
		printf("%d", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

1.5链表的头插

方法一

4.双向循环链表的模拟实现，双向循环链表的模拟实现详解第5张

方法二

4.双向循环链表的模拟实现，双向循环链表的模拟实现详解第6张

// 因为双向循环链表是有哨兵位的，头插的节点是插入到哨兵位之后的
// 也就是将 head newnode d1 这三个节点，按照顺序连接就可以
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
    // 方法一：
    // 需要关心节点连接的循序（如果先执行第二步，那么phead指向的就是新节点，而不是d1节点）
	// 创建一个要插入的新节点，存储的数据为x
	LTNode* newnode = BuyListNode(x);
    
    // 第一步
    // phead->next就是d1节点
    // 新节点的后指针指向d1节点
	newnode->next = phead->next;
    // phead->next->prev 就是d1节点的前指针；也就是d1节点的前指针指向新节点
	phead->next->prev = newnode;
    // 第二步
    // 哨兵位的后指针指向新节点
	phead->next = newnode;
    // 新节点的前指针指向哨兵位
	newnode->prev = phead;
    
    
    // 方法二：
    /*
	// 不关心顺序（第一步和第二步哪个先执行都可以）
	LTNode* newnode = BuyListNode(x);
	// 1.先保存d1节点的地址
	LTNode* first = phead->next;
	// 第一步：
	// 哨兵位的后指针指向新节点
	phead->next = newnode;
	// 新节点的前指针指向哨兵位
	newnode->prev = phead;
	
	// 第二步：
	// 新节点的后指针指向d1节点
	newnode->next = first;
	// d1节点的前指针指向新节点
	first->prev = newnode;
	*/
    
    // 方法三：
    // 在phead->next位置前插入，也就是头插
    // void ListInsert(LTNode* pos, LTDataType x)  这个函数就是在pos位置前插入一个节点
	// ListInsert(phead->next, x);
}

1.6链表的尾删

4.双向循环链表的模拟实现，双向循环链表的模拟实现详解第7张

// 用来判断是否为空链表，空链表无法头删
bool ListEmpty(LTNode* phead)
{
	assert(phead);
    // 方法一（比较麻烦）
	/*
	if (phead->next == phead)
		return true;
	else
		return false;
	*/
    // 如果相等，那么就是空链表（因为这是一个双向循环链表）
	return phead->next == phead;
}

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
    // 哨兵位的前指针指向的就是双向循环链表的尾节点
	LTNode* tail = phead->prev;
    // 尾节点的前指针指向的前节点将其命名为prev
	LTNode* prev = tail->prev;
    // 要进行尾删，也就是将 phead tail prev 三个节点中的tail删除，再将phead和prev连接
    // 1.连接phead和prev
	prev->next = phead;
	phead->prev = prev;
    
    // 释放要删除的节点空间，将其变为空指针，防止产生野指针
	free(tail);
	tail = NULL;
}

1.7链表的头删

4.双向循环链表的模拟实现，双向循环链表的模拟实现详解第8张

// 对于双向循环链表,头删就是将 phead d1 d2中的d1节点删除，再将phead和d2节点连接
void ListPopFront(LTNode* phead)
{
	assert(phead);
    // 保证这个双向循环链表不是空链表
	assert(!ListEmpty(phead));
	
    // phead->next就是d1节点
    LTNode* first = phead->next;
    // phead->next->next就是d2节点
	LTNode* second = first->next;
    // 连接phead和d2节点
	phead->next = second;
	second->prev = phead;
    // 释放d1节点
	free(first);
	first = NULL;
}

1.8链表节点的数量

size_t ListSize(LTNode* phead)
{
	assert(phead);
	size_t n = 0;
	LTNode* cur = phead->next;
    
    // 当cur != phead，说明链表循环一周结束
	while (cur != phead)
	{
		++n;
		cur = cur->next;
	}
	return n;
}

1.9链表的查找

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	size_t n = 0;
    // 哨兵位没有存储数据，不需要进行查找
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
        // 迭代
		cur = cur->next;
	}
	return NULL;
}

1.10在pos位置之前插入

4.双向循环链表的模拟实现，双向循环链表的模拟实现详解第9张

// 在pos之前插入
// 也就是将prev newnode pos进行连接
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
    // 将pos前指针指向的节点，命名为prev
	LTNode* prev = pos->prev;
    // 创建一个新节点
	LTNode* newnode = BuyListNode(x);
	// 连接3个节点 prev newnode pos;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

头插

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
    //在phead->next之前插入，也就是头插
	ListInsert(phead->next, x);
}

尾插

4.双向循环链表的模拟实现，双向循环链表的模拟实现详解第10张

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
    //在phead之前插入，也就是尾插
    ListInsert(phead, x);
}

1.11删除pos位置

4.双向循环链表的模拟实现，双向循环链表的模拟实现详解第11张

void ListErase(LTNode* pos)
{
	assert(pos);
    // prev pos next
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
    
	// 连接prev和next，释放pos节点
	prev->next = next;
	next->prev = prev;
    
	free(pos);
    //需要调用的人自行置空，因为pos是传值拷贝，在这里将pos置空，主函数中的pos并没有被改变
	//pos = NULL; 
}

尾删

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
    
    //删除phead->prev也就是尾删
	ListErase(phead->prev); 
}

头删

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	
    // 删除phead->next也就是头删
	ListErase(phead->next);
}

1.12销毁链表

void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
        // 释放当前节点
		free(cur);
        
        // 迭代
		cur = next;
	}
    // 释放哨兵位
	free(phead);
    
    // 可以传二级，内部置空头结点
	// 建议：也可以考虑用一级指针，让调用ListDestory的人置空  （保持接口一致性）
	// phead = NULL;
}

2.双向循环链表的完整实现

List.h

#pragma once
#include 
#include 
#include 
#include 
// 双链表的节点的结构体
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
// 初始化一个双向循环链表
LTNode* ListInit();
// 销毁这个双向循环链表
void ListDestory(LTNode* phead);
// 打印链表
void ListPrint(LTNode* phead);
// 尾插
void ListPushBack(LTNode* phead, LTDataType x);
// 头插
void ListPushFront(LTNode* phead, LTDataType x);
// 尾删
void ListPopBack(LTNode* phead);
// 头删
void ListPopFront(LTNode* phead);
// 判断链表是否为空
bool ListEmpty(LTNode* phead);
// 链表的节点数量
size_t ListSize(LTNode* phead);
// 查找指定节点
LTNode* ListFind(LTNode* phead, LTDataType x);
// pos位置前插入节点
void ListInsert(LTNode* pos, LTDataType x);
// 删除pos位置的节点
void ListErase(LTNode* pos);

List.c

#include "List.h"
// 初始化，并返回哨兵位的地址
LTNode* ListInit()
{
	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
	if (guard == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	guard->next = guard;
	guard->prev = guard;
	return guard;
}
// 创建一个新节点
LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}
// 打印链表中的数据
void ListPrint(LTNode* phead)
{
	assert(phead);
	printf("phead");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead, x);
}
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	ListErase(phead->prev);
}
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	ListErase(phead->next);
}
bool ListEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
size_t ListSize(LTNode* phead)
{
	assert(phead);
	size_t n = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		++n;
		cur = cur->next;
	}
	return n;
}
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	size_t n = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
// 在pos之前插入
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	// prev newnode pos;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
// 删除pos位置
void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	//pos = NULL;
}
// 可以传二级，内部置空头结点
// 建议：也可以考虑用一级指针，让调用ListDestory的人置空  （保持接口一致性）
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

main.c

#define _CRT_SECURE_NO_WARNINGS
#include "List.h"
void TestList1()
{
	// 初始化链表
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	ListPushFront(plist, 10);
	ListPushFront(plist, 20);
	ListPushFront(plist, 30);
	ListPushFront(plist, 40);
	ListPrint(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	// 防止内存泄漏
	ListDestory(plist);
	plist = NULL;
}
void TestList2()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);
	ListDestory(plist);
	plist = NULL;
}
void TestList3()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	// ...
}
int main()
{
	TestList2();
	return 0;
}