带头双向循环链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了带头双向循环链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言：当我们想要挪动大量数据的时候，单链表的效率就很低了，比如尾插，要找到尾，通过遍历的时间复杂度最坏情况是O(N),所以我们引进结构复杂但效率高的双向带头循环链表

带头双向循环链表

带头双向循环链表指得是什么呢？就是既存储了上一个节点的地址，又存储了下一个节点的地址，带有哨兵位，加上哨兵位的头指向了链表的尾，链表的尾的下一个指向了哨兵位的头
带头双向循环链表,链表,数据结构

定义

和单链表一样，有指针域和数据域，不过比单链表多了一个存储上一个节点的指针

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

双向链表的功能

和单链表大差不差

头插
尾插
头删
尾删
找到某个位置的下标
在任意位置插入
删除任意位置的数据
销毁链表

标明：我们先实现每个函数的接口，插入和删除用这两个函数(在任意位置插入
，删除任意位置的数据)复用效率会快好多

双向链表的功能实现

初始化

初始化需要传二级指针，因为初始化需要改变结构体指针，也就是要对头进行初始化，让头指向自己，如果传一级，就相当于传值调用，形参的改变并不会影响实参，而后面的函数接口都不用二级，因为改变的是结构体，也就是“箭头”的指向
注：你可以返回结构体指针，也可以传二级指针，我们这里采用的是返回结构体指针

代码实现

ListNode* ListInit()
{
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

创建新节点

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

打印链表

代码实现

void ListPrint(ListNode* phead)
{
	assert(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 = BuyListNode(x);
	ListNode* next = phead->next;
	phead->next = newNode;
	newNode->prev = phead;
	newNode->next = next;
	next->prev = newNode;
}

尾插

先定义一个尾指针，使代码清晰易懂，不用像单链表一样考虑一个节点，两个节点，多个节点的问题
带头双向循环链表,链表,数据结构

代码实现

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


}

头删

当删到只剩哨兵位的话就不能删了

代码实现

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

尾删

删到最后只剩哨兵位，就不要删了，链表为空，再去解引用就会报错

代码实现

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

销毁链表

循环结束的条件是当遍历到等于哨兵位时，说明已经销毁完数据了，再把哨兵位free掉就好

代码实现

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

查找下标

代码实现

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;

}

在任意位置之前插入数据

带头双向循环链表,链表,数据结构

代码实现

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

删除任意位置的数据

带头双向循环链表,链表,数据结构文章来源地址https://www.toymoban.com/news/detail-856560.html

代码实现

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

源码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
ListNode*  ListInit();
void ListPushBack(ListNode* phead, LTDataType x);
void ListPrint(ListNode* phead);
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);
void ListPushFront(ListNode* phead,LTDataType x);
ListNode* ListFind(ListNode* phead, LTDataType x);
void ListInsert(ListNode* pos, LTDataType x);
void ListErase(ListNode* pos);
void ListDestroy(ListNode* phead);

List.c

#define  _CRT_SECURE_NO_WARNINGS
#include"List.h"
ListNode* ListInit()
{
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	phead->prev = phead;
	phead->next = phead;
	return phead;
}
ListNode* BuyListNode(LTDataType x)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}
void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newNode = BuyListNode(x);
	ListNode* tail = phead->prev;
	newNode->prev = tail;
	tail->next = newNode;
	newNode->next = phead;
	phead->prev = newNode;
	也处理了空链表的问题，不用像单链表一样考虑一个节点，两个节点，多个节点的问题
	//ListInsert(phead, x);

}
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//删到最后只剩哨兵位，就不要删了，链表为空，再去解引用就会报错
	/*ListNode* tail = phead->prev;
	ListNode* tailprev = tail->prev;
	free(tail);
	phead->prev = tailprev;
	tailprev->next = phead;*/
	ListErase(phead->prev);
}

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newNode = BuyListNode(x);
	ListNode* next = phead->next;
	phead->next = newNode;
	newNode->prev = phead;
	newNode->next = next;
	next->prev = newNode;
	//ListInsert(phead->next, x);
}
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
	ListNode* nextNext = next->next;
	phead->next = nextNext;
	nextNext->prev = phead;
	free(next);
	//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 = BuyListNode(x);
	ListNode* posPrev = pos->prev;
	posPrev->next = newNode;
	newNode->prev = posPrev;
	newNode->next = pos;
	pos->prev = newNode;
}
void ListErase(ListNode* pos) 
{
	assert(pos);
	ListNode* posPre = pos->prev;
	ListNode* posNext = pos->next;
	posPre->next = posNext;
	posNext->prev = posPre;
	free(pos);
	pos = NULL;
}
void ListDestroy(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur->next != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

test.c

#define  _CRT_SECURE_NO_WARNINGS
#include"List.h"
void test2()
{
	
	ListNode* plist = ListInit();
	//尾插
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);
	//头插
	ListPushFront(plist, 10);
	ListPushFront(plist, 18);
	ListPushFront(plist, 17);
	ListPushFront(plist, 16);
	ListPushFront(plist, 15);
	ListPrint(plist);
/*
	//在pos位置前插入
	ListNode* pos1 = ListFind(plist, 3);
	if(pos1)
	{
	ListInsert(pos1,30);
	}
	ListPrint(plist);
*/
	
/*	//删除pos位置的数据
	ListNode* pos = ListFind(plist, 2);
	if(pos)
	{
	ListErase(pos);
	}
	ListPrint(plist);
*/
	头删
	//ListPopFront(plist);
	//ListPopFront(plist);
	//ListPrint(plist);
	尾删
	//ListPopBack(plist);
	//ListPrint(plist);
	//ListPopBack(plist);
	//ListPrint(plist);
	//销毁
	ListDestroy(plist);
	plist = NULL;

}
int main()
{
	//test1();
	test2();
	return 0;
}