【数据结构】手写双链表【纯C语言版】

2023-10-16 21:03:04

摘要：本章主要讲述循环双链表的实现

文章目录

本章导读

  本章我并不会把代码的实现逻辑详细的描述出来，如果大家看了之前的文章或是自己写过单链表，那么你将会对本文中关于循环双链表的实现手到擒来；如果大家对其中的一些逻辑不够清楚可以自己画图理解，这里我只会画两个图出来作为示范，其他的大家可以自己画，画图真的很重要很重要！

1. 循环双链表的逻辑结构

  这里我以带头结点的循环双链表作为示例：
【数据结构】手写双链表【纯C语言版】
  每个结点都有一个数据域和两个指针域，prev指向该节点的前一个元素，next指向该结点的下一结点，每两个结点之间的连接是双向的，所以我们可以通过任一结点找到该结点的直接前驱和直接后继；值得留意的是，头结点的prev指向尾结点，尾结点的next域指向头结点，这样就形参了循环链表。

2. 循环双链表的代码实现

2.1 定义循环双链表的存储结构

// 定义链表数据域的类型
typedef int LTDataType;

// 定义链表类型
typedef struct ListNode
{
	struct ListNode* prev; // 指向前一个结点，即指向直接前驱结点
	struct ListNode* next; // 指向下一个结点，即指向直接后继结点
	LTDataType data; // 数据域
} ListNode;

2.2 创建结点

// 新建结点
ListNode* BuyListNode(LTDataType* data)
{
	if (!data)
	{
		printf("数据域不能为空\n");
		return NULL;
	}

	// 创建新结点
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	// 判空
	if (!newNode)
	{
		perror("开辟空间失败");
		return NULL;
	}

	// 插入数据
	newNode->data = *data;
	// next指向空
	newNode->next = NULL;
	// prev指向空
	newNode->prev = NULL;

	return newNode;

}

2.2 初始化头结点

  当循环双链表中只有一个结点即头结点时，头结点的prev域和next域都是指向自己的。

void ListInit(ListNode** pphead)
{
	int a = 10;
	// 创建新结点
	ListNode* newNode = BuyListNode(&a);
	// 自己指向自己
	newNode->next = newNode;
	newNode->prev = newNode;
	*pphead = newNode;
}

2.3 计算链表长度

  计算循环双链表长度时，我们将链表一直变量，那么问题来了，带头结点循环双链表只要不为空，那么它就永远有指向，我们的循环终止条件是应该是什么呢？很简单，当前结点为头结点时就表示已经把双链表遍历了。

// 计算双链表长度，头结点不算在内
size_t ListSize(ListNode* phead)
{
	// 记录当前结点
	ListNode* cur = phead->next;
	// 记录长度
	size_t size = 0;
	// 如果当前结点不是头结点
	while ( cur != phead )
	{
		cur = cur->next;
		size ++;
	}
	return size;
}

2.4 尾插法

【数据结构】手写双链表【纯C语言版】

void ListPushBack(ListNode* phead, LTDataType* data)
{
	assert(phead);

	// 创建新结点
	ListNode* newNode = BuyListNode(data);
	// 保存尾结点
	ListNode* tail = phead->prev;
	// 尾结点的next指向新结点
	tail->next = newNode;
	// 新结点的prev指向尾结点
	newNode->prev = tail;
	// 新结点的next指向头结点
	newNode->next = phead;
	// 头结点的prev指向新结点
	phead->prev = newNode;
	// 完成插入
}

2.5 尾删法

【数据结构】手写双链表【纯C语言版】

// 尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	// 如果链表为空则中断
	assert(phead->next != phead);

	// 计算链表长度
	size_t size = ListSize(phead);
	// size小于1表示链表中只有头结点
	if (size < 1)
	{
		printf("链表中没有结点\n");
		exit(-1);
	}

	// 保存尾结点
	ListNode* tail = phead->prev;
	// 保存尾结点的前一个结点
	ListNode* tailPrev = tail->prev;

	tailPrev->next = phead;
	phead->prev = tail->prev;
	free(tail);
	tail = NULL;
}

2.6 打印链表

void ListPrint(ListNode* phead)
{
	assert(phead);

	// 记录当前结点
	ListNode* cur = phead->next;
	while ( cur != phead)
	{
		printf("%p\t%d\t%p\t%p\n", cur->prev, cur->data, cur->next, cur);
		cur = cur->next;
	}
}

2.7 头插法

// 头插
void ListPushFront(ListNode* phead, LTDataType* data)
{
	// 创建新结点
	ListNode* newNode = BuyListNode(data);
	
	// 方法一，此方法以下代码的顺序不能乱，否则不能实现头插
	/*newNode->prev = phead;
	newNode->next = phead->next;
	phead->next->prev = newNode;
	phead->next = newNode;*/

	// 方法二：此方法的代码顺序可以改变
	ListNode* pheadNext = phead->next;
	phead->next = newNode;
	newNode->prev = phead;
	pheadNext->prev = newNode;
	newNode->next = pheadNext;

}

2.8 头删法

// 头删
void ListPopFront(ListNode* phead)
{
	// 头结点不能为空
	assert(phead);
	// 计算链表长度
	assert(phead->next != phead);

	// 方法一,以下代码顺序可以打乱
	ListNode* target = phead->next;
	ListNode* targetNext = target->next;
	phead->next = targetNext;
	targetNext->prev = phead;
	free(target);

	// 方法二，以下代码顺序不能打乱
	/*phead->next = phead->next->next;
	free(phead->next->prev);
	phead->next->prev = phead;*/
}

2.9 查找具有指定数据的结点

// 查找具有指定数据域的结点,并返回结点的指针
ListNode* ListFind(ListNode* phead, LTDataType* data)
{
	assert(phead);
	assert(phead->next != NULL);

	ListNode* cur = phead->next;

	while (cur != phead)
	{
		if (cur->data == *data) return cur;
		cur = cur->next;
	}

	return NULL;

}

2.10 查找指定位置的结点

// 查找位置的结点，pos取值为[0,size-1]
ListNode* ListFindByPos(ListNode* phead, size_t pos)
{
	assert(phead);
	// 如果只有头结点则中断
	assert(phead->next != phead);
	// 计算当前链表长度
	size_t size = ListSize(phead);
	assert(pos < size);

	// 用于记录位置为pos的结点
	ListNode* posNode = phead->next;
	
	for (int i = 0; i < pos; i++)
	{
		posNode = posNode->next;
	}

	return posNode;
}

2.11 在任意结点前插入结点

// 在任意结点target前插入新结点
void ListInsert(ListNode* target, LTDataType* data)
{
	assert(target);

	
	ListNode* targetPrev = target->prev;
	// 创建新结点
	ListNode* newNode = BuyListNode(data);
	
	targetPrev->next = newNode;
	newNode->prev = targetPrev;
	newNode->next = target;
	target->prev = newNode;
}

2.12 查找指定结点

// 查找链表中是否具有指定结点，有返回该结点，没有返回NULL
ListNode* ListIsExistNode(ListNode* phead, ListNode* target)
{
	assert(phead && target);
	assert(phead->next != phead);

	ListNode* cur = phead->next;
	while (cur && (cur != phead))
	{
		if (cur == target) return cur;
		cur = cur->next;
	}
	return NULL;
}

2.13 删除指定结点

// 删除指定结点
void ListErase(ListNode* target)
{
	assert(target);

	ListNode* targetPrev = target->prev;
	ListNode* targetNext = target->next;

	targetPrev->next = targetNext;
	targetNext->prev = targetPrev;
	free(target);
}

2.14 清空链表

// 清空链表,保留头结点
void ListClear(ListNode* phead)
{
	assert(phead && phead->next != phead);

	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	phead->next = phead;
	phead->prev = phead;
}

2.15 释放链表

// 释放链表，包括头结点
void ListDestory(ListNode** pphead)
{
	assert(*pphead);
	// 清空链表内存
	ListClear(*pphead);
	// 释放头
	free(*pphead);
	// 将链表置为空
	*pphead = NULL;
}

3. 源码链接

点击查看源码

【文件说明】

文件名 说明
SList.h 链表的类型定义和函数声明
SList.c 具体函数的实现
test.c 测试代码

后记

我水平有限，错误难免，还望各位加以指正。

关于双链表的内容到此结束，感谢您的阅读！！！如果内容对你有帮助的话，记得给我三连丫（点赞、收藏、关注）

本人博客所有文章，均为原创。部分文章中或引用相关资料，但均已著明来源出处。可随意转载、分享，但需加本文链接，以及版权说明。

上一篇：剑指offer编程题Java实现——面试题7相关题用两个队列实现一个栈


下一篇：Java_手工实现HashMap