前面我们已经学完了单向链表，知道了单向链表如何进行增删查改等基本功能，而今天，我们将要学习双向链表。
目录
回忆上次学习的单向链表结构图：
下面还要详细的介绍一下各种链表示意图，上期遗漏了这部分内容
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是以下两种结构：
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向 循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了，后面我们代码实现了就知道了。
由于上期我们已经学完了无头单向非循环链表，因此这期我们来学习带头双向循环链表。
和单向链表一样，双向链表每个节点都是由结构体组成的数据类型，但是双向链表结构体中增加了一个指向前一个节点的指针。
typedef int LTDataType; //方便修改数据类型
typedef struct ListNode
{
struct ListNode* next;//指向下一个节点的指针
struct ListNode* prev;//指向前一个节点的指针
LTDataType data; //存储的数据
}LTNode;我们今天要将的是带哨兵卫头节点的双向循环链表，它的头节点不存储有效数据，头节点中的prev指针指向最后一个节点
当链表为空时，指针的指向关系图：
下面是双向链表中经常要用到的一些接口函数：
//初始化
LTNode* ListInit();
//打印
void printList(LTNode* phead);
//尾插
void ListPushBack(LTNode* phead, LTDataType x);
//头插
void ListPushFront(LTNode* phead, LTDataType x);
//尾删
void ListPopBack(LTNode* phead);
//头删
void ListPopFront(LTNode* phead);
//判断链表是否为空
bool ListEmpty(LTNode* phead);
//在pos位置前插入x
void ListInsert(LTNode* pos, LTDataType x);
//删除pos位置节点
void ListErase(LTNode* pos);
//求链表长度
int ListSize(LTNode* phead);
//销毁
void ListDestory(LTNode* phead);函数使用malloc动态分配了一个 LTNode类型的内存空间，用node进行接收。同时要检查内存分配是否成功，将新节点中的data赋值为传入的数据x，将新节点的next和prev指针都设置为NULL,最后返回新节点的地址。
//创建新节点
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->data = x;
node->next = NULL;
node->prev = NULL;
return node;
}
初始化链表就是给链表创建一个头节点，这里需要使用到上面介绍完的创建新节点BuyListNode函数，因为头节点不存储有效数据，所以我们将data赋值为-1，同时头节点中的next和prev都指向自己，最后返回头节点的地址。
LTNode* ListInit()
{
LTNode* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}双向链表的打印和单向链表类似，注意循环的截止条件不是cur为空，而当当cur重新指向头节点的时候停止循环。因为最后一个节点的next指针指向的是头节点。
//打印
void printList(LTNode* phead)
{
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
普通的方法是创建一个新的节点插入到链表的尾部，当然还有更为简单的方法，就是调用一下我们后面要讲到的 ListInsert 函数，这个函数可以在指定位置前插入一个节点并存储有效数据。如果这个指定位置是头节点的位置，那么头节点的前一个位置就是链表最后一个节点所在的位置。
下面介绍一下普通的方法吧：
将最后一个节点命名为tail，然后根据上图修改一下phead ， tail ， newNode之间的指向关系即可
//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
/*
//可以直接调用void ListInsert来实现
ListInsert(phead , x);
//代码复用
*/
LTNode* newNode = BuyListNode(x);
LTNode* tail = phead->prev;
newNode->next = phead;
newNode->prev = tail;
tail->next = newNode;
phead->prev = newNode;
}
这里也可以使用两种方法来实现，普通方法是找到最后一个节点，修改指向关系，再释放掉最后一个节点的空间。简单的方法是调用一个可以删除指定位置节点的函数ListErase，将最后一个节点的位置传入到这个函数就可以进行尾删，（最后一个节点的位置是phead->prev）这个函数下面也将会给大家介绍到。
普通方法：
将最后一个节点命名为tail，倒数第二个节点命名为tailPrev，按上图修改它们的指向关系即可。
为了防止出现尾删空链表的情况出现，我们需要使用一个ListEmpty函数来判断链表是否为空，同时使用assert断言，一旦链表为空，用户仍然使用尾删程序就会报错。头删同理如此。
//尾删
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(ListEmpty(phead));
/*
//可以复用ListErase函数来实现后面的代码
ListErase(phead->prev);
*/
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
phead->prev = tailPrev;
tailPrev->next = phead;
free(tail);
}这里也可使用两种方法，我们介绍一下普通的方法：
将头节点的后一个节点命名为pheadNext，然后将newNode插入到phead和pheadNext之间即可。
//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
/*
//可以直接调用void ListInsert来实现
ListInsert(phead->next , x);
//代码复用
*/
LTNode* newNode = BuyListNode(x);
LTNode* pheadNext = phead->next;
phead->next = newNode;
newNode->prev = phead;
newNode->next = pheadNext;
pheadNext->prev = newNode;
}这里也可使用两种方法，我们介绍一下普通的方法：
//头删
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(ListEmpty(phead));
/*
//可以复用ListErase函数来实现后面的代码
ListErase(phead->next);
*/
LTNode* next = phead->next;
phead->next = next->next;
next->next->prev = phead;
free(next);
}直接将pos的前一个节点命名为prev，再将newNode插入。
//在pos位置前插入x
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newNode = BuyListNode(x);
prev->next = newNode;
newNode->prev = prev;
newNode->next = pos;
pos->prev = newNode;
}
将pos前一个节点命名为prev,后一个节点命名为next,这样命名方便我们修改指针的指向。然后按照上图修改指针即可。
//删除pos位置节点
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}这里使用的方法是遍历整个链表。
//求链表长度
int ListSize(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
int size = 0;
while (cur != phead)
{
++size;
cur = cur->next;
}
return size;
}这一步可以复用删除pos位置节点的函数ListErase，我们只要将链表的每一个节点地址都传入到这个函数，就可销毁链表。当然，最后也要将头节点给释放销毁。
//销毁
void ListDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
ListErase(cur);
cur = next;
}
free(phead);
}| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连 续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 任意位置插入或者删除元 素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩 容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
顺序表优点：下标随机访问，cpu高速缓存命中率高
顺序表缺点：头部或者中间插入删除效率低，扩容有一定程度性能消耗，可能存在一定程度空间浪费。
链表优点：任意位置插入删除O(1)复杂度，按需申请释放。
链表缺点：不支持下标随机访问。
头文件： 存放函数声明部分
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int LTDataType; //方便修改数据类型
typedef struct ListNode
{
struct ListNode* next;//指向下一个节点的指针
struct ListNode* prev;//指向前一个节点的指针
LTDataType data; //存储的数据
}LTNode;
//初始化
LTNode* ListInit();
//打印
void printList(LTNode* phead);
//尾插
void ListPushBack(LTNode* phead, LTDataType x);
//头插
void ListPushFront(LTNode* phead, LTDataType x);
//尾删
void ListPopBack(LTNode* phead);
//头删
void ListPopFront(LTNode* phead);
//判断链表是否为空
bool ListEmpty(LTNode* phead);
//在pos位置前插入x
void ListInsert(LTNode* pos, LTDataType x);
//删除pos位置节点
void ListErase(LTNode* pos);
//求链表长度
int ListSize(LTNode* phead);
//销毁
void ListDestory(LTNode* phead);List.c文件 存放函数定义
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//创建新节点
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->data = x;
node->next = NULL;
node->prev = NULL;
return node;
}
//初始化
LTNode* ListInit()
{
LTNode* phead = BuyListNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
//判断链表是否为空
bool ListEmpty(LTNode* phead)
{
assert(phead);
return phead->next != phead;
}
//打印
void printList(LTNode* phead)
{
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
/*
//可以直接调用void ListInsert来实现
ListInsert(phead , x);
//代码复用
*/
LTNode* newNode = BuyListNode(x);
LTNode* tail = phead->prev;
newNode->next = phead;
newNode->prev = tail;
tail->next = newNode;
phead->prev = newNode;
}
//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
/*
//可以直接调用void ListInsert来实现
ListInsert(phead->next , x);
//代码复用
*/
LTNode* newNode = BuyListNode(x);
LTNode* pheadNext = phead->next;
phead->next = newNode;
newNode->prev = phead;
newNode->next = pheadNext;
pheadNext->prev = newNode;
}
//尾删
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(ListEmpty(phead));
/*
//可以复用ListErase函数来实现后面的代码
ListErase(phead->prev);
*/
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
phead->prev = tailPrev;
tailPrev->next = phead;
free(tail);
}
//头删
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(ListEmpty(phead));
/*
//可以复用ListErase函数来实现后面的代码
ListErase(phead->next);
*/
LTNode* next = phead->next;
phead->next = next->next;
next->next->prev = phead;
free(next);
}
//在pos位置前插入x
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* newNode = BuyListNode(x);
prev->next = newNode;
newNode->prev = prev;
newNode->next = pos;
pos->prev = newNode;
}
//删除pos位置节点
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
//求链表长度
int ListSize(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
int size = 0;
while (cur != phead)
{
++size;
cur = cur->next;
}
return size;
}
//销毁
void ListDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
ListErase(cur);
cur = next;
}
free(phead);
}
test.c文件 用于测试接口函数正确性
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//尾插测试
void ListTest1()
{
LTNode* plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPushBack(plist, 5);
printList(plist);
}
//头插测试
void ListTest2()
{
LTNode* plist = ListInit();
ListPushFront(plist, 1);
ListPushFront(plist, 2);
ListPushFront(plist, 3);
ListPushFront(plist, 4);
ListPushFront(plist, 5);
printList(plist);
}
//尾删测试
void ListTest3()
{
LTNode* plist = ListInit();
ListPushFront(plist, 1);
ListPushFront(plist, 2);
ListPushFront(plist, 3);
ListPushFront(plist, 4);
ListPushFront(plist, 5);
printList(plist);
ListPopBack(plist);
ListPopBack(plist);
ListPopBack(plist);
ListPopBack(plist);
printList(plist);
}
//头删测试
void ListTest4()
{
LTNode* plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPushBack(plist, 5);
printList(plist);
ListPopFront(plist);
ListPopFront(plist);
ListPopFront(plist);
ListPopFront(plist);
printList(plist);
}
void ListTest5()
{
LTNode* plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPushBack(plist, 5);
printList(plist);
ListDestory(plist);
//printList(plist);
}
int main()
{
//ListTest1();
ListTest1();
return 0;
}