AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】双链表

2024-07-09 38
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构中的双链表

​

1. 双链表的概念

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

2. 双链表的逻辑结构

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

我们从中也可以发现，双链表相比单链表的优势是方便找某一个结点的前一个结点。

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。建立这样的连接后，尾插就完成了
image.png

//尾插
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()进行断言。
image.png

//尾删
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。
image.png

//头插
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()进行断言。
image.png

//头删
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()断言。
image.png

//在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()断言。
image.png

​

//删除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;
}

image.png

​

6. 顺序表和链表的区别

image.png
​
存储器层次结构：
image.png

​

顺序表

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

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

链表

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

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

7. 总结

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

​

文章标签：
存储
C语言
DataX
关键词：
数据结构链表
数据结构双链表
是基德吖
目录
相关文章
龙大吉
|
6天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
28 5
ephemerals__
|
29天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
55 4
肾透侧视攻城狮
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
22 2
肾透侧视攻城狮
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
32 2
小强在此
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
小强在此
26 7
GuGuStudy
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
GuGuStudy
26 3
java冯坚持
|
2月前
|
算法 Java
数据结构与算法学习五：双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现，并通过实例演示了双向链表的优势和应用。
java冯坚持
18 0
数据结构与算法学习五：双链表的增、删、改、查
ephemerals__
|
29天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
42 0
努力学习的小廉
|
2月前
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
努力学习的小廉
32 2
椰椰椰耶
|
2月前
|
存储 Java
【数据结构】链表
【数据结构】链表
椰椰椰耶
18 1