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

【DS】带头双向循环链表的实现@线性表 —— 增删查改

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

:strawberry:本文出现如此多草莓的原因是，我昨天晚上吃了好多草莓，并且现在还想吃。
:strawberry:接下来要更新链表这儿的题解咯~

正文开始
反爬链接

0. 引

上文提到，带头双向循环链表 ——

  • 结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。
  • 另外这个结构虽然复杂，却也是无死角的结构，用代码实现时会发现结构会带来很多优势，非常爽，后面我们代码实现了就知道了。

<img src=" title="">

代码实现的简单归功于它复杂的结构，以下这几点都是在写的过程中感受到的 ——

:strawberry: 带头
  1. 这样使得尾插尾删头插头删不必传二级指针，因为pList这个带哨兵位头节点的地址不会发生改变
  2. 尾删时，只剩一个节点和普遍情况(>=2个节点)可以合并
:strawberry: 双向

方便找上一个下一个

:strawberry: 循环

使找尾变得简单

1. 双向循环链表实现

1.1 创建、销毁、申请新节点、打印

1.1.1 创建

<img src=" title="">

:strawberry: 对于pList即这个链表地址的分配我们完全可以直接写，但还是推荐写成接口函数

:strawberry: 初始化函数， 对于pList这个实参的改变，我们同样可以采取以往的办法传二级指针（即pList的地址类型，为LTNode**）

:strawberry: 这里采取返回值的办法，返回地址，赋给pList

LTNode* ListInit()
{
    //哨兵位的头结点
    LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
    if (phead == NULL)
    {
        printf("malloc failed\n");
        exit(-1);
    }
    phead->prev = phead;
    phead->next = phead;
    
    return phead;
}

test.c中是这样调用的

    LTNode* pList = ListInit();

1.1.2 销毁

<img src=" title="">

void ListDestroy(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    
    while (cur != phead)
    {
        LTNode* curNext = cur->next;
        free(cur);
        cur = curNext;
    }
    free(phead);
    //phead = NULL;
}

注意这里的phead = NULL; 很有必要，但这样写没有发挥实际作用（所以我也把它注释掉了），因为phead是形参，形参改变不会影响实参，也就是pList不会改变。

这就导致了野指针的问题 —— 虽然pList仍保持着原来的地址，但是phead已经被释放了，此时pList就是一个野指针。（可以传二级，实际上传二级就不会有这些问题，但为了保持接口一致性用一级比较好）

因此，我们需要在外面，即test.c文件中把它置空 ——

    ListDestroy(pList);
    pList = NULL;//外面置空，就跟free一样

1.1.3 申请新节点

LTNode* BuyListNode(LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL)
    {
        printf("malloc failed\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->prev = NULL;
    newnode->next = NULL;

    return newnode;
}

1.1.4 打印

<img src=" title="">

void ListPrint(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) 
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

1.2 尾插、尾删

1.2.1 尾插

<img src=" title="">

:strawberry: 相比于单链表
  • 不必再传二级指针，因为phead不用更改
  • 完美处理空链表，无需再把链表为空时的插入单拎出来解决
  • 找尾也很方便O(1)，不必像单链表一样找尾找得好辛苦
void ListPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* tail = phead->prev;
    
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
}

1.2.2 尾删

<img src=" title="">

:strawberry: 与单链表相比
  • 不必再传二级指针，因为phead不用更改
  • 不用单拎出来解决只剩一个节点时的情况，它的结构保证了tail不会为空，就不会被错误的解引用
void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);//1.删空了
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    free(tail);
    //链接
    phead->prev = tailPrev;
    tailPrev->next = phead;
}

1.3 头插、头删

1.3.1头插

<img src=" title="">

:strawberry: 与单链表相比
  • 不必再传二级指针，因为phead不用更改
  • 链表为空？也没事。其实这在单链表那儿也没事，就是情不自禁要想一下
void ListPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* headNext = phead->next;
    //链接
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = headNext;
    headNext->prev = newnode;
}

1.3.2 头删

<img src=" title="">

:strawberry: 与单链表相比
  • 不必再传二级指针，因为phead不用更改
  • 只剩一个节点？也没事。其实这在单链表那儿也没事，就是情不自禁要想一下
void ListPopFront(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);//删空时断言
    LTNode* next = phead->next;
    LTNode* nextNext = next->next;
    free(next);
    //链接
    phead->next = nextNext;
    nextNext->prev = phead;
}

1.4 查找、任意位置插入、任意位置删除

1.4.1 查找

和打印类似

LTNode* ListFind(LTNode* phead, LTDataType x)
{
    assert(phead);
    //空链表
    if (phead->next == phead)
    {
        return NULL;
    }
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

1.4.2 任意位置插入

<img src=" title="">

void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode* newnode = BuyListNode(x);
    LTNode* posPrev = pos->prev;
    //链接
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;
}

1.4.3 任意位置删除

<img src=" title="">

void ListErase(LTNode* pos)
{
    //按理说应该断言一下pos是pList的情况，但是为了这个再增加一个参数，得不偿失
    assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;
    free(pos);
    //链接
    posPrev->next = posNext;
    posNext->prev = posPrev;
}

1.4.4 复用

有了上面的任意位置插入删除，就可以快速写出头插头删、尾插尾删。

//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    ListInsert(phead, x);
}

//尾删
void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);//1.删空了
    ListErase(phead->prev);
}

//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    ListInsert(phead->next, x);
}

//头删
void ListPopFront(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);//删空时断言
    ListErase(phead->next);
}

2. 顺序表和链表的比较

这两个结构各有优势，很难说谁更优，它们是相辅相成的结构。

顺序表 链表（带头双向循环链表）
优点 1. 支持随机访问，需要随机访问支持的结构可以很好地适用 1. 任意位置插入删除效率高O(1)
2. CPU高速缓存命中率高 2. 按需申请释放空间
缺点 1. 头部、中间插入效率低 1. 不支持随机访问（即下标访问，如要访问第5个）
2. 连续的物理空间，空间不够了需要增容 2. 链表存储一个值，同时要存储两个指针，有一定消耗
a. 增容有一定程度的消耗 3. CPU高速缓存命中率低
b. 为了避免频繁增容，一般按倍数去增，用不完存在一定空间浪费

img

关于CPU高速缓存命中率，请阅读陈皓的文章与程序员相关的CPU缓存知识 | 酷 壳 - CoolShell，我顺便也读了，没法完全的懂，另外我还被他的其他文章拽走了，太有意思了，但还是解释一下CPU高速缓存命中率。

<img src=" title="">

附：

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* ListInit();
//链表打印
void ListPrint(LTNode* phead);
//销毁
void ListDestroy(LTNode* phead);

//尾插
void ListPushBack(LTNode* phead, LTDataType x);
//尾删
void ListPopBack(LTNode* phead);
//头插
void ListPushFront(LTNode* phead, LTDataType x);
//头删
void ListPopFront(LTNode* phead);
//查找
LTNode* ListFind(LTNode* phead, LTDataType x);


//任意位置插入
void ListInsert(LTNode* pos, LTDataType x);
//任意位置删除
void ListErase(LTNode* pos);

List.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"List.h"

LTNode* BuyListNode(LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL)
    {
        printf("malloc failed\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->prev = NULL;
    newnode->next = NULL;

    return newnode;
}

LTNode* ListInit()
{
    //哨兵位的头结点
    LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
    if (phead == NULL)
    {
        printf("malloc failed\n");
        exit(-1);
    }
    phead->prev = phead;
    phead->next = phead;
    
    return phead;
}

void ListDestroy(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    
    while (cur != phead)
    {
        LTNode* curNext = cur->next;
        free(cur);
        cur = curNext;
    }
    free(phead);
    //phead = NULL;
}

void ListPrint(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) 
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void ListPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* tail = phead->prev;
    //链接
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
    //ListInsert(phead, x);
}

void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);//1.删空了
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    free(tail);
    //链接
    phead->prev = tailPrev;
    tailPrev->next = phead;
    //ListErase(phead->prev);
}

void ListPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* headNext = phead->next;
    //链接
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = headNext;
    headNext->prev = newnode;
    //ListInsert(phead->next, x);

}

void ListPopFront(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);//删空时断言
    LTNode* next = phead->next;
    LTNode* nextNext = next->next;
    free(next);
    //链接
    phead->next = nextNext;
    nextNext->prev = phead;
    //ListErase(phead->next);

}

LTNode* ListFind(LTNode* phead, LTDataType x)
{
    assert(phead);
    //空链表
    if (phead->next == phead)
    {
        return NULL;
    }
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode* newnode = BuyListNode(x);
    LTNode* posPrev = pos->prev;
    //链接
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;
}

void ListErase(LTNode* pos)
{
    //按理说应该断言一下pos是pList的情况，但是为了这个再增加一个参数，得不偿失
    assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;
    free(pos);
    //链接
    posPrev->next = posNext;
    posNext->prev = posPrev;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"List.h"

//测试尾插尾删
void testList1()
{
    LTNode* pList = ListInit();
    ListPushBack(pList, 1);
    ListPushBack(pList, 2);
    ListPushBack(pList, 3);
    ListPrint(pList);

    ListPopBack(pList);
    //ListPopBack(pList);
    /*ListPopBack(pList);
    ListPopBack(pList);*/

    ListPrint(pList);
    ListDestroy(pList);
    pList = NULL;
}

//测试头插头删
void testList2()
{
    LTNode* pList = ListInit();
    ListPushFront(pList, 1);
    ListPushFront(pList, 2);
    ListPushFront(pList, 3);
    ListPrint(pList);

    ListPopFront(pList);
    /*ListPopFront(pList);
    ListPopFront(pList);
    ListPopFront(pList);*/

    ListPrint(pList);
    ListDestroy(pList);
    pList = NULL;

}

//测试查找、任意位置插入、任意位置插入
void testList3()
{
    LTNode* pList = ListInit();
    ListPushBack(pList, 1);
    ListPushBack(pList, 2);
    ListPushBack(pList, 4);
    ListPushBack(pList, 5);
    ListPrint(pList);

    LTNode* ret = ListFind(pList, 4);
    if (ret == NULL)
    {
        printf("not found\n");
    }
    else
    {
        printf("%d\n", ret->data);
    }
    ListInsert(ret,3);
    ListPrint(pList);

    ListErase(ret);
    ListPrint(pList);

    ListDestroy(pList);
    pList = NULL;

}


int main()
{
    //testList1();
    testList2();
    //testList3();
    return 0;
}

本文完@边通书

文章标签：
程序员
缓存
存储
关键词：
链表线性表
ds链表
@浮光掠影
目录
相关文章
张继群
|
6月前
|
存储 算法 C语言
线性表，双向链表，静态链表，循环链表(约瑟夫环)（上）
线性表，双向链表，静态链表，循环链表(约瑟夫环)
张继群
78 5
小陈在拼命
|
6月前
|
存储
DS：带头双向循环链表的实现
DS：带头双向循环链表的实现
小陈在拼命
48 0
小陈在拼命
|
6月前
|
存储 编译器
DS：单链表的实现
DS：单链表的实现
小陈在拼命
71 0
玥轩
|
算法
数据结构与算法2.1线性表、链表
数据结构与算法2.1线性表、链表
玥轩
38 0
数据结构与算法2.1线性表、链表
sky_qiyi
|
5月前
|
算法
数据结构和算法学习记录——线性表之双向链表（上）-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表（上）-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
sky_qiyi
48 0
老秦包你会
|
6月前
|
存储
数据结构第二课 -----线性表之单向链表
数据结构第二课 -----线性表之单向链表
老秦包你会
55 0
sky_qiyi
|
5月前
|
算法
数据结构和算法学习记录——线性表之双向链表（下）-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
数据结构和算法学习记录——线性表之双向链表（下）-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
sky_qiyi
30 0
sky_qiyi
|
5月前
|
算法
数据结构和算法学习记录——线性表之单链表（下）-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表（下）-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
sky_qiyi
62 0
sky_qiyi
|
5月前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数（顺序表缺陷、单链表优点、链表打印）
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数（顺序表缺陷、单链表优点、链表打印）
sky_qiyi
39 0
Skrrapper
|
6月前
|
存储 缓存 算法
【数据结构】线性表----链表详解
【数据结构】线性表----链表详解
Skrrapper
96 0