0
0

数据结构：线性表之-循环双向链表(万字详解)

本文将以写代码思路进行讲述，故中间会出现代码的优化以便梳理思路，渐入佳境

本文分成三个文件：

List.h//函数的声明
List.c//函数的创建
test.c //用于测试文件

基本概念

1，什么是双向链表

双向链表（Doubly Linked List）是一种常见的链表数据结构。它与普通链表的区别在于，每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点，因此可以从任意一个节点开始，双向遍历整个链表。

双向链表的节点通常由三部分组成：数据部分（存储节点的值）、前驱指针（指向前一个节点的指针）和后继指针（指向后一个节点的指针）。相比于单向链表，双向链表可以更方便地进行正反向遍历和节点的插入、删除操作。

双向链表的优点是在某些特定场景下可以更高效地操作链表，缺点是相比于单向链表，需要额外的空间来存储每个节点的前驱指针。

继续遍历一下双向链表的特点和操作：

  1. 特点：- 双向链表每个节点有两个指针，可以向前或向后遍历。- 可以从任意节点开始向前或向后遍历整个链表。- 插入和删除节点的操作相对容易，只需要调整节点的前驱和后继指针即可。- 对于双向链表，可以更轻松地实现双向循环链表，即首尾节点相连。
  2. 常见操作：- 遍历链表：可以从头节点开始，按照后继指针依次访问每个节点。或者从尾节点开始，按照前驱指针依次访问每个节点。- 插入节点：在给定位置之前或之后插入一个新节点，只需要调整前后节点的指针即可。- 删除节点：删除给定位置上的节点，同样通过调整前后节点的指针来实现。- 查找节点：可以通过遍历链表来查找特定值或者特定位置上的节点。

注意：在使用双向链表时需要注意指针的正确性和更新，以避免出现指针丢失和内存泄漏等问题。

2，与单向链表的区别

双向链表与单向链表的主要区别在于节点中指针的个数和指向方式：

1. 指针个数：双向链表每个节点有两个指针，分别指向前一个节点和后一个节点；而单向链表每个节点只有一个指针，指向下一个节点。
2. 遍历方式：双向链表可以从任意节点开始向前或向后遍历整个链表，而单向链表只能从头节点开始顺序遍历。
3. 插入和删除操作：双向链表的插入和删除操作相对方便，因为可以直接调整前驱和后继节点的指针；而单向链表在进行插入和删除时，需要更多的操作来调整节点之间的链接关系。
4. 空间占用：双向链表相较于单向链表需要额外的空间来存储每个节点的前驱指针。这在一些特定场景下可能会带来一定的开销。
5. 双向性：双向链表可以在节点内部通过前驱指针和后继指针来实现双向的遍历和操作。这使得在某些场景下，双向链表更加方便和高效，例如需要反向遍历链表或者需要在给定节点处进行插入和删除操作。
6. 双向循环性：双向链表可以通过连接首尾节点的前驱和后继指针来形成一个双向循环链表。这使得链表在某些场景下更具灵活性，例如需要循环遍历链表或者实现循环队列等。
7. 内存占用：相对于单向链表，每个节点额外存储一个前驱指针和一个后继指针，使得双向链表在存储上需要更多的内存空间。这是一个需要考虑的因素，尤其是在链表节点数量较大或内存有限的情况下。
8. 双向链表的前向遍历与后向遍历：由于双向链表具有前驱和后继指针，可以方便地进行正向和反向的遍历操作。而单向链表只能从头节点开始进行顺序遍历，无法直接进行反向遍历。
9.  删除操作的效率：相对于单向链表，在双向链表中删除给定节点的效率更高。由于双向链表可以直接通过前驱和后继指针找到目标节点的前后节点，所以删除操作只需要修改前后节点的指针即可，而单向链表需要遍历找到目标节点的前一个节点，才能进行删除操作。
10.  双向链表支持双向迭代器：由于双向链表具有双向性，可以轻松地实现双向迭代器。这使得在某些情况下，可以更加方便地进行双向迭代操作，如双向搜索算法或需要反向遍历的数据结构。
总之，双向链表相较于单向链表具有更强的遍历和操作能力，但在存储上需要额外的空间开销。根据具体需求和场景的不同，选择适合的链表类型是根据实际情况进行权衡和取舍。

概述：

  1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。

单向链表(无头)详细讲解：# 数据结构：线性表之-单向链表(无头)

双向链表详解

功能展示：

typedef int LTDataType;
typedef struct ListNode
{
    struct ListNode* next;
    struct ListNode* prev;
    LTDataType data;
}LTNode;

LTNode* BuyListNode(LTDataType x);

//void ListInit(LTNode** pphead);
LTNode* ListInit();

//打印
void ListPrint(LTNode* phead);

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

//头插
void ListPushFront(LTNode* phead, LTDataType x);

//尾删
void ListPopBack(LTNode* phead);

//头删
void ListPopFront(LTNode* phead);

//判断链表是否被删空
bool ListEmptyLTNode(LTNode* phead);

//pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x);

//删除pos位置的节点
void ListErase(LTNode* pos);

//求链表长度
int ListSize(LTNode* phead);

//销毁链表
void ListDestory(LTNode* phead);

1. 定义链表

typedef struct ListNode
{
    struct ListNode* next;//下一节点
    struct ListNode* prev;//上一个节点
    LTDataType data;
}LTNode;

2，创建双向链表

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;
}

3，初始化链表

初始化链表使用哨兵位(头节点)前后指针存储的位置为phead本身。

LTNode* ListInit()
{
    LTNode* phead = BuyListNode(-1);
    phead->next = phead;
    phead->prev = phead;
}

当然用无返回值的函数用二级指针进行初始化，及后续的增删查改
这样会更麻烦，本文全程采用一级指针：

void ListInit(LTNode** pphead)
{
    *pphead = BuyListNode(-1);
    (*pphead)->next = *pphead;
    (*pphead)->prev = *pphead;
}

改变结构体要用结构体指针。
要改变结构体指针要用结构体指针的指针。

4,尾插

先让我们回顾下双向链表的结构：


与单链表的不同是：单链表要尾插时，要从头一次向后访问找到为节点再进行插入
，而双向链表要尾插在head前插入节点即为尾节点。

void ListPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);

    LTNode* newnode = BuyListNode(x);
    LTNode* tail = phead->prev;
    //前一个节点指向新节点
    tail->next = newnode;
    //新节点的prev指向上一个节点
    newnode->prev = tail;
    //新节点存放的下一节点为头节点
    newnode->next = phead;
    //头节点的prev存放新节点，方便尾插
    phead->prev = newnode;
}

5，头插

头部插入为head前一个节点

void ListPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    
    LTNode* newnode = BuyListNode(x);
    LTNode* next = phead->next;
//尾部标号对应图中步骤
    next->prev = newnode;  //1
    newnode->next = next;  //2
    newnode->prev = phead; //3
    phead->next = newnode; //4
//另一种写法
    //phead->next = newnode;
    //newnode->prev = phead;
    //newnode->next = next;
    //next->prev = newnode;
}

6，尾删

尾删即为删除head的前一个节点
切记不可先将head指向尾删节点NULL，否则有可能造成野指针。
还有一种情况，若链表已经被删空，则会出现错误，则应该对删空时进行提醒并终止程序：

判断链表是否被删空

bool ListEmptyLTNode(LTNode* phead)
{
    assert(phead);
    /*
        链表返回只剩头节点(链表已经被删空)为真
        否则为假
    */
    return phead->next == phead;
}

尾删代码

void ListPopBack(LTNode* phead)
{
    assert(phead);
    //判断链表是否被删空：为真即为假，为假即为真
    assert(!ListEmptyLTNode(phead));//assert(phead->next != phead);

    //head的前一个即为尾巴
    LTNode* tail = phead->prev;//head前一个节点
    LTNode* tailPrev = tail->prev;//tail的前一个节点

    free(tail);//删除节点

    //重新链接新尾节点
    tailPrev->next = phead;
    phead->prev = tailPrev;
}

7，头删

void ListPopFront(LTNode* phead)
{
    assert(phead);
    assert(!ListEmptyLTNode(phead));

    LTNode* next = phead->next;
    LTNode* nnext = next->next;

    free(next);//删除节点

    phead->next = nnext;
    nnext->prev = phead;
}

8,pos位置之前插入

void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);

    LTNode* prev = pos->prev;
    LTNode* newnode = BuyListNode(x);

    //prev newnode pos
    prev->next = newnode;
    newnode->prev = prev;
    newnode->next = pos;
    pos->prev = newnode;
}

此时既然已经做到了可以任意位置插入，
那就可以对头插尾插进行复用，简化代码

优化后的头插

void ListPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);

    ListInsert(phead->next, x);
}

优化后的尾插

void ListPopBack(LTNode* phead)
{
    assert(phead);
    //判断链表是否被删空：为真即为假，为假即为真
    assert(!ListEmptyLTNode(phead));//assert(phead->next != phead);
    
    ListErase(phead->prev);
}

9,删除pos位置的节点

void ListErase(LTNode* pos)
{
    assert(pos);

    LTNode* prev = pos->prev;
    LTNode* next = pos->next;

    prev->next = next;
    next->prev = prev;

    free(pos);
}

此时既然已经做到了可以任意位置插入，
那就可以对头插尾插进行复用，简化代码

优化后的尾删

void ListPopBack(LTNode* phead)
{
    assert(phead);
    //判断链表是否被删空：为真即为假，为假即为真
    assert(!ListEmptyLTNode(phead));//assert(phead->next != phead);
    
    ListErase(phead->prev);
}

优化后的头删

void ListPopFront(LTNode* phead)
{
    assert(phead);

    assert(!ListEmptyLTNode(phead));

    ListErase(phead->next);
}

10,求链表长度

int ListSize(LTNode* phead)
{
    assert(phead);

    //跳过哨兵位
    LTNode* cur = phead->next;
    //求长度
    int size = 0;
    while (cur!=phead)
    {
        ++size;
        cur = cur->next;
    }
    //返回链表长度
    return size;
/*
    不要用头节点存储来计算长度，int符合但其他类型
    例如char，double 都会出现错误
*/
}

test.c中的调用方法：

    printf("存储的元素个数为：%d\n", ListSize(plist));
    //plist为主函数中创建的结构体

11,查找链元素

/*phead为原双链表，x表示被查找元素*/
int ListFind(LTNode* phead, LTDataType x)
{
    assert(phead);

    /*新建一个指针t，初始化为头指针 head*/
    LTNode* temp = phead->next;
    int i = 1;
    while (temp!=phead)
    {
        if (temp->data == x)
        {
            return i;
        }
        i++;
        temp = temp->next;
    }
    /*程序执行至此处，表示查找失败*/
    return 0;
}

test.c中的调用方法：

    int lf = ListFind(plist, 5);
    if (lf==1)
        printf("找到了%d\n",lf);
    else
        printf("没找到\n");

12,销毁链表

void ListDestory(LTNode* phead)
{
    assert(phead);

    LTNode* cur = phead->next;
    int size = 0;
    while (cur != phead)
    {
        LTNode* next = cur->next;
        ListErase(cur);
        cur = next;
    }
    free(phead);
    //只是将指向plist的指针置空，要置空plist要在Test.c中完成
    phead = NULL;
}

test.c中的使用方法：

    //销毁的为结构体，并不是指向结构体的指针，所以需要对指针置空
    ListDestory(plist);
    plist = NULL;
    if (plist == NULL)
        printf("销毁成功");

成品展示

List.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int LTDataType;

//定义链表
typedef struct ListNode
{
    struct ListNode* next;
    struct ListNode* prev;
    LTDataType data;
}LTNode;

//创建双向链表
LTNode* BuyListNode(LTDataType x);

//链表初始化
//void ListInit(LTNode** pphead);
LTNode* ListInit();

//打印
void ListPrint(LTNode* phead);

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

//头插
void ListPushFront(LTNode* phead, LTDataType x);

//尾删
void ListPopBack(LTNode* phead);

//头删
void ListPopFront(LTNode* phead);

//判断链表是否被删空
bool ListEmptyLTNode(LTNode* phead);

//pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x);

//删除pos位置的节点
void ListErase(LTNode* pos);

//求链表长度
int ListSize(LTNode* phead);

//查找链元素
int ListFind(LTNode* phead, LTDataType x);

//销毁链表
void ListDestory(LTNode* phead);

List.c

#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;
} 

/*
    改变结构体要用结构体指针。
    要改变结构体指针要用结构体指针的指针。
*/
//初始化链表
//void ListInit(LTNode** pphead)
//{
//    *pphead = BuyListNode(-1);
//    (*pphead)->next = *pphead;
//    (*pphead)->prev = *pphead;
//}
LTNode* ListInit()
{
    LTNode* phead = BuyListNode(-1);
    phead->next = phead;
    phead->prev = phead;
}

//打印
void ListPrint(LTNode* phead)
{
    assert(phead);
    
    //创建指针进行依次访问
    LTNode* cur = phead->next;

    //当cur循环到头节点时代表已经循环一圈，停止循环
    while (cur!=phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    
    //head前一个位置插入即为尾插
    ListInsert(phead, x);//pos前一个位置插入
}
//void ListPushBack(LTNode* phead, LTDataType x)
//{
//    assert(phead);
//
//    LTNode* newnode = BuyListNode(x);
//    LTNode* tail = phead->prev;
//    //前一个节点指向新节点
//    tail->next = newnode;
//    //新节点的prev指向上一个节点
//    newnode->prev = tail;
//    //新节点存放的下一节点为头节点
//    newnode->next = phead;
//    //头节点的prev存放新节点，方便尾插
//    phead->prev = newnode;
//}

//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);

    ListInsert(phead->next, x);
}
//void ListPushFront(LTNode* phead, LTDataType x)
//{
//    assert(phead);
//    
//    LTNode* newnode = BuyListNode(x);
//    LTNode* next = phead->next;
//
//    next->prev = newnode;  //1
//    newnode->next = next;  //2
//    newnode->prev = phead; //3
//    phead->next = newnode; //4
//
//    //phead->next = newnode;
//    //newnode->prev = phead;
//    //newnode->next = next;
//    //next->prev = newnode;
//
//}

//判断链表是否被删空
bool ListEmptyLTNode(LTNode* phead)
{
    assert(phead);

    /*
        链表返回只剩头节点(链表已经被删空)为真
        否则为假
    */
    return phead->next == phead;
}

//尾删
void ListPopBack(LTNode* phead)
{
    assert(phead);
    //判断链表是否被删空：为真即为假，为假即为真
    assert(!ListEmptyLTNode(phead));//assert(phead->next != phead);
    
    ListErase(phead->prev);
}
//void ListPopBack(LTNode* phead)
//{
//    assert(phead);
//    //判断链表是否被删空：为真即为假，为假即为真
//    assert(!ListEmptyLTNode(phead));//assert(phead->next != phead);
//
//    //head的前一个即为尾巴
//    LTNode* tail = phead->prev;//head前一个节点
//    LTNode* tailPrev = tail->prev;//tail的前一个节点
//
//    free(tail);//删除节点
//
//    //重新链接新尾节点
//    tailPrev->next = phead;
//    phead->prev = tailPrev;
//}

//头删
void ListPopFront(LTNode* phead)
{
    assert(phead);

    assert(!ListEmptyLTNode(phead));

    ListErase(phead->next);
}
//void ListPopFront(LTNode* phead)
//{
//    assert(phead);
//    assert(!ListEmptyLTNode(phead));
//
//    LTNode* next = phead->next;
//    LTNode* nnext = next->next;
//
//    free(next);//删除节点
//
//    phead->next = nnext;
//    nnext->prev = phead;
//}

//pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);

    LTNode* prev = pos->prev;
    LTNode* newnode = BuyListNode(x);

    //prev newnode pos
    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;

/*
    不要用头节点存储来计算长度，int符合但其他类型
    例如char，double 都会出现错误
*/
}

/*phead为原双链表，x表示被查找元素*/
int ListFind(LTNode* phead, LTDataType x)
{
    assert(phead);

    /*新建一个指针t，初始化为头指针 head*/
    LTNode* temp = phead->next;
    int i = 1;
    while (temp!=phead)
    {
        if (temp->data == x)
        {
            return i;
        }
        i++;
        temp = temp->next;
    }
    /*程序执行至此处，表示查找失败*/
    return 0;
}

//销毁链表
void ListDestory(LTNode* phead)
{
    assert(phead);

    LTNode* cur = phead->next;
    int size = 0;
    while (cur != phead)
    {
        LTNode* next = cur->next;
        ListErase(cur);
        cur = next;
    }
    free(phead);
    //只是将指向plist的指针置空，要置空plist要在Test.c中完成
    phead = NULL;
}

test.c

test.c只是用于测试代码，菜单的写法本文将不进行讲解。
但test.c中含有对查找and销毁and存储链元素个数的使用方法进行了示例可以当参考。

#include "List.h"

void Test1()
{
    //LTNode* plist = NULL;
    //ListInit(&plist);
    
    LTNode* plist = ListInit();
    ListPushBack(plist, 0);
    ListPushBack(plist, 1);
    ListPushBack(plist, 2);
    ListPushBack(plist, 3);
    ListPushBack(plist, 4);
    ListPrint(plist);
    ListPushFront(plist, 10);
    ListPrint(plist);
}

void Test2()
{
    //LTNode* plist = NULL;
    //ListInit(&plist);

    LTNode* plist = ListInit();
    ListPushFront(plist, 0);
    ListPushFront(plist, 1);
    ListPushFront(plist, 2);
    ListPushFront(plist, 3);
    ListPushFront(plist, 4);
    ListPushBack(plist, 5);
    ListPrint(plist);
    ListPopBack(plist);
    ListPrint(plist);
    ListPopFront(plist);
    ListPrint(plist);

    int lf = ListFind(plist, 5);
    if (lf==1)
        printf("找到了%d\n",lf);
    else
        printf("没找到\n");

    printf("存储的元素个数为：%d\n", ListSize(plist));

    ListDestory(plist);
    plist = NULL;
    if (plist == NULL)
        printf("销毁成功");
}

int main()
{
    Test2();

    return 0;
}

本文到这就结束啦，本文为万字解读，创作不易，若喜欢请留下免费的赞吧！
感谢阅读😊😊😊

标签： 数据结构 链表 c语言
本文转载自: https://blog.csdn.net/2301_77649794/article/details/132807995
版权归原作者 努力学c的楼下小王 所有， 如有侵权，请联系我们删除。
登录后发布评论

“数据结构：线性表之-循环双向链表(万字详解)”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航