目录
前言
双链表节点定义
接口函数实现
初始化函数
创建节点
打印双链表
尾插节点
尾删节点
头插节点
头删节点
指定位置前插入
删除指定位置节点
改写插入删除
判断链表是否为空
计算链表长度
销毁链表
双链表完整代码
浅谈链表及顺序表
前言
前面我们已经实现了无头单向非循环链表，现在我们来实现带头双向循环链表。
双链表节点定义
//双链表节点定义
typedef int LDataType;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LDataType data;
}LNode;与单链表不同的是，在实现双链表时，我们需要创建一个初始化函数。双链表的初始化需要一个头节点，并且这个头节点的prev指针和next指针需要指向自身。
接口函数实现
初始化函数
初始化函数创建了一个头节点（哨兵卫），这个哨兵卫不储存值，并且让它的prev、next指向自身。这样就形成了一个闭环。
//初始化双链表
LNode* LInit()
{LNode* newnode = (LNode*)malloc(sizeof(LNode));if (newnode == NULL){perror("malloc fail");exit(-1);}//prev与next均指向自身newnode->next = newnode;newnode->prev = newnode;return newnode;
}
与单链表的实现类似，我们同样也实现两个函数用来检测和辅助其他函数的实现。
创建节点
//创建节点、
LNode* BuyListNode(LDataType x)
{LNode* newnode = (LNode*)malloc(sizeof(LNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;//创建后的节点prev与next均指向NULLnewnode->next = NULL;newnode->prev = NULL;return newnode;
}新创建的节点的prev与next指针我们让他们指向NULL就可以了，因为后面我们还会处理它的链接关系，所以指向空指针就可以了。
打印双链表
//打印双链表
void LPrint(LNode* phead)
{assert(phead);LNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}PS：
打印链表信息之所以从phead->next开始是因为我们的phead并没有存值，链表的节点信息是从phead->next开始的。
尾插节点
//尾插节点
void LPushBack(LNode* phead,LDataType x)
{//防止传入空指针assert(phead);//先将x存入创建的节点中LNode* newnode = BuyListNode(x);//链表最后一个节点就是phead的prev指针LNode* tail = phead->prev;//将newnode节点链接到链表中tail->next = newnode;phead->prev = newnode;newnode->next = phead;newnode->prev = tail;
}
可能会有人会问，为什么双链表在尾插的时候传的参数是一级指针啊？单链表在尾插节点的的时候传的就是二级指针。那是因为我们现在实现的双链表具有头节点（哨兵卫），正是因为有了它，我们就不用传二级指针了。为什么了，前面我们讲过，单链表之所以传入的是二级指针。那是因为在特殊情况下我们的第一个节点会变成空指针。有哨兵卫后就不同了，假如我们现在双链表中只存在一个节点，我们将它删除，只需要将phead的prev与next均指向自身就可以了，而如果没有哨兵卫，我们就要将phead置成空指针，这样传入的参数就改变了，那么就需要传二级指针。
其实就一点，如果链表有哨兵卫的话就直接传入一级指针就可以了。
尾删节点
//尾删节点
void LPopBack(LNode* phead)
{assert(phead);//防止传入的链表是一个空链表assert(phead->prev != phead);LNode* tail = phead->prev;LNode* tailPrev = tail->prev;//每个节点都是动态开辟出来的，记得释放free(tail);phead->prev = tailPrev;tailPrev->next = phead;
}
头插节点
//头插节点
void LPushFront(LNode* phead, LDataType x)
{assert(phead);LNode* newnode = BuyListNode(x);LNode* first = phead->next;phead->next = newnode;first->prev = newnode;newnode->prev = phead;newnode->next = first;
}
头删节点
//头删节点
void LPopFront(LNode* phead)
{assert(phead);//防止链表为空assert(phead->next != phead);LNode* first = phead->next;LNode* newfirst = first->next;free(first);phead->next = newfirst;newfirst->prev = phead;
}
指定位置前插入
//指定位置前插入
void LInsert(LNode* pos, LDataType x)
{assert(pos);LNode* newnode = BuyListNode(x);LNode* posPrev = pos->prev;newnode->next = pos;pos->prev = newnode;posPrev->next = newnode;newnode->prev = posPrev;
}
删除指定位置节点
//删除指定位置节点
void LErase(LNode* pos)
{assert(pos);LNode* posNext = pos->next;LNode* posPrev = pos->prev;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}
改写插入删除
有了删除指定位置节点函数和指定位置前插入函数，我们就可以改写尾插尾删、头插头删函数。
//尾插节点
void LPushFront(LNode* phead, LDataType x)
{LInsert(phead, x);
}
//尾删节点
void LPopBack(LNode* phead)
{LErase(phead->prev);
}
//头插节点
void LPushFront(LNode* phead, LDataType x)
{LInsert(phead->next, x);
}
//头删节点
void LPopFront(LNode* phead)
{LErase(phead->next);
}判断链表是否为空
//判断链表是否为空
bool LIsEmpty(LNode* phead)
{assert(phead);return phead == phead->next;
}计算链表长度
//计算链表长度
int LSize(LNode* phead)
{int count = 0;LNode* cur = phead->next;while (cur != phead){count++;cur = cur->next;}return count;
}销毁链表
//销毁链表
void LDestroy(LNode* phead)
{assert(phead);LNode* cur = phead->next;//将每个节点都释放while (cur != phead){LNode* next = cur->next;free(cur);cur = next;}//自己手动将phead置为空指针free(phead);
}双链表完整代码
List.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <stdbool.h>typedef int LDataType;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LDataType data;
}LNode;//初始化双链表
LNode* LInit();//打印双链表
void LPrint(LNode* phead);//创建一个节点
LNode* BuyListNode(LDataType x);//尾插尾删
void LPushBack(LNode* phead, LDataType x);
void LPopBack(LNode* phead);//头插头删
void LPushFront(LNode* phead, LDataType x);
void LPopFront(LNode* phead);//在指定位置前插入，删除指定位置
void LErase(LNode* pos);
void LInsert(LNode* pos, LDataType x);//销毁链表
void LDestroy(LNode* phead);//判断链表是否为空
bool LIsEmpty(LNode* phead);//计算链表节点个数
size_t LSize(LNode* phead);List.c
#include "List.h"LNode* LInit()
{LNode* newnode = (LNode*)malloc(sizeof(LNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->next = newnode;newnode->prev = newnode;return newnode;
}LNode* BuyListNode(LDataType x)
{LNode* newnode = (LNode*)malloc(sizeof(LNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}void LPushBack(LNode* phead,LDataType x)
{assert(phead);LNode* newnode = BuyListNode(x);LNode* tail = phead->prev;tail->next = newnode;phead->prev = newnode;newnode->next = phead;newnode->prev = tail;//LInsert(phead, x);
}void LPopBack(LNode* phead)
{assert(phead);assert(phead->prev != phead);LNode* tail = phead->prev;LNode* tailPrev = tail->prev;free(tail);phead->prev = tailPrev;tailPrev->next = phead;//LErase(phead->prev);
}void LPrint(LNode* phead)
{assert(phead);LNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}void LPushFront(LNode* phead, LDataType x)
{assert(phead);LNode* newnode = BuyListNode(x);LNode* first = phead->next;phead->next = newnode;first->prev = newnode;newnode->prev = phead;newnode->next = first;//LInsert(phead->next, x);
}void LPopFront(LNode* phead)
{//assert(phead);//assert(phead->next != phead);//LNode* first = phead->next;//LNode* newfirst = first->next;//free(first);//phead->next = newfirst;//newfirst->prev = phead;LErase(phead->next);
}LNode* LFind(LNode* phead, LDataType x)
{assert(phead);LNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void LErase(LNode* pos)
{assert(pos);LNode* posNext = pos->next;LNode* posPrev = pos->prev;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}void LInsert(LNode* pos, LDataType x)
{assert(pos);LNode* newnode = BuyListNode(x);LNode* posPrev = pos->prev;newnode->next = pos;pos->prev = newnode;posPrev->next = newnode;newnode->prev = posPrev;
}void LDestroy(LNode* phead)
{assert(phead);LNode* cur = phead->next;while (cur != phead){LNode* next = cur->next;free(cur);cur = next;}//自己手动置为空指针free(phead);
}bool LIsEmpty(LNode* phead)
{assert(phead);return phead == phead->next;
}int LSize(LNode* phead)
{int count = 0;LNode* cur = phead->next;while (cur != phead){count++;cur = cur->next;}return count;
}浅谈链表及顺序表
链表和顺序表都作为线性表，他们之间有何异同呢？如以下表格：
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，物理空间上不一定连续 |
| 随机访问 | 支持 O(1) | 不支持 O(N) |
| 任意位置插入和删除元素 | 可能需要搬移元素，效率低；O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
以上就是双链表实现的全部内容了，希望能够帮助到大家。如果有不对的地方请各位大佬在评论区指正（鞠躬）。
