【数据结构】双链表

大家好！今天我们来学习数据结构中的双链表。（我们这里讲解的是带头（哨兵位）双向循环链表哦~）

目录

1.双链表的概念

2. 双链表的逻辑结构

3. 双链表的定义

4. 双链表的接口实现

4.1 动态申请一个新结点

4.2 双链表的初始化

4.3 打印双链表

4.4 尾插数据

4.5 尾删数据

4.6 头插数据

4.7 头删数据

4.8 获得双链表的长度

4.9 查找指定数据

4.10 在指定位置之前插入数据

4.11 删除指定位置

4.12 销毁双链表

5. 双链表的完整代码

5.1 List.h

5.2 List.c

5.3 Test.c

6. 顺序表和链表的区别

7. 总结

---

1.双链表的概念

双链表也叫双向链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

2. 双链表的逻辑结构

我们这里以带头双向循环链表为例，它的逻辑结构如下：

​

3. 双链表的定义

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;  //存储的数据struct ListNode* prev;  //存放前一个结点的地址struct ListNode* next;  //存放后一个结点的地址
}LTNode;

使用结构体创建一个双链表。

用SLTDataType替换int，方便对不同类型的数据进行修改。

用SLTNode替换struct SListNode，方便简洁。

data是结点的数据域，*prev用来存放前一个结点的地址（前驱），*next用来存放后一个结点的地址（后继）。

4. 双链表的接口实现

双链表的所有接口函数一览：

//动态申请一个新结点
LTNode* BuyLTNode(LTDataType x);
//双链表的初始化
LTNode* LTInit();
//打印双链表
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//获得双链表的长度
int LTSize(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之前插入x
void LTInsert(LTNode* pos,LTDataType x);
//删除pos位置
void LTErase(LTNode* pos);
//销毁双链表
void LTDestroy(LTNode* phead);

这些接口函数主要实现了单链表的增删改查等功能，接下来我们一一实现这些函数！

4.1 动态申请一个新结点

我们每次给链表插入数据时，都需要动态开辟空间申请结点。所以我们将这个过程封装成函数，方便后续使用。

我们使用malloc()函数动态开辟一块空间表示新结点newnode，malloc函数返回一个void*类型的指针，指向分配的内存块的起始位置。如果内存分配失败，则返回一个空指针NULL。

所以我们要判断newnode是否为空指针NULL，如果newnode是空指针，则用perror()函数打印相关错误，并用exit(-1)退出程序。

如果newnode不为空，我们就用newnode的data赋值。又因为这是新开辟的结点，我们暂时将newnode的prev和newnode的next指向空。

//动态申请一个新结点
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode *)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

4.2 双链表的初始化

双链表的初始化，就是给双链表创建一个头结点。因为头结点（哨兵位）不存储有效数据，所以我们将头结点的data赋值为-1,同时让头结点的prev和next都指向自己，最后返回头结点的地址。

//双链表的初始化
LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

4.3 打印双链表

遍历双链表，依次打印双链表的元素。

我们定义一个结构体类型的指针cur，让cur一开始指向头结点的下一个结点（也就是哨兵位后面的一个结点）。当cur不为空时，输出cur指向的结点的值（cur->data），然后让cur指向下一个结点（cur=cur->next），依次进行，直到cur为头结点时停止（因为最后一个结点的next指针指向头结点）。

//打印双链表
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("phead<=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}

4.4 尾插数据

尾插，就是创建一个新结点newnode，然后将newnode插入到尾结点tail的后面，让tail的next指向newnode,让newnode的prev指向tail；让newnode的next指向头结点phead，头结点phead的prev指向newnode。建立这样的连接后，尾插就完成了

​

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

4.5 尾删数据

尾删，我们需要定义一个tailPrev存储尾结点tail的前一个结点（也就是tail->prev），再free掉tail，让tailPrev的next指向头结点phead，让头结点phead的prev指向tailPrev。

这里要注意的是，如果链表为空（phead->next==phead），我们就不能进行尾删，所以我们要用assert()进行断言。

​

//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next!= phead); //链表为空的情况LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;
}

4.6 头插数据

所谓头插，就是在双链表的头结点（哨兵位）后面的一个结点前插入数据。我们调用BuyLTNode()函数创建一个新结点newnode，让newnode的next指向头结点phead的next，头结点phead的next的prev指向newnode；让头结点phead的next指向newnode，newnode的prev指向phead。

​

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

4.7 头删数据

头删，就是将头结点（哨兵位）后面的那一个结点删除。这里我们可以用first存储头结点（哨兵位）后面的第一个结点，用second存储哨兵位后面的第二个结点。然后free掉first。将头结点phead的next指向second，而second的prev指向头结点。

这里也要注意，如果链表为空（phead->next==phead），我们就不能进行头删，所以我们要用assert()进行断言。

​ 

//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);  //链表为空的情况LTNode* first = phead->next;LTNode* second = phead->next->next;free(first);phead->next = second;second->prev = phead;
}

4.8 获得双链表的长度

要获得双链表的长度，我们就使用cur从头结点（哨兵位）的后一个结点开始遍历，直到cur等于头结点phead时停止。

//获得双链表的长度
int LTSize(LTNode* phead)
{assert(phead);int size = 0;LTNode* cur = phead->next;while (cur != phead){++size;cur = cur->next;}return size;
}

4.9 查找指定数据

定义一个结构体指针cur，让cur首先指向头结点（哨兵位）的下一个结点，然后遍历双链表，如果找到了指定数据（cur->data==x)，就直接返回cur。否则让cur指向cur->next，直到cur为头结点时停止。如果没有提前退出，完整完成了整个循环（也就是没有找到指定数据），就返回空指针NULL。

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

4.10 在指定位置之前插入数据

我们调用BuyLTNode()函数创建一个新结点newnode，定义一个结构体指针posPrev用来保存pos位置的前一个位置，让posPrev的next指向newnode，newnode的prev指向posPrev；让newnode的next指向pos，pos的prev指向newnode。

既然我们要在指定位置之前插入数据，那么这个指定位置必须是存在的，所以我们要使用assert()断言。

​

//在pos位置之前插入x
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyLTNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}

4.11 删除指定位置

我们要删除指定位置，可以定义一个结构体指针posPrev保存要删除位置的前一个位置，定义一个结构体指针posNext保存要删除位置的后一个位置。然后free掉pos，让posPrev的next指向posNext，让posNext的prev指向posPrev。

既然要删除指定位置，那么这个指定位置也必须是存在的，这里也同样要用assert()断言。

​

//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

4.12 销毁双链表

我们先让cur指向头结点（哨兵位）的下一个结点，然后遍历双链表，定义一个结构体指针next用来保存遍历时每一个结点的后面一个结点，依次free每个结点，然后让cur指向next，直到cur指向头结点时停止。

最后将头结点（哨兵位）phead释放。

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

5. 双链表的完整代码

5.1 List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
typedef struct ListNode
{LTDataType data;  //存储的数据struct ListNode* prev;  //指向前一个结点的指针struct ListNode* next;  //指向后一个结点的指针
}LTNode;//动态申请一个新结点
LTNode* BuyLTNode(LTDataType x);
//双链表的初始化
LTNode* LTInit();
//打印双链表
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//获得双链表的长度
int LTSize(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之前插入x
void LTInsert(LTNode* pos,LTDataType x);
//删除pos位置
void LTErase(LTNode* pos);
//销毁双链表
void LTDestroy(LTNode* phead);

5.2 List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"//动态申请一个新结点
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode *)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}//双链表的初始化
LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}//打印双链表
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("phead<=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next!= phead); //链表为空的情况LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);  //链表为空的情况LTNode* first = phead->next;LTNode* second = phead->next->next;free(first);phead->next = second;second->prev = phead;
}//获得双链表的长度
int LTSize(LTNode* phead)
{assert(phead);int size = 0;LTNode* cur = phead->next;while (cur != phead){++size;cur = cur->next;}return size;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}//在pos位置之前插入x
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyLTNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}//删除pos位置
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}//销毁双链表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

5.3 Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"void TestList()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);LTPushFront(plist, 10);LTPushBack(plist, 10);LTPrint(plist);LTPopBack(plist);LTPopFront(plist);LTPrint(plist);LTPushFront(plist, 10);LTPushFront(plist, 20);LTPushFront(plist, 30);LTPushFront(plist, 40);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTDestroy(plist);plist = NULL;
}

​

6. 顺序表和链表的区别

​

存储器层次结构：

​

顺序表

优点：下标随机访问，cpu高速缓存命中率高

缺点：头部和中间插入删除效率低，扩容有一定程度性能消耗，可能存在一定程度的空间浪费。

链表

优点：可以任意位置插入删除，复杂度O(1)，能够按需申请释放。

缺点：不支持下标随机访问。

7. 总结

到这里，我们就用C语言实现了数据结构中的双链表。有什么问题欢迎在评论区讨论。如果觉得文章有什么不足之处，可以在评论区留言。如果喜欢我的文章，可以点赞收藏哦！