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

【数据结构】双链表

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

​

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
关键词：
数据结构链表
数据结构双链表
是基德吖
目录
相关文章
百色彭于晏
|
4天前
|
存储 C语言
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
百色彭于晏
22 0
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
是基德吖
|
1月前
【数据结构OJ题】环形链表
力扣题目——环形链表
是基德吖
26 3
【数据结构OJ题】环形链表
chian-ocean
|
11天前
【数据结构】双向带头（哨兵位）循环链表 —详细讲解（赋源码）
【数据结构】双向带头（哨兵位）循环链表 —详细讲解（赋源码）
chian-ocean
21 4
是基德吖
|
1月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
是基德吖
36 1
【数据结构OJ题】复制带随机指针的链表
是基德吖
|
1月前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
是基德吖
14 1
【数据结构OJ题】环形链表II
是基德吖
|
1月前
【数据结构OJ题】相交链表
力扣题目——相交链表
是基德吖
18 1
【数据结构OJ题】相交链表
是基德吖
|
1月前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
是基德吖
29 8
【数据结构OJ题】合并两个有序链表
是基德吖
|
1月前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
是基德吖
31 2
【数据结构OJ题】移除链表元素
是基德吖
|
1月前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
是基德吖
23 1
【数据结构OJ题】链表中倒数第k个结点
国中之林
|
3天前
|
算法
【数据结构与算法】共享双向链表
【数据结构与算法】共享双向链表
国中之林
4 0