链表效率不高？ 来看双向循环链表再下定论吧

前言：
本文重点实现双向循环链表功能的实现以及讲解
喜欢的老铁留下您宝贵的三连！

文章目录

• 双向循环链表图样
• 创建新节点
• 初始化链表
• 链表的打印
• 头插步骤样例和代码
• 头删步骤样例和代码
• 尾插步骤样例和代码
• 尾删步骤样例和代码
• 在pos的前面进行插入代码
• 查找pos位置
• 删除pos位置的节点代码
• 重点（面试官让你十分钟写成链表的秘诀）
• • 头插的优化
  • 头删的优化
  • 尾插的优化
  • 尾删的优化
• 链表销毁
• 完整代码：
• • 头文件
  • 函数

双向循环链表图样

创建新节点

ListNode* ListBuyNode(LTDataType x)//创建新节点
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

初始化链表

ListNode* ListInit(ListNode* phead)//初始化
{
	ListNode* newNode=ListBuyNode(-1);//创建一个哨兵位
	newNode->next = newNode;
	newNode->prev = newNode;
	return newNode;
}

链表的打印

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

头插步骤样例和代码

代码：

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newNode = ListBuyNode(x);
	ListNode* cur = phead->next;
	phead->next = newNode;
	newNode->next = cur;
	cur->prev = newNode;
	newNode->prev = phead;
}

头删步骤样例和代码

代码：

void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* cur = phead->next;
	phead->next = cur->next;
	cur->next->prev = phead;
	free(cur);
}

尾插步骤样例和代码

通过head->prev找到tail
代码：

void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newNode = ListBuyNode(x);
	ListNode* tail = phead->prev;
	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = phead;
	phead->prev = newNode;
}

尾删步骤样例和代码

通过head->prev找到tail，通过tail->prev找到prev

代码:

void ListPopBack(ListNode* phead) 
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* tail = phead->prev;
	tail->prev->next = phead;
	phead->prev = tail->prev;
	free(tail);
}

在pos的前面进行插入代码

弄懂了头插和尾插，这就很简单就能实现了，直接看代码吧！！

代码：

void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newNode = ListBuyNode(x);
	ListNode* cur = pos->prev;
	cur->next = newNode;
	newNode->next = pos;
	pos->prev = newNode;
	newNode->prev = cur;
}

查找pos位置

ListNode* ListFind(ListNode* phead, LTDataType x) 
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

删除pos位置的节点代码

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}

重点（面试官让你十分钟写成链表的秘诀） 头插的优化

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

头删的优化

void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListErase(phead->next);
}

尾插的优化

void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead, x);
}

尾删的优化

void ListPopBack(ListNode* phead) 
{
	assert(phead);
	assert(phead->next != phead);
	ListErase(phead->prev);
}

链表销毁

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

完整代码： 头文件

#pragma once
#include
#include
#include
typedef  int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

ListNode* ListBuyNode(LTDataType x);//创建新节点
ListNode* ListInit(ListNode* phead);//初始化
// 双向链表销毁
void ListDestory(ListNode* phead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

函数

#define _CRT_SECURE_NO_WARNINGS
#include"ListNode.h"

ListNode* ListBuyNode(LTDataType x)//创建新节点
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}
ListNode* ListInit(ListNode* phead)//初始化
{
	ListNode* newNode=ListBuyNode(-1);//创建一个哨兵位
	newNode->next = newNode;
	newNode->prev = newNode;
	return newNode;
}
// 双向链表打印
void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	//ListNode* newNode = ListBuyNode(x);
	//ListNode* tail = phead->prev;
	//tail->next = newNode;
	//newNode->prev = tail;
	//newNode->next = phead;
	//phead->prev = newNode;
	ListInsert(phead, x);
}
// 双向链表尾删
void ListPopBack(ListNode* phead) 
{
	assert(phead);
	assert(phead->next != phead);
	//ListNode* tail = phead->prev;
	//tail->prev->next = phead;
	//phead->prev = tail->prev;
	//free(tail);
	ListErase(phead->prev);
}
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	//ListNode* newNode = ListBuyNode(x);
	//ListNode* cur = phead->next;
	//phead->next = newNode;
	//newNode->next = cur;
	//cur->prev = newNode;
	//newNode->prev = phead;
	ListInsert(phead->next, x);

}

// 双向链表头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	//ListNode* cur = phead->next;
	//phead->next = cur->next;
	//cur->next->prev = phead;
	//free(cur);
	ListErase(phead->next);


}
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x) 
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newNode = ListBuyNode(x);
	ListNode* cur = pos->prev;
	cur->next = newNode;
	newNode->next = pos;
	pos->prev = newNode;
	newNode->prev = cur;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}
// 双向链表销毁
void ListDestory(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}