c语言数据结构-双向链表

简介: c语言数据结构-双向链表

(创作不易,感谢有你,你的支持,就是我前行的最大动力,如果看完对你有帮助,请留下您的足迹)

目录

初识双向链表:

双向链表的插入:

       插入第一个位置的结点:

        插入其他位置的结点:

双向链表的删除:

       删除第一个结点:

       删除其他位置的结点:


初识双向链表

如图所示,双向链表的指针域有两个,一个指向后面的结点,一个指向前面的结点

优点就是便于访问结点的前后结点,提高效率

typedef struct
{
  int id;
  char* name;
}ElementType;
/** 双向链表的结点,包含一个数据域,两个指针域 */
typedef struct DoublyNode 
{
    ElementType data;
    struct DoublyNode* prev;   //指向前缀结点
    struct DoublyNode* next;   //指向后继结点
}DoublyNode;
/** 双向链表 */
typedef struct DoublyLinkList 
{
    int length;
    DoublyNode* next;
}DoublyLinkList;

双向链表的插入:

插入第一个位置的结点:

将ax插入第一个结点时,只需要将ax的next指向a1,ax的prev设为NULL,a1的prev和头指针都指向ax即可完成插入

 //创建空结点
    DoublyNode* node = (DoublyNode*)malloc(sizeof(DoublyNode));
    node->data = element;
    node->prev = NULL;
    node->next = NULL;
    //在第一个位置插入结点
    if (pos == 1)
    {
        //需要判断插入第一个位置并且插入时链表的长度为0
        if (dlList->length == 0)
        {
            dlList->next = node;
            dlList->length++;
            return;
        }
        node->next = dlList->next;
        dlList->next = node;
        node->next->prev = node;
        dlList->length++;
        return;
    }

插入其他位置的结点:

单链表一样,先通过循环找到要插入位置的前一个位置的结点,如图所示,要在a3处插入ax,需要先找到a2,然后将a2的next和a3的prev指向ax,然后ax的prev指向a2,ax的next指向a3

   //在其他位置插入结点
    DoublyNode* currNode = dlList->next;
    //通过循环找到该位置的前一个结点
    for (int i = 1; currNode && i < pos - 1; i++)
    {
        currNode = currNode->next;
    }
    //判断该结点是否为空
    if (currNode) 
    {
        node->prev = currNode;
        if (currNode->next)
        {
            //如果前缀结点非空(因为空就表示没有后继结点了)
            //将插入位置处的前缀结点指向新结点
            currNode->next->prev = node;
        }
        node->next = currNode->next;
        currNode->next = node;
        dlList->length++;
    }

双向链表的删除:

删除第一个结点:

如图所示,如果要删除第一个结点a1,只需要将头指针指向a2,然后将a2的prev指向NULL,最后释放掉a1即可

    ElementType element;
    element.id = -999;
    //删除第一个结点
    if (pos == 1)
    {
        DoublyNode* node = dlList->next;
        //判断结点是否为空
        if (node)
        {
            element = node->data;
            dlList->next = node->next;
            //判断下一个结点是否为空
            if (node->next)
            {
                //如果有第二个结点,那么设置第二个节点的前缀结点为null
                node->next->prev = NULL;
            }
            free(node);
            dlList->length--;
        }
        return element;
    }

删除其他位置的结点:

如图所示,删除a3,只需要将a3的前置结点a2的next指向a4,将a4的prev指向a2,最后释放掉a3即可

  //删除其他位置结点
    DoublyNode* node = dlList->next;
    //通过循环找到该结点
    for (int i = 1; node && i < pos; i++)
    {
        node = node->next;
    }
    //判断该结点是否存在
    if (node)
    {
        element = node->data;
        //判断该结点的下一个结点是否存在
        if (node->next) 
        {
            node->next->prev = node->prev;
        }
        node->prev->next = node->next;
        free(node);
        dlList->length--;
    }
    return element;



相关文章
|
2月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
51 1
|
2月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
56 4
|
2月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
49 4
|
2月前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
53 4
|
11天前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
1月前
|
存储 算法 C语言
【C语言】深入浅出:C语言链表的全面解析
链表是一种重要的基础数据结构,适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现,以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
452 6
|
2月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
73 5
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
65 1
|
存储 缓存 C语言
数据结构——双链表(C语言)
数据结构——双链表(C语言)
|
2月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
117 4