数据结构——双向链表（保姆级教程，包学包会）

1.双向链表的概念

双向链表就是带头双向循环链表

我们在学完单链表之后，就感觉这个非常简单了，他的主要表现就是拥有头节点，链表永不为空，不需要二级指针；可以通过一个节点找到上一个或者下一个节点；头尾相连呈环状。

他主要结构是由prev、next、data，这三个结构组成，通过prev找到前一个节点，next就不用多说了。

如图所示

 不多废话，直接上代码

2.双向链表的实现

2.1 结构设计

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

}LTNode;

2.2 接口总览

实现一个双向链表的各个接口

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

}LTNode;

LTNode* LTInit();
void LTPrint(LTNode* phead);

bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

LTNode* LTFind(LTNode* phead, LTDataType x);

// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
// 删除pos位置的值
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

注意看一下啊我们的初始化的时候，这里是不带参数的，是为什么呢？

双向链表是带头的，有头节点，就是我们说的哨兵位，哨兵位不存储有效数据，所以链表的第一个节点就是哨兵位后面的第一个节点。

注意：这里面我们用二级指针也可以操作，但是我们在以后的代码中二级指针太麻烦而且容易用错，所以我们直接用哨兵位的办法来解决，不需要用二级指针。

2.3 初始化

创建一个哨兵位，让他自己变成一个环形链表

只需要让他自己指向自己就可以

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

 2.4 创建节点

当我们需要插入元素是，只需要创建节点，然后直接把值存入，两个指针置为空，返回该节点的地址就可。

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
	
}

2.5 尾插

直接图片更清晰观赏，我们思路是：将tail->next的链接直接连接到newnode，然后将newnode->prev连接到tail。最后phead的prev和next连接即可。

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

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

2.6 头插

头插就是将链表上的第一个节点与哨兵位的链接断开，但是在断开之前我们一定要先保存好将要断开的data，在去改变你将要头插的newnode

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* first = phead->next;
	LTNode* newnode = BuyLTNode(x);

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;

}

 2.7 尾删

这里我们还是一样的要找到tail前一个节点tailprev，然后直接释放掉尾节点就好

这里面注意一下，要是只有哨兵位就不能删除

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//防止把哨兵位删掉
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);

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

2.8 头删

对于头删来说，我需要删除链表的第一个节点，也就是 哨兵位的 next 节点 ，我需要改变 哨兵位 和 第二个节点 的链接关系，然后释放 第一个节点 。

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* first = phead->next;
	LTNode* firstnext = first->next;
	free(first);

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

2.9 查找

对于 双向链表 来说，它是没有指向NULL的节点的，它是一个环，停不下来。所以我们要把循环的截止条件设定为 ! = phead，这个条件就表示，已经遍历过一遍链表了

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

2.10 在pos之前插入

通过 pos 的 prev 找到 pos 位置的上一个节点 posprev ，然后改变 posprev 和 新节点 newnode  之间的链接和 newnode 和 pos 之间的链接

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;

	newnode->prev = posprev;
	posprev->next = newnode;

	newnode->next = pos;
	pos->prev = newnode;
}

2.11 在pos之前插入

在pos位置删除，我们只需找到pos前一个节点posprev，和后一个节点posnext，将prev和next的链接接好，释放pos节点

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	free(pos);

	posprev->next = posnext;
	posnext->prev = posprev;
}

2.12 判断是否为空

这里我们可以加上这个函数，如果phead下一个等于phead，说明链表为空只剩下哨兵位自己，那么此时我们就不能继续删除了，这里我们可以用这个函数直接替换掉上面的断言

bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

这里我们也可以简写成：

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTInsert(phead, x);
}


void LTPushFront(LTNode* phead, LTDataType x)
{
	LTInsert(phead->next, x);
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->prev);
}


void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	LTErase(phead->next);

}

2.13 打印

void LTPrint(LTNode* phead)
{
	assert(phead);

	printf("guard<==>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.14 销毁

我们这时直接把链表节点全部删除，在删除过程中记住我们下一个节点以便于循环

注意：由于在函数中，我释放了哨兵位，并要将其置空。释放是可以的，因为我知道哨兵位的地址，释放就可以，但是置空却完成不了。因为我的 哨兵位 是形参，改变形参并不能影响实参，所以我们还需要在主函数中将 哨兵位 置空

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

完整代码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

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

}LTNode;

LTNode* LTInit();
void LTPrint(LTNode* phead);

bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

LTNode* LTFind(LTNode* phead, LTDataType x);

// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
// 删除pos位置的值
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

List.c

#include "List.h"


LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
	
}

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

bool LTEmpty(LTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);

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

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* first = phead->next;
	LTNode* newnode = BuyLTNode(x);

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;

}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//防止把哨兵位删掉
	LTNode* tail = phead->prev;
	LTNode* tailprev = tail->prev;
	free(tail);

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

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* first = phead->next;
	LTNode* firstnext = first->next;
	free(first);

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

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

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posprev = pos->prev;

	newnode->prev = posprev;
	posprev->next = newnode;

	newnode->next = pos;
	pos->prev = newnode;
}

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
	free(pos);

	posprev->next = posnext;
	posnext->prev = posprev;
}

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

void LTPrint(LTNode* phead)
{
	assert(phead);

	printf("guard<==>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

Test.c

#include"List.h"

void TestList1()
{
	LTNode* plist = LTInit();
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);

	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

	LTPopBack(plist);
	LTPrint(plist);

	//LTPopBack(plist);
	//LTPrint(plist);

	LTDestroy(plist);
	plist = NULL;
}

void TestList2()
{
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	LTPopFront(plist);
	LTPrint(plist);

	/*LTPopFront(plist);
	LTPrint(plist);*/

	LTDestroy(plist);
	plist = NULL;
}

void TestList3()
{
	LTNode* plist = LTInit();
	LTPushFront(plist, 1);
	LTPushFront(plist, 2);
	LTPushFront(plist, 3);
	LTPushFront(plist, 4);
	LTPrint(plist);

	LTNode* pos = LTFind(plist, 3);
	if (pos)
	{
		LTInsert(pos, 30);
	}
	LTPrint(plist);

	LTDestroy(plist);
	plist = NULL;
}

int main()
{
	TestList3();

	return 0;
}

以上就是今天的分享喜欢的话请三联支持一下我们下期再见哦文章来源地址https://www.toymoban.com/news/detail-769512.html

到了这里，关于数据结构——双向链表（保姆级教程，包学包会）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！