数据结构与算法-双向链表专题

目录

一. 双向链表的结构

二.双向链表的使用

2.1 创建节点

2.2 初始化

2.3 打印

2.4 尾插

2.5 头插

2.6 尾删

2.7 头删

2.8 在指定位置pos之后插入数据

2.9 查找数据

2.10 删除pos位置的节点

2.11 销毁链表

---

一. 双向链表的结构

在List.h的头文件中对链表的结构进行创建

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;//双向链表的结构
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

为了方便使用，将结构体类型重命名为LTNode

将存储数据的类型通过typedef来使用，方便进行修改

如果双向链表为空，则只有头节点一个节点。

如果phead=NULL，则只能说明这不是一个有效的双向链表。

二.双向链表的使用

2.1 创建节点

（下列的声明就不再显示，直接写函数的实现）

//创建节点
LTNode* LTNBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = node->prev = node;return node;
}

 由于带头双向循环链表的特性，prev和next都指向node本身，也就是自身循环

2.2 初始化

//初始化
void LTInit(LTNode** phead)
{* phead =LTNBuyNode(-1);
}

初始化就是创建哨兵位，哨兵位的数据和地址都不会被修改

哨兵位也就是头节点，原先单链表中说的头节点其实是指第一个有效节点。

第二种方式：

LTNode* LTInit()
{LTNode*phead = LTNBuyNode(-1);return phead;
}

 无需创建变量，而是直接返回phead

2.3 打印

//打印
void LTPrint(LTNode* phead)//int 类型
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

2.4 尾插

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTNBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}

尾插主要是要直到双向链表尾插的结构和指针指向就很简单了

如果你要在哨兵位前面头插，那相当于尾插（因为双向链表是带头双向循环链表）

2.5 头插

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

2.6 尾删

//尾删
void LTPopBack(LTNode* phead)
{//链表必须有效，且链表不为空assert(phead&&phead->next!=phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

注意，需要del来承载phead->next

链表有效且不为空

2.7 头删

//头删
void LTPopFront(LTNode* phead)
{//链表必须有效，且链表不为空assert(phead && phead->next != phead);LTNode* del = phead->next;//phead,del,del->nextphead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}

2.8 在指定位置pos之后插入数据

//在pos位置之后插⼊数据 
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTNBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

2.9 查找数据

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

注意返回的是数据的节点地址

所以之后要检验find是否为空来判断是否有

2.10 删除pos位置的节点

//删除pos节点
//为什么不传二级指针
//为了保证接口的一致性void LTErase(LTNode* pos)
{//理论上pos不能为phead，但是没有参数phead，无法增加校验assert(pos);//pos,pos->next,pos->prevpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

这里不使用二级指针传参是因为为了保证接口的统一性，因为之前的形参都是一级指针

所以此函数使用后需要将find指针变为NULL

2.11 销毁链表

//销毁链表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

使用后还得将plist（实参）赋值为空指针

原来还是应该传二级指针，但是为了接口统一性，跟前者一样