1. AI技术聚合首页
  2. IT

链表基础知识（二、双向链表头插、尾插、头删、尾删、查找、删除、插入）

心中带点小风骚 • • IT • 阅读 52

目录

书接上文：

链表基础知识（一、单链表、头插、尾插、头删、尾删、查找、删除、插入）-CSDN博客

一、双向链表的概念

双向链表，即一个节点中有两个指针域，一个存放当前节点前一个节点的地址，另一个存放当前节点后一个节点的地址。

（STL中list就是这个结构）

双链表的节点：

二、 双向链表的优缺点分析​与对比

 2.1双向链表特点：

       1.每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 实现起来要困难一些
  2.相对于单向链表, 必然占用内存空间更大一些.
  3.既可以从头遍历到尾, 又可以从尾遍历到头

2.2双链表的优劣：

2.3循环链表的优劣

循环表的好处主要包括以下几点：

  • 灵活性：循环链表可以从任何一个节点开始遍历，而且任何节点都可以作为头节点。这种灵活性使得循环链表在处理某些问题时比其他类型的链表更有优势。

  • 简化操作：在循环链表中，插入和删除操作相对简便，不需要对头尾节点

  • 行特殊处理。这种简便性可以提高算法的效率，降低编程的复杂性。

  • 适用于循环问题：循环链表可以实现循环访问，因此特别适用于解决涉及到循环问题的场景。

  • 便于实现队列数据结构：使用循环链表来实现队列数据结构可以简化操作，只需要维护一个尾节点指针即可，因为尾节点的后向节点就是队头节点。

  • 方便操作系统管理和应用程序运行：循环链表在操作系统和应用程序中也有广泛的应用。例如，操作系统可以利用循环链表来管理多个应用程序，通过循环遍历来给每个应用程序分配执行时间。

  • 可用于实现高级数据结构：循环双向链表可以用于实现高级数据结构，例如斐波那契堆(Fibonacci Heap)，从而扩展了其在复杂算法和数据结构中的应用范围。

循环链表的缺点主要包括：

  • 内存占用更多：相比单链表，循环链表需要更多的内存空间来存储链接信息。这是因为循环链表中的每个节点都需要指向下一个节点，形成一个闭环，从而增加了内存开销。

  • 代码复杂度提高：循环链表的代码实现相比单链表要复杂一些。在插入、删除节点或遍历链表时，需要特别注意处理边界条件和循环结构，这可能会增加开发和调试的难度。

  • 潜在的死循环风险：如果循环链表中的链接关系出现错误，可能会导致死循环的情况发生。例如，在插入或删除节点时，如果没有正确更新链接关系，就可能导致链表无法正确遍历或陷入无限循环中。

2.4 顺序表和链表的优缺点分析​

三、带头双向循环链表增删改查实现

结构复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3.1SList.c

#pragma once
#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>


typedef int LTDataType;
//带哨兵位的头节点，第一个节点不存储有效数据，不能存储链表的长度
//typedef char LTDataType;
//typedef double LTDataType;无法存储链表长度


//Slist  双向链表
//DList  单链表
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}ListNode;

ListNode* ListInit();
void ListDestory(ListNode* phead);
void ListPrint(ListNode* phead);

void ListPushBack(ListNode* phead, LTDataType x);
void ListPushFront(ListNode* phead, LTDataType x);
void ListPopFront(ListNode* phead);
void ListPopBack(ListNode* phead);

ListNode* ListFind(ListNode* phead, LTDataType x);
// pos位置之前插入x
void ListInsert(ListNode* pos, LTDataType x);
// 删除pos位置的值
void ListErase(ListNode* pos);

//bool ListEmpty(ListNode* phead);
//int ListSize(ListNode* phead);//链表的长度

3.2创建一个新节点、头节点

ListNode* BuyListNode(LTDataType x)
//创建一个新节点
{
	ListNode* newnode = malloc(sizeof(ListNode));
	//malloc分配大小,是一个ListNode结构体的大小
	newnode->data = x;//将新节点的data字段设置为参数x的值
	newnode->next = NULL;//给新节点的next存储的地址置空
	newnode->prev = NULL;//给新节点的prev存储的地址置空

	return newnode;
}
ListNode* ListInit()
//创建头节点
{
	ListNode* phead = BuyListNode(0);//phead指向了这个新创建的节点
	phead->next = phead; // 将phead的 next 指向其自身
	phead->prev = phead; // 将phead的 prev 指向其自身

	return phead;//返回phead,即头节点
}

3.3头插

在头节点后插入

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);//此节点不为空

	//顺序不能换
	ListNode* newnode = BuyListNode(x);
	newnode->next = phead->next;//存储phead的next,即下一个节点
	phead->next->prev = newnode;//下一个节点的prev指向newnode

	phead->next = newnode;//下一个节点的next 指向 newnode
	newnode->prev = phead;//newnode的prev 指向 phead
}

3.4尾插

在头节点前插入

void ListPushBack(ListNode* phead, LTDataType x)
//x = 0,尾插
{
	assert(phead);//phead不为空
	ListNode* tail = phead->prev;//tail存储phead的prev中的地址,即最后一个节点
	ListNode* newnode = BuyListNode(x);//创建一个新节点
	
	tail->next = newnode;//上一个节点的next指向新节点
	newnode->prev = tail;//新节点的prev指向phead
	newnode->next = phead;//新节点的next指向phead
	phead->prev = newnode;//上一个节点的prev指向新节点
}

3.5头删

在头结点后删除

void ListPopFront(ListNode* phead)
{
	assert(phead);//phead不为空
	assert(phead->next != phead);

	ListNode* first = phead->next;//先first存储phead的next中的地址,即phead的下一个节点
	ListNode* second = first->next;//再second存储下一个的节点的next中的地址,即下下个节点
	phead->next = second;//phead的next指向下下一个节点
	second->prev = phead;//下下一个节点的prev指向phead

	free(first);//下一个节点的空间被释放
	first = NULL;//first置空
}

3.6尾删

在头节点前删除

void ListPopBack(ListNode* phead)
{
	assert(phead);//此节点不为空
	assert(phead->next != phead);

	ListNode* tail = phead->prev;//先tail存储phead的prev中的地址,即上一个节点
	ListNode* prev = tail->prev;//prev存储上一个节点的prev中的地址,即上上一个节点

	prev->next = phead;//上上个节点的next指向phead
	phead->prev = prev;//phead的prev指向上上个节点

	free(tail);//释放tail存储的空间,即上个节点的空间
	tail = NULL;//tail置空
	
}

3.7查找

ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);//此节点不为空
	ListNode* cur = phead->next;//cur存储phead的next中的地址,即下一个节点
	while (cur != phead)//不是头节点
	{
		if (cur->data == x)//如果是要查找的地址
		{
			return cur;//找到了返回这个地址
		}

		cur = cur->next;//指向下一个节点
	}

	return NULL;//没有找到,返回空
}

3.8删除

// 删除pos位置的值
void ListErase(ListNode* pos)
{
	assert(pos);//此节点不为空

	ListNode* prev = pos->prev;//prev存储pos的prev中的地址,即上一个节点
	ListNode* next = pos->next;//next存储pos的next中的地址,即下一个节点
	prev->next = next;//上一个节点的next指向pos的next,即下一个节点
	next->prev = prev;//下一个节点的prev指向pos的prev,即上一个节点
	free(pos);//释放pos所在的空间
}

3.9插入

// pos位置之前插入x
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);//此节点不为空
	ListNode* prev = pos->prev;//prev存储pos的prev中的地址,即pos上一个节点
	ListNode* newnode = BuyListNode(x);//创建一个新节点

	// prev newnode pos
	prev->next = newnode;//上一个节点的next指向newnode
	newnode->prev = prev;//新节点的prev指向上一个节点
	newnode->next = pos;//新节点的next指向pos
	pos->prev = newnode;//pos的prev指向newnode
}

3.10查找

ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);//此节点不为空
	ListNode* cur = phead->next;//cur存储phead的next中的地址,即下一个节点
	while (cur != phead)//不是头节点
	{
		if (cur->data == x)//如果是要查找的地址
		{
			return cur;//找到了返回这个地址
		}

		cur = cur->next;//指向下一个节点
	}

	return NULL;//没有找到,返回空
}

3.11打印链表

void ListPrint(ListNode* phead)
{
	assert(phead);//此节点不为空

	ListNode* cur = phead->next;//cur存储phead的next中的地址,即下一个节点
	while (cur != phead)//cur不是指向的自己(头节点)
	{								
		printf("%d ", cur->data);
		//打印cur存储的数据,即下一个地址的数据(因为有头节点)
		cur = cur->next;//指向下一个节点
	}
	printf("\n");
}

3.12销毁链表

void ListDestory(ListNode* phead)
{
	assert(phead);//phead不为空
	ListNode* cur = phead->next;//cur存储phead的next中的地址,即下一个节点
	while (cur != phead)//cur指向的不是自己
	{
		ListNode* next = cur->next;//next指向下一个节点
		free(cur);//释放cur所在的空间
		cur = next;//cur指向下一个节点
	}

	free(phead);//释放头节点所在的空间
	phead = NULL;//头节点置空

}

四、简化链表，用插入和删除代替其他插入删除

void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);//phead不为空
	ListInsert(phead, x);//可以用插入来表示尾插
}

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);//此节点不为空
	ListInsert(phead->next, x);//可以用插入来表示头插
}

void ListPopFront(ListNode* phead)
{
	assert(phead);//phead不为空
	ListErase(phead->next);//可以用删除表示头删
}

void ListPopBack(ListNode* phead)
{
	assert(phead);//此节点不为空
	ListErase(phead->prev);//可以用删除表示尾删
}

// pos位置之前插入x
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);//此节点不为空
	ListNode* prev = pos->prev;//prev存储pos的prev中的地址,即pos上一个节点
	ListNode* newnode = BuyListNode(x);//创建一个新节点

	// prev newnode pos
	prev->next = newnode;//上一个节点的next指向newnode
	newnode->prev = prev;//新节点的prev指向上一个节点
	newnode->next = pos;//新节点的next指向pos
	pos->prev = newnode;//pos的prev指向newnode
}

// 删除pos位置的值
void ListErase(ListNode* pos)
{
	assert(pos);//此节点不为空

	ListNode* prev = pos->prev;//prev存储pos的prev中的地址,即上一个节点
	ListNode* next = pos->next;//next存储pos的next中的地址,即下一个节点
	prev->next = next;//上一个节点的next指向pos的next,即下一个节点
	next->prev = prev;//下一个节点的prev指向pos的prev,即上一个节点
	free(pos);//释放pos所在的空间
}

五、SList.h

#include"List.h"

ListNode* BuyListNode(LTDataType x)
//创建一个新节点
{
	ListNode* newnode = malloc(sizeof(ListNode));
	//malloc分配大小,是一个ListNode结构体的大小
	newnode->data = x;//将新节点的data字段设置为参数x的值
	newnode->next = NULL;//给新节点的next存储的地址置空
	newnode->prev = NULL;//给新节点的prev存储的地址置空

	return newnode;
}

//void ListInit(ListNode* phead)
初始化了链表的新节点
//{
//	phead = BuyListNode(0);//phead指向了这个新创建的节点
//	phead->next = phead;//将phead的 next 指向其自身
//	phead->prev = phead;//将phead的 prev 指向其自身
//}

ListNode* ListInit()
//创建头节点
{
	ListNode* phead = BuyListNode(0);//phead指向了这个新创建的节点
	phead->next = phead; // 将phead的 next 指向其自身
	phead->prev = phead; // 将phead的 prev 指向其自身

	return phead;//返回phead,即头节点
}


void ListDestory(ListNode* phead)
{
	assert(phead);//phead不为空
	ListNode* cur = phead->next;//cur存储phead的next中的地址,即下一个节点
	while (cur != phead)//cur指向的不是自己
	{
		ListNode* next = cur->next;//next指向下一个节点
		free(cur);//释放cur所在的空间
		cur = next;//cur指向下一个节点
	}

	free(phead);//释放头节点所在的空间
	phead = NULL;//头节点置空

}

void ListPrint(ListNode* phead)
{
	assert(phead);//此节点不为空

	ListNode* cur = phead->next;//cur存储phead的next中的地址,即下一个节点
	while (cur != phead)//cur不是指向的自己(头节点)
	{								
		printf("%d ", cur->data);
		//打印cur存储的数据,即下一个地址的数据(因为有头节点)
		cur = cur->next;//指向下一个节点
	}
	printf("\n");
}


void ListPushBack(ListNode* phead, LTDataType x)
//x = 0,尾插
{
	//assert(phead);//phead不为空
	//ListNode* tail = phead->prev;//tail存储phead的prev中的地址,即最后一个节点
	//ListNode* newnode = BuyListNode(x);//创建一个新节点
	//
	//tail->next = newnode;//上一个节点的next指向新节点
	//newnode->prev = tail;//新节点的prev指向phead
	//newnode->next = phead;//新节点的next指向phead
	//phead->prev = newnode;//上一个节点的prev指向新节点
	ListInsert(phead, x);//可以用插入来表示尾插
}



//void ListPushFront(ListNode* phead, LTDataType x)
x = 0,头插
//{
//	assert(phead);//此节点不为空
//
//	ListNode* first = phead->next;//first存储phead的next中的地址,即下一个节点
//	ListNode* newnode = BuyListNode(x);//在x处创建一个新节点
//
//	// phead newnode first
//	phead->next = newnode;//下一个节点的next指向新节点
//	newnode->prev = phead;//新节点的prev指向此节点
//	newnode->next = first;//新节点的next指向此节点
//	first->prev = newnode;//下一个节点的prev指向新节点
//}

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);//此节点不为空

	//顺序不能换
	ListNode* newnode = BuyListNode(x);
	newnode->next = phead->next;//存储phead的next,即下一个节点
	phead->next->prev = newnode;//下一个节点的prev指向newnode

	phead->next = newnode;//下一个节点的next 指向 newnode
	newnode->prev = phead;//newnode的prev 指向 phead
	//ListInsert(phead->next, x);//可以用插入来表示头插
}

void ListPopFront(ListNode* phead)
{
	assert(phead);//phead不为空
	assert(phead->next != phead);

	ListNode* first = phead->next;//先first存储phead的next中的地址,即phead的下一个节点
	ListNode* second = first->next;//再second存储下一个的节点的next中的地址,即下下个节点
	phead->next = second;//phead的next指向下下一个节点
	second->prev = phead;//下下一个节点的prev指向phead

	free(first);//下一个节点的空间被释放
	first = NULL;//first置空

	//ListErase(phead->next);//可以用删除表示头删
}

void ListPopBack(ListNode* phead)
{
	assert(phead);//此节点不为空
	/*assert(phead->next != phead);

	ListNode* tail = phead->prev;//先tail存储phead的prev中的地址,即上一个节点
	ListNode* prev = tail->prev;//prev存储上一个节点的prev中的地址,即上上一个节点

	prev->next = phead;//上上个节点的next指向phead
	phead->prev = prev;//phead的prev指向上上个节点

	free(tail);//释放tail存储的空间,即上个节点的空间
	tail = NULL;//tail置空
	*/

	ListErase(phead->prev);//可以用删除表示尾删
}

ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);//此节点不为空
	ListNode* cur = phead->next;//cur存储phead的next中的地址,即下一个节点
	while (cur != phead)//不是头节点
	{
		if (cur->data == x)//如果是要查找的地址
		{
			return cur;//找到了返回这个地址
		}

		cur = cur->next;//指向下一个节点
	}

	return NULL;//没有找到,返回空
}

// pos位置之前插入x
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);//此节点不为空
	ListNode* prev = pos->prev;//prev存储pos的prev中的地址,即pos上一个节点
	ListNode* newnode = BuyListNode(x);//创建一个新节点

	// prev newnode pos
	prev->next = newnode;//上一个节点的next指向newnode
	newnode->prev = prev;//新节点的prev指向上一个节点
	newnode->next = pos;//新节点的next指向pos
	pos->prev = newnode;//pos的prev指向newnode
}

// 删除pos位置的值
void ListErase(ListNode* pos)
{
	assert(pos);//此节点不为空

	ListNode* prev = pos->prev;//prev存储pos的prev中的地址,即上一个节点
	ListNode* next = pos->next;//next存储pos的next中的地址,即下一个节点
	prev->next = next;//上一个节点的next指向pos的next,即下一个节点
	next->prev = prev;//下一个节点的prev指向pos的prev,即上一个节点
	free(pos);//释放pos所在的空间
}

六、Test.c

#include"List.h"

void TestList1()
{
	ListNode* plist = ListInit();//plist为头节点
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);

	ListPushFront(plist, 0);
	ListPushBack(plist, -1);
	ListPrint(plist);

	/*ListPopFront(plist);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);

	ListPopBack(plist);
	ListPrint(plist);

	ListDestory(plist);*/

}

int main()
{
	TestList1();

	return 0;
}

今天就先到这了！！！

看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！

你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
心中带点小风骚的头像心中带点小风骚普通用户
0
上一篇 2023年12月27日
下一篇 2023年12月27日

相关推荐