首页 > 其他分享 >教你如何手撕双向链表

教你如何手撕双向链表

时间:2024-07-22 14:55:17浏览次数:11  
标签:void pos next 链表 如何 LTNode phead 双向 prev

1. 双向链表

1.1 概念与结构

注意:这⾥的“带头”跟前⾯我们说的“头结点”是两个概念,实际前⾯的在单链表阶段称呼不严 谨,但是为了同学们更好的理解就直接称为单链表的头结点。
带头链表⾥的头结点,实际为“哨兵位”,哨兵位结点不存储任何有效元素,只是站在这⾥“放哨的”

1.2 实现双向链表

List.h

typedef int LTDataType;
typedef struct ListNode
{
     struct ListNode* next; //指针保存下⼀个结点的地址
     struct ListNode* prev; //指针保存前⼀个结点的地址
     LTDataType data;
}LTNode;
//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDestroy(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
LTNode *LTFind(LTNode* phead,LTDataType x);

1.3 头插

思路:

        要先把新节点的next指针指向head的next节点,然后head的next节点(d1)的prev指针指向要

插入的新节点,将插入新节点的prev指针指向head,最后head的next指针指向新节点。

代码实现(list.c):
 
void LTHBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

1.4 尾插

思路:

        要先把新节点的next指针指向head节点,然后head的prev节点(d3)的next指针指向要插入的

新节点,将插入新节点的prev指针指向head的prev节点(d3),head的prev指针指向新节点。

代码实现(list.c):
void LTPBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	//申请新的节点
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

1.5 尾删

代码实现:
void LTPDel(LTNode* phead) 
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	LTNode* preva = del->prev;
	preva->next = phead;
	phead->prev = preva;
	free(del);
	del = NULL;
}

1.6 头删

如图:

代码实现:
void LTHDel(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTNode* next = phead->next;
	next->next->prev = phead;
	phead->next = next->next;
	free(next);
	next = NULL;
}

1.7 寻找指定位置数据

代码实现:

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

1.8 指定位置之后插入节点

注:需调用1.7的方法找到相应位置后方可插入节点 代码实现:
 
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;
}

1.9 删除指定位置的节点

注:需调用1.7的方法找到相应位置后方可插入节点 代码实现:
 
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos -> next;
	free(pos);
	pos = NULL;
}

最后来销毁双向链表:

//销毁链表
void LTDestory(LTNode** pphead)
{
	assert(pphead && *pphead);
	LTNode* pour = (*pphead)->next;
	while (pour != *pphead)
	{
		LTNode* Next = pour->next;
		free(pour);
		pour = Next;
	}
	free(*pphead);
	*pphead = NULL;
	pour = NULL;
}

 

这就完成了一个双向链表,如有不懂欢迎私信博主  ,诚信在线为大家解答!!

标签:void,pos,next,链表,如何,LTNode,phead,双向,prev
From: https://blog.csdn.net/L286594/article/details/140589292

相关文章

  • 如何修复包含 OpenAi api 的 Flask 服务器的 405 错误?
    我正在尝试向我的网页添加API,之前从未使用过任何Flask服务器,也从未使用过Javascript,所以这是一次全新的学习体验。我的问题是我不断收到405错误代码,指出该方法不被允许。我继续使用POST方法,但它不起作用,我相信我的问题可能更多地出在我的HTML代码而不是我的Flask服......
  • 在 VSCode 中通过 Python 使用 YouTube API 时如何启用 Intellisense
    我想在使用GoogleYouTubeAPI和Python时在VSCode中获得IntelliSense。但我不知道详细步骤。fromgoogleapiclient.discoveryimportbuildapi_key="****"youtube=build("youtube","v3",developerKey=api_key)request=youtube.channels().list(part......
  • 2024-07-22 如何让宽度和高度一致(flex布局)
    <template><divclass="demo-container"><divclass="demo-item"><divclass="demo-title">方向指示类图标</div><divclass="demo-content">......
  • 如何使 argparse 与枚举和默认值完美配合?
    我有一个枚举:fromenumimportauto,EnumclassMyEnum(Enum):ONE=auto()TWO=auto()THREE=auto(),我想将它用作argparse的参数。更具体地说,我想创建一个接受枚举名称之一("one","two","three")并且可能具有默认值的参数,并且相......
  • Nginx 中如何实现请求的排队机制?
    Nginx中如何实现请求的排队机制?在当今数字化的时代,网站和应用的流量就如同潮水一般,时涨时落,时急时缓。想象一下,当流量如洪水猛兽般汹涌而来,服务器就像是那抗洪的堤坝,如果没有有效的管理和调度,很容易就会被冲垮。而Nginx就像是一位聪明的水利工程师,能够通过其强大的功能,......
  • Nginx 如何处理请求的限速?
    ......
  • 如何消除此错误:Traceback(最近一次调用最后一次):文件“<string>”,第 1 行,在 <module> 文
    我一直尝试用uvicornmain:app--reload启动我的python后端,但我不断收到此错误:INFO:Willwatchforchangesinthesedirectories:['C:\\Users\\darkg\\OneDrive\\Desktop\\loginpage\\FastAP_BackEnd\\books']INFO:Uvicornrunningonhttp://......
  • (算法)合并两个有序链表————<递归>
    1.题⽬链接:21.合并两个有序链表 2.题⽬描述: 3.解法(递归):算法思路:1.递归函数的含义:交给你两个链表的头结点,你帮我把它们合并起来,并且返回合并后的头结点;2.函数体:选择两个头结点中较⼩的结点作为最终合并后的头结点,然后将剩下的链表交给递归函数去处理;3.递归出......
  • Mailspring邮件服务器如何配置做邮件管理?
    Mailspring邮件服务器性能调优的策略?如何部署服务器?Mailspring是一款功能强大的邮件客户端,支持多种邮件服务,同时具有直观的用户界面和丰富的功能。那么,如何配置Mailspring邮件服务器来进行邮件管理呢?AokSend将详细介绍相关步骤和技巧。Mailspring邮件服务器:下载安装可以从M......
  • 如何在 vercel 部署中路由 python 和 typescript 无服务器函数
    我从一个带有Next.js和Typescript前端以及python后端的全栈应用程序开始。由于我们想在vercel上部署,因此我们将所有后端功能迁移到/api文件夹中的typescript函数中,可通过以下方式访问:fetch('api/**foldername**)问题是我有一个简单的pytorch模型,因此......