【数据结构】双向链表

2024-04-25 19:22:03
开发
13

前面我们学习了单向链表，在单向链表中我们找最后一个节点的时候都要遍历一遍链表。我们下面学习的双向链表中，我们就可以规避这一问题。

文章目录

一、双向链表的结构
二、双向链表的实现

一、双向链表的结构

在这里插入图片描述
在这里，带头链表里的头节点，实际为“哨兵卫”，哨兵卫节点不存储任何有效元素，只是站在这里“放哨的”
注意：这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，实际前⾯的在单链表阶段称呼不严
谨，但是为了同学们更好的理解就直接称为单链表的头节点。
双向链表为空时，此时链表中只剩下一个头节点。

二、双向链表的实现

2.1 定义双向链表结构

和之前我们实现的单链表一天，创建头文件（.h）和源文件（.c），测试文件创建出来test.c

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

}LTNode;

双向链表一个节点由数据和指向下一个节点的指针指向上一个节点的指针组成。

2.2 双向链表的初始化

函数的声明

LTNode* LTInit();

函数的实现

LTNode* LTInit()
{
	//phead 哨兵卫
	LTNode* phead = LTBuyNode(1);
	return phead;
}

在这之前我们要先创建新节点，所以写一个创建新节点的函数

//申请新节点
 LTNode* LTBuyNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(1);
	}
	node->data = x;
	node->next = node->prev = node;

	return node;
}

malloc创建新节点，存储数据并且把指向后一个节点的指针和指向前一个节点的指针指向自己。
初始化中，申请一个新节点当哨兵卫也就是头节点。

2.3双链表的尾插

函数的声明

void LTPushBack(LTNode* phead, LTDataType x);

函数的实现

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

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

在这里插入图片描述

先断言传过来的哨兵卫不能为空，申请新节点。先让即将尾插进来的新节点指向前一个节点的指针也就是prev指针指向之前链表的最后一个节点，让新节点的指向下一个节点的指针也就是next指针指向头节点。让之前链表的最后一个节点的next指针指向新节点，最后让头节点也就哨兵卫的prev指针指向新节点。这样就满足了双链表的结构。

2.4 双链表的头插

函数的声明

void LTPushFront(LTNode* phead, LTDataType x);

函数的实现

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

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

在这里插入图片描述
断言，申请新节点。
让新节点的prev指针指向头节点，让新节点的next指针指向之前链表头节点的下一个节点。让之前链表中头节点下一个节点的prev指针指向新节点，最后让头节点的next指针指向新节点。

2.5 双链表的尾删

函数的声明

void LTPopBack(LTNode* phead);

函数的实现

//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next != NULL);

	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}

在这里插入图片描述
创建一个临时变量储存最后一个节点，将最后一个节点的前一个前一个节点的next节点指向头节点，将头节点的prev指针指向指向最后一个节点的前一个节点。最后释放最后一个节点。

不管是头插还是尾插，头节点都不会发生变化。头插是在头节点之后插入。

2.6 双链表的头删

函数的声明

void LTPopFront(LTNode* phead);

函数的实现

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != NULL);

	LTNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}

在这里插入图片描述
创建一个临时变量存储头节点的下一个节点。让要删除的节点的下一个节点的prev指向头节点，头节点的next指针指向要删除的节点的下一个节点。

2.7 在指定位置（pos）后插入

函数的声明

void LTInsert(LTNode* pos, LTDataType x);

函数的实现

//在指定位置后插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode= LTBuyNode(x);

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

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

}

在这里插入图片描述
让新节点的next指针指向之前链表pos节点的下一个节点，让新节点的prev指针指向pos节点。让pos下一个节点的prev指针指向新节点，让pos的next指针指向新节点。

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

在链表中找到想要的节点，遍历链表找想要的节点。

2.8删除指定（pos）节点

函数的声明

void LTErase(LTNode* pos);

函数的实现

//删除pos节点
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);

}

在这里插入图片描述
让pos节点的前一个节点的next指针指向pos节点的下一个节点。让pos节点的下一个节点的prev指针指向pos节点的前一个节点。释放pos节点。

2.9 链表的销毁

函数的声明

void LTDesTroy(LTNode* phead);

函数的实现

//链表的销毁
void LTDesTroy(LTNode* phead)
{
	assert(phead);

	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pcur = pcur->next;
}

把哨兵卫的下一个节点用临时变量存储起来也就是像单链表一样的位置开始，用while循环判断条件是节点的next指针不指向头节点。遍历链表释放每一个节点。

Seqlist.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;

}LTNode;

//初始化
LTNode* LTInit();

//申请新节点
LTNode* LTBuyNode(LTDataType x);

//尾插
void LTPushBack(LTNode* phead, LTDataType x);

//头插
void LTPushFront(LTNode* phead, LTDataType x);

//尾删
void LTPopBack(LTNode* phead);

//头删
void LTPopFront(LTNode* phead);

//在pos之后插入数据
void LTInsert(LTNode* pos, LTDataType x);

//删除pos节点
void LTErase(LTNode* pos);

//链表的销毁
void LTDesTroy(LTNode* phead);

Seqlist.c

#include"List.h"
//初始化
LTNode* LTInit()
{
	//phead 哨兵卫
	LTNode* phead = LTBuyNode(1);
	return phead;
}
//打印数据
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while(pcur!=phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}
//找数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//申请新节点
 LTNode* LTBuyNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(1);
	}
	node->data = x;
	node->next = node->prev = node;

	return node;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev->next = newnode;
	phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

	newnode->prev = phead;
	newnode->next = phead->next;
	phead->next->prev = newnode;;
	phead->next = newnode;
}
//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next != NULL);

	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != NULL);

	LTNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}
//在指定位置后插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode= LTBuyNode(x);

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

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

}
//删除pos节点
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);

}
//链表的销毁
void LTDesTroy(LTNode* phead)
{
	assert(phead);

	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pcur = pcur->next;
}

test.c

#include"List.h";

void test()
{
	LTNode* plist = LTInit();
	//LTPushBack(plist, 1);
	//LTPrint(plist);
	
	//LTPrint(plist);
	//LTPopBack(plist);
	//LTPrint(plist);
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);
	LTPushBack(plist, 3);
	LTPushBack(plist, 4);
	LTPrint(plist);
	//LTPrint(plist);
	//LTPopFront(plist);
	/*LTPrint(plist);
	LTInsert(plist, 2);*/
	/*LTPrint(plist);
	LTErase(3);*/
	//LTNode* find = LTFind(plist, 3);
	//LTErase(find);
	//find = NULL;
	//LTPrint(plist);
	//LTDesTroy(plist);
	LTNode* pos = LTFind(plist, 2);
	if (pos != NULL) {
		LTInsert(pos, 4);
		LTPrint(plist);
	}
	LTPrint(plist);
}
int main()
{
	test();
	return 0;
}

LTErase和LTDestroy参数理论上要传二级指针，因为我们需要让形参的改变影响实参，但是为了保持接口的一致性才传的一级指针。传一级指针时，当形参phead置为NULL后实参plist不会被修改为NULL，所以在调用完后要手动将实参置为NULL。

原文地址:https://blog.csdn.net/GGDxianv/article/details/138191231 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1783456430758694912.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部