当前位置：首页 > article >正文

初阶数据结构（C语言实现）——3.4带头双向循环链表详解（定义、增、删、查、改）

article 2025/3/11 20:06:17

1 带头双向循环链表的实现
3. 5 带头+双向+循环链表增删查改接口实现
- - 3.5.0 申请新结点
  - 3.5.1双向链表的初始化
  - 3.5.2双向链表销毁
  - 3.5.3 双向链表打印
  - 3.5.4 双向链表尾插
  - 3.5.5 双向链表尾删
  - 3.5.6 双向链表头插
  - 3.5.7 双向链表头删
  - 3.5.8 双向链表查找
  - 3.5.9 双向链表删除pos位置的结点
  - 3.5.10 双向链表在pos的前面进行插入
4.顺序表和链表的区别
附录：双向带头循环链表接口实现源代码
- 5.1 .h文件
- 5.2 .c文件
- 5.3 test.c文件

学习带头双向循环链表之前，建议先学习下顺序表，和单向不带头不循环链表。
这是博主之前的文章，欢迎学习交流
初阶数据结构（C语言实现）——3.1顺序表详解（初始化、增、删、查、改）
初阶数据结构（C语言实现）——3.3单向非循环链表详解（定义、增、删、查、改）

1 带头双向循环链表的实现

在VS2022中新建一个工程

List.h（带头双向循环链表的类型定义、接口函数声明、引用的头文件）
List.c（带头双向循环链表接口函数的实现）
Test.c（主函数、测试顺序表各个接口功能）

3. 5 带头+双向+循环链表增删查改接口实现

图示

特点

实现内容

typedef int LTDataType;
typedef struct HDLListNode
{
struct HDLListNode* next;
struct HDLListNode* prve;
LTDataType data;
}HDLListNode;

//双向链表的初始化
HDLListNode* HDLListInit();
//申请一个新结点
HDLListNode* BuyListNode(LTDataType x);
//链表销毁
void HDLLDestroy(HDLListNode* phead);
//双向链表的打印
void HDLListPrint(HDLListNode* phead);
//双向链表尾插
void HDLListPushBack(HDLListNode* phead, LTDataType x);
//双向链表尾删
void HDLListPopBack(HDLListNode* phead);
//双向链表头插
void HDLListPushFront(HDLListNode* phead, LTDataType x);
//双向链表头删
void HDLListPupFront(HDLListNode* phead);
//双向链表查找
HDLListNode* HDLListFind(HDLListNode* phead, LTDataType x);
//双向链表删除pos位置的结点
HDLListNode* HDLListErase(HDLListNode* pos);
// 双向链表在pos的前面进行插入
HDLListNode* HDLListInsert(HDLListNode* pos, LTDataType x);

3.5.0 申请新结点

申请新结点图解

申请新结点代码实现

HDLListNode* BuyListNode(LTDataType x)
{
	HDLListNode* newNode = (HDLListNode*)malloc(sizeof(HDLListNode)); //申请空间
	if (newNode == NULL)
	{
		perror("BuyListNode::malloc fail!"); //如果申请失败报错
		return NULL;//返回NULL
	}
	//对新申请的结点进行初始化
	newNode->next = NULL;
	newNode->prve = NULL;
	newNode->data = x;

	return newNode;//返回新结点
}

3.5.1双向链表的初始化

双向链表初始化图解

双向链表初始化代码实现

HDLListNode* HDLListInit()
{
	HDLListNode* phead = BuyListNode(-1);//申请新结点
	phead->next = phead;
	phead->prve = phead;
	
	return phead;//返回头结点
}

3.5.2双向链表销毁

双向链表销毁图解

双向链表销毁代码实现

void HDLLDestroy(HDLListNode* phead)
{
	assert(phead);
	HDLListNode* cur = phead->next;//让cur从带哨兵的头结点之后的第一个有效结点开始遍历
	while (cur!=phead)//遍历一遍链表，一个节点一个节点的释放
	{
		HDLListNode* next = cur->next;//记录cur的下一个结点
		free(cur);//释放结点
		cur = next;//cur往后走
	}
	free(phead);//最后释放哨兵头结点

}

3.5.3 双向链表打印

因为头结点不带有效数值，所以让cur指针不要指向头结点，指向头结点的下一个结点，然后遍历链表打印。下次到头的时候cur =phead。

双向链表打印代码实现

//双向链表的打印
void HDLListPrint(HDLListNode* phead)
{
	assert(phead);//断言，确保传入参数正确
	printf("<=head=>");
	HDLListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d=>", cur->data);
		cur = cur->next;//cur继续往后走
	}
	//最后全部打印完之后，换行。
	printf("\n");
}

3.5.4 双向链表尾插

图解尾插

双向链表的尾插代码实现

void HDLListPushBack(HDLListNode* phead, LTDataType x)
{
	assert(phead);

	HDLListNode* newnode = BuyListNode(x); //申请一个新结点
	HDLListNode* tail = phead->prve;//尾结点直接就能找到
	tail->next = newnode;//让尾结点指向要插入的结点
	newnode->next = phead;//让新插入的结点指向头结点
	phead->prve = newnode;//让头结点的prve指向新的尾结点

}

代码验证

在这里插入图片描述

3.5.5 双向链表尾删

尾删图解

尾删代码实现

bool isEmpty(HDLListNode* phead)
{
	assert(phead);
	//if (phead == NULL)
	//{
	//	return true;
	//}
	//else
	//{
	//	return false;
	//}
	//上面几行代码可以直接写成下面这一句
	return phead->next == phead; //如果相等就是true

}

void HDLListPopBack(HDLListNode* phead)
{
	assert(phead);//断言
	//还需要确定该链表非空
	assert(!isEmpty(phead));

	HDLListNode* tail = phead->prve;//找尾
	HDLListNode* tailPrve = tail->prve;//找到尾结点的前一个结点
	tailPrve->next = phead;//让新尾结点的next指向头结点
	phead->prve = tailPrve;//让头结点的peve指向新尾结点

	free(tail);//释放之前的尾结点
	tail = NULL;
}

尾删验证

在这里插入图片描述

3.5.6 双向链表头插

双向链表头插图解

方式1：有先后顺序必须先执行12，再执行34，如果不按顺序来，就找不到后面d1节点了


void HDLListPushFront(HDLListNode* phead, LTDataType x)
{
	assert(phead);
	HDLListNode* newnode = BuyListNode(x);//申请一个要插入的结点newnode
	//方式1 ：有先后顺序
	HDLListNode* cur = phead->next; //先找到要插入的结点位置 
	newnode->next = cur; //让新结点的next指向cur结点
	cur->prve = newnode;//让cur 的prve指向newnode
	phead->next = newnode;//让头结点的next指向新插入的newnode结点
	newnode->prve = phead;//让新插入的newnode结点的peve指向头结点
}

方式1验证

方式2，不需要有先后顺序，因为我们先找了一个first结点记录了下一个结点d1的位置

void HDLListPushFront(HDLListNode* phead, LTDataType x)
{
	assert(phead);
	HDLListNode* newnode = BuyListNode(x);//申请一个要插入的结点newnode
	//方式1 ：有先后顺序
	//HDLListNode* cur = phead->next; //先找到要插入的结点位置 
	//newnode->next = cur; //让新结点的next指向cur结点
	//cur->prve = newnode;//让cur 的prve指向newnode
	//phead->next = newnode;//让头结点的next指向新插入的newnode结点
	//newnode->prve = phead;//让新插入的newnode结点的peve指向头结点

	//方式2：先记录下要插入位置结点，不需要有先后顺序
	HDLListNode* first = phead->next; //记录下要插入结点位置first
	phead->next = newnode; //让头结点指向newnode
	newnode->prve = phead;//让newnode的prve 指向头结点
	newnode->next = first;//让newnode 的next指向first
	first->prve = newnode;//让first的peve指向newnode
}

方式2验证

3.5.7 双向链表头删

双向链表头删图解

双向链表头删代码实现

void HDLListPuopFront(HDLListNode* phead)
{
	assert(phead);//断言
	//还需要确定该链表非空
	assert(!isEmpty(phead));

	HDLListNode* delNode = phead->next;//找到要删除的结点
	HDLListNode* cur = delNode->next; //找到要删除节点的后一个结点cur
	phead->next = cur;//让头结点的next直接指向cur
	cur->prve = phead;//让cur的prve直接指向phead
	free(delNode);//释放要删除的结点
	delNode = NULL;
}

头删验证

在这里插入图片描述

3.5.8 双向链表查找

双向链表查找代码实现

HDLListNode* HDLListFind(HDLListNode* phead, LTDataType x)
{
	assert(phead);
	HDLListNode* cur = phead->next; //让cur结点从头结点的下一个结点位置出发，
	while (cur != phead)//遍历完整个链表，就是从头结点下一个结点出发再次回到头结点
	{
		while (cur->data == x)//如果查找到了
		{
			return cur;//返回查找到的结点
		}
		cur = cur->next; //cur一直往后遍历
	}
	return NULL;
}

双向链表查找验证

在这里插入图片描述

3.5.9 双向链表删除pos位置的结点

双向链表删除pos位置的结点图解

双向链表删除pos位置的结点代码实现

HDLListNode* HDLListErase(HDLListNode* pos)
{
	assert(pos);

	HDLListNode* posPrve = pos->prve;//找到pos的前一个结点
	HDLListNode* posNext = pos->next;//找到pos的后一个结点
	
	posPrve->next = posNext;//让前一个结点的next直接指向pos的后一个结点
	posNext->prve = posPrve;//让后一个结点的prve直接指向pos的前一个结点

	free(pos);//释放pos结点
}

双向链表删除pos位置的结点，功能验证

void test()
{
    HDLListNode* plist = HDLListInit();
    HDLListPushBack(plist, 1);
    HDLListPushBack(plist, 2);
    HDLListPushBack(plist, 3);
    HDLListPushBack(plist, 4);
    HDLListPrint(plist);
    HDLListNode* pos = HDLListFind(plist, 2);
    if (pos)
    {
        HDLListErase(pos);
        pos = NULL;
    }
    HDLListPrint(plist);
}
int main()
{
    test();
    return 0;
}

实现了这个函数，我们的尾删直接调用这个函数就行，删除phead->prve

void HDLListPopBack(HDLListNode* phead)
{
	assert(phead);//断言
	//还需要确定该链表非空
	assert(!isEmpty(phead));
	HDLListErase(phead->prve);
}

在这里插入图片描述

实现了这个函数，我们的头删也可以直接调用这个函数，删除phead->next

void HDLListPopFront(HDLListNode* phead)
{
	assert(phead);//断言
	//还需要确定该链表非空
	assert(!isEmpty(phead));
	HDLListErase(phead->next);
}

在这里插入图片描述

3.5.10 双向链表在pos的前面进行插入

双向链表在pos的前面进行插入代码实现

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* prve = pos->prve;
	LTNode* newNode = BuyListNode(x);

	prve->next = newNode;
	newNode->prve = prve;

	newNode->next = pos;
	pos->prve = newNode;
}

双向链表在pos的前面进行插入功能验证

在这里插入图片描述

实现了这个函数，我们的头插直接调用这个函数就行，插入到phead->next位置

void HDLListPushFront(HDLListNode* phead, LTDataType x)
{
	assert(phead);
	HDLListInsert(phead->next, x);
}

在这里插入图片描述

尾插入同理，插入到phead位置

void HDLListPushBack(HDLListNode* phead, LTDataType x)
{
	assert(phead);
	HDLListInsert(phead, x);
}

在这里插入图片描述

4.顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

附录：双向带头循环链表接口实现源代码

5.1 .h文件

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


typedef int LTDataType;
typedef struct HDLListNode
{
	struct HDLListNode* next;
	struct HDLListNode* prve;
	LTDataType data;
}HDLListNode;

//双向链表的初始化
HDLListNode* HDLListInit();
//申请一个新结点
HDLListNode* BuyListNode(LTDataType x);
//链表销毁
void HDLLDestroy(HDLListNode* phead);
//双向链表的打印
void HDLListPrint(HDLListNode* phead);
//双向链表尾插
void HDLListPushBack(HDLListNode* phead, LTDataType x);
//双向链表尾删
void HDLListPopBack(HDLListNode* phead);
//双向链表头插
void HDLListPushFront(HDLListNode* phead, LTDataType x);
//双向链表头删
void HDLListPupFront(HDLListNode* phead);
//双向链表查找
HDLListNode* HDLListFind(HDLListNode* phead, LTDataType x);
//双向链表删除pos位置的结点
HDLListNode* HDLListErase(HDLListNode* pos);
// 双向链表在pos的前面进行插入
HDLListNode* HDLListInsert(HDLListNode* pos, LTDataType x);

5.2 .c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"HDLList20250307.h"

HDLListNode* BuyListNode(LTDataType x)
{
	HDLListNode* newNode = (HDLListNode*)malloc(sizeof(HDLListNode)); //申请空间
	if (newNode == NULL)
	{
		perror("BuyListNode::malloc fail!"); //如果申请失败报错
		return NULL;//返回NULL
	}
	//对新申请的结点进行初始化
	newNode->next = newNode;
	newNode->prve = newNode;
	newNode->data = x;

	return newNode;//返回新结点
}

HDLListNode* HDLListInit()
{
	HDLListNode* phead = BuyListNode(-1);//申请新结点
	phead->next = phead;
	phead->prve = phead;
	
	return phead;//返回头结点
}


void HDLLDestroy(HDLListNode* phead)
{
	assert(phead);
	HDLListNode* cur = phead->next;//让cur从带哨兵的头结点之后的第一个有效结点开始遍历
	while (cur!=phead)//遍历一遍链表，一个节点一个节点的释放
	{
		HDLListNode* next = cur->next;//记录cur的下一个结点
		free(cur);//释放结点
		cur = next;//cur往后走
	}
	free(phead);//最后是否哨兵头结点

}
//双向链表的打印
void HDLListPrint(HDLListNode* phead)
{
	assert(phead);//断言，确保传入参数正确
	printf("<=head=>");
	HDLListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d=>", cur->data);
		cur = cur->next;//cur继续往后走
	}
	//最后全部打印完之后，换行。
	printf("\n");
}
void HDLListPushBack(HDLListNode* phead, LTDataType x)
{
	assert(phead);

	HDLListNode* newnode = BuyListNode(x); //申请一个新结点
	HDLListNode* tail = phead->prve;//尾结点直接就能找到
	tail->next = newnode;//让尾结点指向要插入的结点
	newnode->prve = tail;//让新插入发结点的prve指向之前的尾结点
	newnode->next = phead;//让新插入的结点的next指向头结点
	phead->prve = newnode;//让头结点的prve指向新的尾结点

    //HDLListInsert(phead, x);
}

bool isEmpty(HDLListNode* phead)
{
	assert(phead);
	//if (phead == NULL)
	//{
	//	return true;
	//}
	//else
	//{
	//	return false;
	//}
	//上面几行代码可以直接写成下面这一句
	return phead->next == phead; //如果相等就是true

}

void HDLListPopBack(HDLListNode* phead)
{
	assert(phead);//断言
	//还需要确定该链表非空
	assert(!isEmpty(phead));
	HDLListNode* tail = phead->prve;//找尾
	HDLListNode* tailPrve = tail->prve;//找到尾结点的前一个结点
	tailPrve->next = phead;//让新尾结点的next指向头结点
	phead->prve = tailPrve;//让头结点的peve指向新尾结点

	free(tail);//释放之前的尾结点
	tail = NULL;
		//HDLListErase(phead->prve);
}

void HDLListPushFront(HDLListNode* phead, LTDataType x)
{
	assert(phead);
	HDLListInsert(phead->next, x);
	//HDLListNode* newnode = BuyListNode(x);//申请一个要插入的结点newnode
	//方式1 ：有先后顺序
	//HDLListNode* cur = phead->next; //先找到要插入的结点位置 
	//newnode->next = cur; //让新结点的next指向cur结点
	//cur->prve = newnode;//让cur 的prve指向newnode
	//phead->next = newnode;//让头结点的next指向新插入的newnode结点
	//newnode->prve = phead;//让新插入的newnode结点的peve指向头结点
	//方式2：先记录下要插入位置结点，不需要有先后顺序
	//HDLListNode* first = phead->next; //记录下要插入结点位置first
	//phead->next = newnode; //让头结点指向newnode
	//newnode->prve = phead;//让newnode的prve 指向头结点
	//newnode->next = first;//让newnode 的next指向first
	//first->prve = newnode;//让first的peve指向newnode
}

void HDLListPopFront(HDLListNode* phead)
{
	assert(phead);//断言
	//还需要确定该链表非空
	assert(!isEmpty(phead));
	HDLListNode* delNode = phead->next;//找到要删除的结点
	HDLListNode* cur = delNode->next; //找到要删除节点的后一个结点cur
	phead->next = cur;//让头结点的next直接指向cur
	cur->prve = phead;//让cur的prve直接指向phead
	free(delNode);//释放要删除的结点
	delNode = NULL;

	//HDLListErase(phead->next);
}

HDLListNode* HDLListFind(HDLListNode* phead, LTDataType x)
{
	assert(phead);
	HDLListNode* cur = phead->next; //让cur结点从头结点的下一个结点位置出发，
	while (cur != phead)//遍历完整个链表，就是从头结点下一个结点出发再次回到头结点
	{
		while (cur->data == x)//如果查找到了
		{
			return cur;//返回查找到的结点
		}
		cur = cur->next; //cur一直往后遍历
	}
	return NULL;
}

HDLListNode* HDLListErase(HDLListNode* pos)
{
	assert(pos);

	HDLListNode* posPrve = pos->prve;//找到pos的前一个结点
	HDLListNode* posNext = pos->next;//找到pos的后一个结点
	
	posPrve->next = posNext;//让前一个结点的next直接指向pos的后一个结点
	posNext->prve = posPrve;//让后一个结点的prve直接指向pos的前一个结点

	free(pos);//释放pos结点
}

HDLListNode* HDLListInsert(HDLListNode* pos, LTDataType x)
{
	assert(pos);
	HDLListNode* newnode = BuyListNode(x);//申请一个新结点
	HDLListNode* posPrve = pos->prve;//找到pos的前一个位置posPrve

	posPrve->next = newnode;//posPrve的next直接指向新结点newnode
	newnode->prve = posPrve;//让newnode的prve指向posPrve

	newnode->next = pos;//让newnode的next指向pos
	pos->prve = newnode;//让pos的prve指向newnode
}

5.3 test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"HDLList20250307.h"
void test()
{
    HDLListNode* plist = HDLListInit();
    HDLListPushBack(plist, 1);
    HDLListPushBack(plist, 2);
    HDLListPushBack(plist, 3);
    HDLListPushBack(plist, 4);
    HDLListPrint(plist);
  /*  HDLListPopBack(plist);*/
    HDLListPopFront(plist);
    HDLListPrint(plist);
    //HDLListPushFront(plist, 5);
    //HDLListPushFront(plist, 6);
    //HDLListPrint(plist);

    //HDLListPrint(plist);
    //HDLListNode* ret = HDLListFind(plist, 2);
    //ret->data *=2;
    //HDLListPrint(plist);
    //HDLListNode* pos = HDLListFind(plist, 2);
    //if (pos)
    //{
    //    HDLListErase(pos);
    //    pos = NULL;
    //}
    //HDLListPrint(plist);
    //HDLListNode* pos = HDLListFind(plist, 2);
    //if (pos)
    //{
    //    HDLListInsert(pos,7);
    //    pos = NULL;
    //}
    //HDLListPrint(plist);
}
int main()
{
    test();
    return 0;
}