Guff_9hys

这个屌丝很懒，什么也没留下！

热门标签

【数据结构】--双向链表

作者：Guff_9hys | 2024-06-27 05:22:17

踩

双向链表

本篇文章经过检测基本没问题，放心

一、双向带头循环链表的实现

一、ListInit--初始化函数

二、CreateListNode--创造节点函数

三、ListPushBack--尾插函数

四、ListPrint--打印函数

五、ListPopback--尾删函数

六、ListPushFront--头插函数

七、ListPopFront--头删函数

八、ListFind---查找函数

九、ListInsert--指定位置pos前面插入函数

十、 ListErase--指定pos位置删除节点的函数

十一、ListDestroy--销毁链表函数

二、回顾链表与顺序表的优缺点

一、双向带头循环链表的实现

①双链表的头结点：

头结点只是为了操作更方便，有头结点功能实现更简洁，但是你可以在功能实现中忽略他，比如打印数据，插入数据等都不要动这个头结点，不打印头结点的数据等，并且删除更不要动头结点，而是要删除头结点后面的节点

②实际中链表的结构非常多样，以下情况组合有8中链表结构：

1、单向、双向

2、带头、不带头

3、循环、非循环

注意：哨兵位的头结点不存储任何有效数据，带头双向循环链表的实现比之前学的无头单向非循环更简单，有头的链表无需传二级指针改变指向了，他很方便，他跟双向单向，循环不循环无关，只要带头它对某些操作就很方便

在之前单向链表的实现过程我们就知道，如果想改变你传进来的链表，你需要传链表头的地址，也就是用二级指针，但也有另外一种方法，即使用返回值，返回这个链表类型的头结点

需要头是因为有了头结点对于我们插入等操作，都很方便

那么我们必须知道双向带头循环链表为空是什么样的，为空就是只有一个头结点，如下图：

用vs分三个文件：List.c List.h test.c

首先我们是用以下操作，定义了链表，和链表每个节点的数据类型


typedef int LTDateType;
typedef struct ListNode
{
	LTDateType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

一、ListInit--初始化函数

所以初始化双向带头循环链表就是开辟一个头，然后两个指针域都指向自己就可以


LTNode* ListInit(void)
{
	//哨兵位的头结点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

二、CreateListNode--创造节点函数


LTNode* CreateListNode(LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;;
}

三、ListPushBack--尾插函数

尾插是否要传二级指针，因为尾插你并不改变结构体指向的头，这个链表你已经创建一个头了，它是改变这个链表（结构体）的内容。注：你传入的plist一定是初始化完带头的，所以要assert断言一下，防止你传入的是无头的，防止是NULL。

那这么写对空链表（只有一个头的时候）尾插时是否需要特殊考虑呢？不需要，因为它带头，空链表也是符合的，但是我们之前实现的单链表无头是需要特殊考虑的，这就是带头链表的优势，当然，他也有对应的缺点，比如要释放它，并且函数返回时返回的不是头结点，而是下一个。


void ListPushBack(LTNode* phead)
{
	assert(phead);
	//断言是因为如果你没有创建哨兵位的头结点，assert
	//就会帮你直接报错，防止你出现错误
	LTNode* tail = phead->prev;
	LTNode* newnode = CreateListNode(x);
	//phead             tail newnode
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

四、ListPrint--打印函数

因为带头，故只需从头结点的后一个节点开始遍历，而头结点无需遍历，因为头不存储有效数据，你无需打印头结点的数据，头结点只是为了你操作方便而涉及，他的数据域是随机值。遍历到什么时候？循环链表无NULL，但我们遍历到头（phead）就可以，也就是从头结点的后一个节点开始，往后打印数据，直到遇到了头结点，说明我已经遍历一次了。


void ListPrint(LTNode* phead)
{
	assert(phead);
	//断言的意思是你传的链表一定至少有个头
	//因为这里讲的就是有头结点的链表，不能传入NULL
    //也就是不能传入没有头结点的链表
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

五、ListPopback--尾删函数

尾删就是需要注意先保存尾删之前一个的节点，改变指向，最后再释放尾节点，因为如果你先释放，释放导致的结果就是你的尾节点的地址和值都会变成随机值。而你此时对已经释放的地址去访问（因为你tail保存原来的尾节点地址了），那么再改变指向，就是会对NULL解引用，那么就会非法访问内存。这是经典的野指针问题。

还有一个问题，这个链表的头结点不能删除，删到头结点之前应该也加一个断言。


void ListPopBack(LTNode* phead)
{
	assert(phead);//传进来的链表的头不能为NULL，要有头结点
	assert(phead->next != phead);//这种情况如果相等是链表为空的情况，就不能往下删了
	//当然，用if也可以，但是更推荐assert这种暴力法
	//这里也可以写成assert(phead->prev != phead);也可以，因为都表示链表为空的状态
	LTNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next = phead;
	free(tail);
	//也可以写成如下，如下的方法更推荐！
	/*assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;*/
}

六、ListPushFront--头插函数

注意头插，因为有头结点，头插直接插在头的后面就可以，一定不要插在头结点的前面。那么还需考虑临界问题，若链表为空链表呢？还是可以的，这就是因为带头结点的优势。


void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);//你传入的链表必须有头
	LTNode* newnode = CreateListNode(x);
	if (newnode == NULL)
		exit(-1);
//exit（-1）表示异常退出程序
//eixt(0)表示正常退出程序
//动态开辟内存都失败了，肯定属于异常退出了
	LTNode* next = phead->next;
 
	phead->next = newnode;
	newnode->prev = phead;
 
	newnode->next = next;
	next->prev = newnode;
}

七、ListPopFront--头删函数

带头的链表关于删除的问题，一定不能把头结点删除了，所以加一个断言，并且，头删一定是从头结点后面的那个节点开始删除，不要动头结点。


void ListPopFront(LTNode* phead)
{
	assert(phead);
	//链表为空的情况（只有头结点了），就不能继续删除了
	assert(phead->next != phead);//不能动头结点
	LTNode* next = phead->next;
	LTNode* nextNext = next->next;
 
	phead->next = nextNext;
	nextNext->prev = phead;
	free(next);
}

八、ListFind---查找函数

查找意味着遍历这个链表一次，但是循环链表没有NULL，那这个函数实现和ListPrint函数实现的思路很类似了，找到头了，那就意味这个链表遍历了一遍，因为尾节点是指向头的。我们规定如果没找到返回这个节点，则返回NULL


LTNode* ListFind(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* cur = phead->next;//从头结点的后一个节点开始遍历
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
 
		cur = cur->next;
	}
	return NULL;
}

九、ListInsert--指定位置pos前面插入函数

注意我们这里不用下标，因为之前我们已经写了一个ListFind查找函数，我们用pos可以更方便的使用查找函数。pos是一个节点，即LTNode类型的。pos肯定是通过ListFind函数查找到的，所以不可能存在插入节点在头结点之前的情况。


//在pos位置之前插入
void ListInsert(LTNode* pos, LTDateType x)
{
	assert(pos);//因为查找节点存在节点为NULL的情况，即不存在
	LTNode* posprev = pos->prev;
	LTNode* newnode = CreateListNode(x);
 
	posprev->next = newnode;
	newnode->prev = posprev;
 
	newnode->next = pos;
	pos->prev = newnode;
}

那么有了ListInsert函数就可以改一下头插和尾插函数，均可用ListInsert函数实现，下面为用ListInsert改头插尾插函数的实现逻辑

也就是可以改成


void ListPushBack(LTNode* phead,LTDateType x)
{
     assert(phead);
    ListInsert(phead,x);
//在头结点的前面插入一个节点，就实现了尾插
//因为头结点的前面插入一个节点就会被看做尾节点，因为指针域等原因
}
void ListPushFront(LTNode* phead,LTDateType x)
{
    assert(phead);
    ListInsert(phead->next,x);
//在头结点的下一个节点前面插入一个节点，就实现了头插
}

十、 ListErase--指定pos位置删除节点的函数

思路和指定插入大差不差，但是为什么没有断言或者说判断会不会删到头结点的情况，因为pos是通过ListFind函数找到的，他肯定是LTNode类型的，也就是一个结点，而ListFind函数只能找到这个链表中的除了头结点以外的其他节点，所以不存在会删掉头结点的情况。


//删除pos位置的节点
void ListErase(LTNode* pos)
{
	assert(pos);
 
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
 
	posprev->next = posnext;
	posnext->prev = posprev;
	free(pos);
	pos = NULL;
	//pos不置为NULL也可以，因为他就一个函数内的局部变量
	//出了函数就找不到了
}

同理，头删和尾删都可以用ListErase来修改，代码如下


void ListPopBack(LTNode* phead,LTDateType x)
{
     assert(phead);
   
    ListErase(phead->prev,x);
}
void ListPopFront(LTNode* phead,LTDateType x)
{
    assert(phead);
 
    ListErase(phead->next,x);
}

十一、ListDestroy--销毁链表函数

销毁链表就是释放动态开辟的内存，归还给操作系统。

并且头结点也应该释放，头指针置为空，这个操作涉及头结点，因为在ListDestroy函数中最后会free掉头结点，那你头结点也要置NULL吧，但是因为你是一级指针你改变函数内部的phead，并不会影响函数外部的plist，但你为了保持接口函数一致性而不用二级指针，那么可以在主函数ListDestroy用完之后，主动写一个plist = NULL。


void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	//phead = NULL;这个操作并不会改变外面的plist，因为你没用二级指针，所以可以在主函数主动置plist为NULL
}

最后代码如下：

test.c:


#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
 
void TestList1()
{
	LTNode* plist = ListInit();
	ListPushBack(plist, 1);
	ListPushBack(plist, 3);
	ListPushBack(plist, 1);
	ListPushBack(plist, 4);
	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 5);
	ListPrint(plist);
	LTNode* pos = ListFind(plist, 1);
	if (pos)
	{
		ListErase(pos);
	}
	pos = ListFind(plist, 3);
	if (pos)
	{
		ListErase(pos);
	}
	pos = ListFind(plist, 1);
	if (pos)
	{
		ListErase(pos);
	}
	pos = ListFind(plist, 4);
	if (pos)
	{
		ListErase(pos);
	}
	ListPrint(plist);
	//ListDestroy(plist);
	//plist = NULL;
}
int main()
{
	TestList1();
	return 0;
}
//void ListPopBack(LTNode* phead)
//{
//	assert(phead);
//	assert(phead->next != phead);
//	ListErase(phead->prev);
//}
//void ListPopFront(LTNode* phead)
//{
//	assert(phead);
//	assert(phead->next != phead);
//	ListErase(phead->next);
//}

List.c:


#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
LTNode* ListInit()
{
	//哨兵位的头结点
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->prev = phead;
	phead->next = phead;
	return phead;
}
LTNode* CreateListNode(LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;;
}
void ListPushBack(LTNode* phead,LTDateType x)
{
	assert(phead);
	//断言是因为如果你没有创建哨兵位的头结点，assert
	//就会帮你直接报错，防止你出现错误
	LTNode* tail = phead->prev;
	LTNode* newnode = CreateListNode(x);
	//phead             tail newnode
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
 
void ListPrint(LTNode* phead)
{
	assert(phead);
	//断言的意思是你传的链表一定至少有个头
	//因为这里讲的就是有头结点的链表
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
 
void ListPopBack(LTNode* phead)
{
	assert(phead);//传进来的链表的头不能为NULL，要有头结点
	assert(phead->next != phead);//这种情况如果相等是链表为空的情况，就不能往下删了
	//当然，用if也可以，但是更推荐assert
	//这里也可以写成assert(phead->prev != phead);也可以，因为都表示链表为空的状态
	LTNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next = phead;
	free(tail);
	//也可以写成
	/*assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;*/
}
 
void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);//你传入的链表必须有头
	LTNode* newnode = CreateListNode(x);
	if (newnode == NULL)
		exit(-1);
	LTNode* next = phead->next;
 
	phead->next = newnode;
	newnode->prev = phead;
 
	newnode->next = next;
	next->prev = newnode;
}
 
void ListPopFront(LTNode* phead)
{
	assert(phead);
	//链表为空的情况（只有头结点了），就不能继续删除了
	assert(phead->next != phead);
	LTNode* next = phead->next;
	LTNode* nextNext = next->next;
 
	phead->next = nextNext;
	nextNext->prev = phead;
	free(next);
}
 
LTNode* ListFind(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
 
		cur = cur->next;
	}
	return NULL;
}
//在pos位置之前插入
void ListInsert(LTNode* pos, LTDateType x)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* newnode = CreateListNode(x);
 
	posprev->next = newnode;
	newnode->prev = posprev;
 
	newnode->next = pos;
	pos->prev = newnode;
}
//删除pos位置的节点
void ListErase(LTNode* pos)
{
	assert(pos);
 
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
 
	posprev->next = posnext;
	posnext->prev = posprev;
	free(pos);
	pos = NULL;
	//pos不置为NULL也可以，因为他就一个函数内的局部变量
	//出了函数就找不到了
}
void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	//phead = NULL;这个操作并不会改变外面的plist，因为你没用二级指针，所以可以在主函数主动置plist为NULL
}

List.h :


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

二、回顾链表与顺序表的优缺点

那么最后总结一下链表和顺序表的区别：

这两个结构各有优势，很难说谁更优秀

严格来说，他们俩是相辅相成的两个结构，各有优缺点

顺序表

优点：

1、支持随机访问。需要随机访问结构支持算法可以很好的适用。

2、cpu高速缓存命中率更高。

缺点：

1、头部中部插入删除时间效率低。时间复杂度：o（n）

2、连续的物理空间，空间不够了以后需要增容。

a、增容有一定程度的消耗。

b、为了避免频繁增容，我们一般会按倍数去增，用不完可能存在一定的空间浪费

链表（双向带头循环链表）

优点：

1、任意位置插入删除效率高。时间复杂度：o（1）

2、按需申请释放空间。

缺点：

1、不支持随机访问。（用下标访问）意味着；一些排序，二分查找等在这种结构上不适用。

2、链表存储一个值，同时要存储链接指针，也有一定的消耗，但这个缺点问题不大。

3、cpu高速缓存命中率更低。

关于cpu命中率的理解：

注意：了解即可，cache是缓冲的意思，cpu旁边两个东西是一级二级三级缓冲区和寄存器。

而你取顺序表中的内存时，因为计算机本身有很大概率取这个位置临近的内存，顺序表因为本身的连续性，可以把后面的也取到，而链表不连续，你拿到一个地方的内存，无法访问到后面的，会造成命中率变低

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/761427