C语言双向链表

前面我们已经学完了单链表的知识点（如果还没有看过的主页有哦~），这篇博客我们就来探讨探讨单链表的孪生弟弟——双向链表。

1.链表的分类

2.双向链表的结构

3.双向链表的实现

3.1 List.h

3.2 List.c

4.书写要点总结说明

4.1为什么要使用一级指针

4.2三个使用到的嵌套调用

4.3相对于单链表书写的不同

1.链表的分类

首先，链表中最基础的就是单链表，在单链表里面有提过一嘴一个东西“哨兵位”，其实呢，这个哨兵位才是链表真正的头节点。看到如下图：

从图中我们可以看到，链表的分类有八种（2*2*2）：

带不带头：表示有没有哨兵位（也就是不存储有效值的头结点）；“哨兵位”存在的意义：遍历循环链表避免死循环。
单向双向：代表链表可以访问的方向
循环不循环：代表链表的头结点和尾节点有没有链接起来

以下为更详细的表示：

其中我们称之前学过的单链表为“不带头单向不循环链表” ，而这篇要讲的双向链表则是“带头双向循环链表”。链表常用的就是这两种。

2.双向链表的结构

用图表示，结构如下：

想要实现向前访问这样的结构，我们就需要在单链表节点的结构体里面再加上一个指向上一个链表节点的指针。两个指针实现双向访问！

用代码表示如下：

typedef int LTDateType;
typedef struct LTNode {struct LTNode* prev;//指向上一个链表节点的指针LTDateType val;struct LTNode* next;//指向下一个链表节点的指针
}LTNode;

3.双向链表的实现

下面是实现双向链表的代码：

3.1 List.h

存放双向链表结构体及相关函数声明：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//双向链表节点结构体
typedef int LTDateType;
typedef struct LTNode {struct LTNode* prev;LTDateType val;struct LTNode* next;
}LTNode;//申请内存
LTNode* LTBuyNode(LTDateType x);//初始化空链表
LTNode* LTInit();
//头插
void LTPushFront(LTNode* phead,LTDateType x);
//尾插
void LTPushBack(LTNode* phead, LTDateType x);//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);//pos前插
void LTInsert(LTNode*pos,LTDateType x);
//pos后插
void LTInsertAfter(LTNode* pos, LTDateType x);//删pos
void LTErase(LTNode* pos);
//删pos后
void LTEraseAfter(LTNode* pos);//查找
LTNode* LTFind(LTNode* phead, LTDateType x);
//打印链表
void LTPrint(LTNode* phead);
//销毁链表
void LTDestroy(LTNode* phead);

3.2 List.c

存放相关函数定义：

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//初始化双向链表
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);phead->next = phead;phead->prev = phead;
}
//申请内存
LTNode* LTBuyNode(LTDateType x)
{LTNode* p = (LTNode*)malloc(sizeof(LTNode));p->next = NULL;p->prev = NULL;p->val = x;return p;
}
//头插
void LTPushFront(LTNode* phead,LTDateType x)
{assert(phead);//为pcur申请内存LTNode* pcur = LTBuyNode(x);//pcur链接到头和下一个节点上pcur->next = phead->next;pcur->prev = phead;//修改头结点的next与下一个节点的prevent指针指向pcur->next->prev = pcur;pcur->prev->next = pcur;
}
//尾插
void LTPushBack(LTNode* phead, LTDateType x)
{assert(phead);//为pcur申请内存LTNode* pcur = LTBuyNode(x);//修改pcur指针指向pcur->next = phead;pcur->prev = phead->prev;//pcur->next->prev = pcur;pcur->prev->next = pcur;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next!=phead);LTNode* pdel = phead->next;//链接前后两个节点phead->next = pdel->next;pdel->next->prev = phead;//删除pdelfree(pdel);pdel = NULL;
}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* pdel = phead->prev;phead->prev = pdel->prev;pdel->prev->next = phead;free(pdel);pdel = NULL;
}
//pos前插
void LTInsert(LTNode* pos, LTDateType x)
{LTPushBack(pos, x);
}
//pos后插
void LTInsertAfter(LTNode* pos, LTDateType x)
{LTPushFront(pos, x);
}
//删pos
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
//删pos后
void LTEraseAfter(LTNode* pos)
{LTPopFront(pos);
}
//查找
LTNode* LTFind(LTNode* phead, LTDateType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur!= phead){if (pcur->val == x){return pcur;}pcur = pcur->next;}return NULL;
}
//打印链表
void LTPrint(LTNode* phead)
{assert(phead);printf("phead");LTNode* pcur = phead->next;while (pcur != phead){printf("->%d", pcur->val);pcur = pcur->next;}printf("\n");}
//销毁链表
void LTDestroy(LTNode* phead)
{LTNode* pcur = phead->next;LTNode* pdel = pcur;while (pcur != phead){pdel = pcur;pcur = pcur->next;free(pdel);}free(pcur);//出了函数后记得把phead置空
}

4.书写要点总结说明

4.1为什么要使用一级指针

我们可以回顾一下，在编写单链表的时候，函数的形参使用的都是二级指针

那么同是链表，为什么单链表使用二级指针，但是双向链表就可以用一级指针了呢？

对于单链表为什么使用二级指针可以回顾博主之前的单链表博客

对于双向链表：

区别于单链表，双向链表有一个哨兵位，哨兵位不存储有效数据，也就是说，对于链表的增删查改都不改变哨兵位，真正会改变的是哨兵位head的head->prev和head->next，而这两者虽是链表节点指针，但却使head指向的结构体里面的成员，改变成员的话，传入结构体的地址，即传入一个指向成员对应的结构体的指针就足够了。

双向链表中唯一需要改变head指向的操作时销毁链表操作，因为销毁链表后需要将head指向NULL。然而，为了保持函数传入接口的统一（为了方便记忆），所以我们把销毁操作传入指针也设置为一级指针，不过要注意在函数结束后要手动将head置空，防止野指针的出现。

4.2三个使用到的嵌套调用

其实代码不一定要这样去写，只是博主单纯觉得这样写更加简单明了。

由于双向链表是一个循环的链表，所以在进行插入删除操作时，不用担心会出现对空指针解引用的现象。也就是说，相比于单链表，双向链表的头结点也可以成为中间节点，中间节点也可以看做头结点（但注意不能改变head指向），所以博主进行了一下操作：

pos前插调用尾插：尾插是在head前面插入元素，那么将传入指针改为pos后，尾插也能实现在pos前插入元素。
pos后插调用头插：头插是在head后，第一个有效节点前插入元素，那么将传入指针改为pos后，头插也能实现在pos后插入元素。
pos后删调用头删：头删是删除head后的第一个节点，pos后删也是删除pos后的第一个节点，所以调用头删也能实现该功能。

4.3相对于单链表书写的不同

单链表的相关函数传参传的是二级指针；双向链表传的是一级指针。
单链表中，指针解引用访问next是需要考虑空指针的情况（尾插、尾删、pos前插，删pos）；双向链表由于是循环结构，故不管访问到第几个next或prev，都不会遇到空指针，所以不需要考虑空指针解引用的情况。
销毁链表后：单链表中不用再对头指针置空（传入二级指针，函数内部可进行置空）；双向链表中销毁链表后需要再对头指针置空（传入一级指针，函数内部无法改变传入指针指向）。
单链表中所有不在头节点的操作（除了删除pos后节点）都需要遍历链表找到要操作的节点；双向链表不需要遍历，直接通过传入节点就可以找到前后节点。