【数据结构】链表（2）：双向链表和双向循环链表

双向链表（Doubly Linked List）

定义：
每个节点包含三个部分：

  1. 数据域。
  2. 前驱指针域（指向前一个节点）。
  3. 后继指针域（指向下一个节点）。

支持从任意节点向前或向后遍历。

#define datatype int
typedef struct link{
  datatype data;
  struct link* next;  //该指针保存的后继结点的地址
  struct link* prev;  //该指针保存的前驱结点的地址 
}link_t;

双向链表的特点：

  • 双向遍历更灵活，插入和删除操作更高效。
  • 占用更多内存（每个节点需存储两个指针）。
1> 初始化link_init
void link_init(link_t **p)
{
   //申请堆 
    *p = (link_t *)malloc(sizeof(link_t));
    if(NULL == p)
    {
        perror("malloc");
        return;
    }
    (*p)->prev = NULL;
    (*p)->next = NULL;
}
2> 创建结点create_node
static link_t *create_node(datatype d)
{
    //1>向堆空间申请
    link_t *p = (link_t *)malloc(sizeof(link_t));
    if(NULL == p)
    {
        perror("malloc");
        return NULL;
    }
    //2>赋值  
    p->data = d;
    p->next = NULL;   
    p->prev = NULL;
    return p;
}
3> 插入函数insert_behind
//将一个结点(a)插到另一个结点(b)的后面
static void insert_behind(link_t *a,link_t *b)
{
   //遵循先连后断 
   a->next = b->next; 
   a->prev = b;
   if(b->next != NULL)
       b->next->prev = a;
   b->next = a;
}

在这里插入图片描述

4> 头插函数link_insert_head
void link_insert_head(link_t *p,datatype data)
{
    //创建结点
    link_t * node = create_node(data);
    if(NULL == node)
    {
        perror("create_node");
        return;
    }
    //将node插到p后面
    insert_behind(node,p);
}
5> 尾插函数link_insert_tail
void link_insert_tail(link_t *p,datatype data)
{
    //创建结点
    link_t * node = create_node(data);
    if(NULL == node)
    {
        perror("create_node");
        return;
    }
    //遍历找到尾结点
    while(p->next != NULL)
        p = p->next;
    //将node插到尾结点p后面
    insert_behind(node,p);
}
6> 正序遍历display
void display(link_t *p)
{
    printf("正序遍历结果为：\n");
    while(p->next != NULL)
    {
       p = p->next;       
       printf("%d ",p->data);
    }
    printf("\n");
}
7> 逆序遍历dispaly_reverse
void dispaly_reverse(link_t *p)
{
   printf("逆序遍历结果为：\n");
    while(p->next != NULL)
    {
       p = p->next;       
    }
    //往前遍历
    while(p->prev != NULL)
    {
      printf("%d ",p->data);
      p = p->prev;
    }
    printf("\n");  
}
8> 删除函数link_del
void link_del(link_t *p,datatype data)
{
   link_t *node =NULL;
   //遍历 
   while(p->next != NULL)
   {
     //数据对比
     if(p->next->data == data)
     {
        //使要删除的结点的前后结点建立联系
        node = p->next; 
        p->next = node->next;
        if(p->next != NULL)
            p->next->prev = p;
        //释放结点
        node->next = NULL;
        node->prev = NULL;
        free(node);
        continue;
     }  
     p = p->next;  
   } 
}
9> 替换函数link_replace
void link_replace(link_t *p,datatype old,datatype new)
{
   link_t *new_node = NULL;
   link_t *old_node = NULL;
   //遍历 
   while(p->next != NULL) 
   {
       if(p->next->data == old)
       {
          new_node = create_node(new);
          if(NULL == new_node)
          {
              perror("create_node");
              return;
          }
          //替换 
          old_node = p->next;
          new_node->prev = p;
          new_node->next = old_node->next;
          if(old_node->next != NULL)
             old_node->next->prev = new_node;
          p->next = new_node;
          //释放
          old_node->next = NULL;
          old_node->prev = NULL;
          free(old_node);
          continue;
       }
       p = p->next;  //没找到对于数据才会移动
   }    
}

在这里插入图片描述

双向循环链表（Doubly Circular Linked List）

定义：

  1. 双向链表的变体，首尾相连，形成循环。
  2. 每个节点的前驱指针指向前一个节点，后继指针指向下一个节点。

双向循环链表的特点：

  • 支持双向循环遍历。
  • 节点链接更紧密，占用更多内存。

代码包含链表的创建、节点插入、节点删除、以及正向和反向遍历、打印等功能：

1> 初始化link_init
void link_init(link_t **p)
{
   //申请堆 
    *p = (link_t *)malloc(sizeof(link_t));
    if(NULL == p)
    {
        perror("malloc");
        return;
    }
    /*修改处*/ //自己指向自己
    (*p)->prev = (*p);
    (*p)->next = (*p);
}
2> 创建结点create_node
static link_t *create_node(datatype d)
{
    //1>向堆空间申请
    link_t *p = (link_t *)malloc(sizeof(link_t));
    if(NULL == p)
    {
        perror("malloc");
        return NULL;
    }
    //2>赋值  /*修改处*/ 
    p->data = d;
    p->next = p;   
    p->prev = p;
    return p;
}
3> 插入函数insert_behind
//将一个结点(a)插到另一个结点(b)的后面
static void insert_behind(link_t *a,link_t *b)
{
   //遵循先连后断  /*修改处*/
   a->next = b->next; 
   a->prev = b;
   b->next->prev = a;
   b->next = a;
}
4> 头插函数link_insert_head
void link_insert_head(link_t *p,datatype data)
{
    //创建结点
    link_t * node = create_node(data);
    if(NULL == node)
    {
        perror("create_node");
        return;
    }
    //将node插到p后面
    insert_behind(node,p);
}
5> 尾插函数link_insert_tail
void link_insert_tail(link_t *p,datatype data)
{
    //创建结点
    link_t * node = create_node(data);
    if(NULL == node)
    {
        perror("create_node");
        return;
    }
    //将node插到头结点前面 /*修改处*/
    insert_forward(node,p);
}
5.5> 插入到头前函数insert_forward
static void insert_forward(link_t *node,link_t *p)
{
	//先连后断  //尾结点地址用头节点去表示
	node->next = p;
	node->prev = p->prev;
	p->prev->next = node;
	p->prev = node;
}
6> 正序遍历display
void display(link_t *p)
{
    /*修改处*/
    link_t *head = p;
    printf("正序遍历结果为：\n");
    while(p->next != head) /*修改处*/
    {
       p = p->next;       
       printf("%d ",p->data);
    }
    printf("\n");
}
7> 逆序遍历dispaly_reverse
void dispaly_reverse(link_t *p)
{
    /*修改处*/
   link_t *head = p;
   printf("逆序遍历结果为：\n");
    //往前遍历 /*修改处*/
    while(p->prev != head)
    {
      p = p->prev;
      printf("%d ",p->data);
    }
    printf("\n");  
}
8> 删除函数link_del
void link_del(link_t *p,datatype data)
{
    /*修改处*/
   link_t *head =p;
   link_t *node =NULL;
   //遍历 
   while(p->next != head)
   {
     //数据对比
     if(p->next->data == data)
     {
        //使要删除的结点的前后结点建立联系 /*修改处*/
        node = p->next; 
        p->next = node->next;
        p->next->prev = p;
        //释放结点 /*修改处*/
        node->next = node;
        node->prev = node;
        free(node);
        continue;
     }  
     p = p->next;  
   } 
}
9> 替换函数link_replace
void link_replace(link_t *p,datatype old,datatype new)
{
   /*修改处*/
   link_t *head = p;
   link_t *new_node = NULL;
   link_t *old_node = NULL;
   //遍历 
   while(p->next != head)  /*修改处*/
   {
       if(p->next->data == old)
       {
          new_node = create_node(new);
          if(NULL == new_node)
          {
              perror("create_node");
              return;
          }
          //替换  /*修改处*/
          old_node = p->next;
          new_node->prev = p;
          new_node->next = old_node->next;
          old_node->next->prev = new_node;
          p->next = new_node;
          //释放  /*修改处*/
          old_node->next = old_node;
          old_node->prev = old_node;
          free(old_node);
          continue;
       }
       p = p->next;  //没找到对于数据才会移动
   }    
}
一段完整的代码片
#include <stdio.h>
#include <stdlib.h>

// 定义节点结构
typedef struct Node {
    int data;               // 数据域
    struct Node* next;      // 指向下一个节点
    struct Node* prev;      // 指向前一个节点
} Node;

// 创建一个新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// 插入节点到链表末尾
void append(Node** head, int data) {
    Node* newNode = createNode(data);

    // 如果链表为空
    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode; // 自己指向自己（形成循环）
        newNode->prev = newNode;
        return;
    }

    // 查找到链表的最后一个节点
    Node* tail = (*head)->prev;

    // 更新新节点的指针
    newNode->next = *head;      // 新节点的 next 指向头节点
    newNode->prev = tail;       // 新节点的 prev 指向尾节点

    // 更新头节点和尾节点的指针
    tail->next = newNode;       // 尾节点的 next 指向新节点
    (*head)->prev = newNode;    // 头节点的 prev 指向新节点
}

// 删除链表中的指定节点
void deleteNode(Node** head, int key) {
    if (*head == NULL) return;  // 链表为空，直接返回

    Node* current = *head;      // 从头节点开始查找
    Node* temp = NULL;

    // 遍历链表找到值为 key 的节点
    do {
        if (current->data == key) {
            temp = current;
            break;
        }
        current = current->next;
    } while (current != *head); // 回到头节点时终止循环

    if (temp == NULL) {
        printf("节点 %d 未找到。\n", key);
        return;
    }

    // 如果链表中只有一个节点
    if (temp->next == temp && temp->prev == temp) {
        *head = NULL; // 删除唯一节点后链表为空
        free(temp);
        return;
    }

    // 更新前驱和后继节点的指针
    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;

    // 如果删除的是头节点，更新头指针
    if (temp == *head) {
        *head = temp->next;
    }

    free(temp); // 释放删除的节点
}

// 正向遍历链表
void printListForward(Node* head) {
    if (head == NULL) {
        printf("链表为空。\n");
        return;
    }

    Node* temp = head;
    printf("正向遍历链表：");
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head); // 回到头节点时终止
    printf("(head)\n");
}

// 反向遍历链表
void printListBackward(Node* head) {
    if (head == NULL) {
        printf("链表为空。\n");
        return;
    }

    Node* tail = head->prev; // 从尾节点开始
    Node* temp = tail;
    printf("反向遍历链表：");
    do {
        printf("%d -> ", temp->data);
        temp = temp->prev;
    } while (temp != tail); // 回到尾节点时终止
    printf("(tail)\n");
}

// 主函数
int main() {
    Node* head = NULL; // 初始化空链表

    // 添加节点
    append(&head, 10);
    append(&head, 20);
    append(&head, 30);
    append(&head, 40);

    // 打印链表
    printListForward(head);
    printListBackward(head);

    // 删除节点
    printf("删除节点 20：\n");
    deleteNode(&head, 20);
    printListForward(head);
    printListBackward(head);

    // 删除节点 10（头节点）
    printf("删除节点 10：\n");
    deleteNode(&head, 10);
    printListForward(head);
    printListBackward(head);

    return 0;
}
完整代码片 分析：
  1. 结构定义：
    • 每个节点结构包含：
      • data：存储节点数据。
      • next：指向下一个节点。
      • prev：指向前一个节点。
  2. append 函数：
    • 用于在链表末尾插入新节点。
    • 维护双向循环链表的特性：更新新节点、头节点和尾节点的指针。
  3. deleteNode 函数：
    • 在链表中查找值等于key的节点并删除。
    • 特别处理了链表为空、只有一个节点、删除头节点等特殊情况。
  4. 遍历函数：
    • printListForward：正向遍历，从头节点出发，依次打印每个节点。
    • printListBackward：反向遍历，从尾节点出发，依次打印每个节点。
  5. 主函数测试：
    • 插入多个节点。
    • 正向和反向打印链表。
    • 删除指定节点，并再次验证。

双向循环链表运行结果示例：

正向遍历链表：10 -> 20 -> 30 -> 40 -> (head)
反向遍历链表：40 -> 30 -> 20 -> 10 -> (tail)

删除节点 20：
正向遍历链表：10 -> 30 -> 40 -> (head)
反向遍历链表：40 -> 30 -> 10 -> (tail)

删除节点 10：
正向遍历链表：30 -> 40 -> (head)
反向遍历链表：40 -> 30 -> (tail)

双向循环链表提供了灵活的正向和反向遍历功能，同时保持循环特性，适合需要频繁插入、删除并支持循环操作的场景。代码实现中考虑了各种边界条件（如链表为空、只有一个节点等），确保程序安全性。

综上。希望该内容能对你有帮助，感谢！

以上。仅供学习与分享交流，请勿用于商业用途！转载需提前说明。

我是一个十分热爱技术的程序员，希望这篇文章能够对您有帮助，也希望认识更多热爱程序开发的小伙伴。
感谢！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/948943.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

CryptoHack：Diffie-Hellman（STARTER）

CryptoHack：Diffie-Hellman（STARTER）

1.Working with Fields 这里的主要目的是算乘法逆元d 我们有RSA中算乘法逆元的基础这里就很快了&#xff0c;找到“e”和“phi”就是题目中的“g”和"N" # Diffie-Hellman算法 import gmpy2 p991 N991 g209 dgmpy2.invert(g, N) print(d) #5692.Generators of Grou…
阅读更多...
Transformer知识梳理

Transformer知识梳理

Transformer知识梳理 文章目录 Transformer知识梳理什么是Transformer&#xff1f;语言模型迁移学习 Transformer结构注意力层原始结构 总结 什么是Transformer&#xff1f; 语言模型 Transformer模型本质上都是预训练语言模型&#xff0c;大部分采用自监督学习&#xff08;S…
阅读更多...
计算机缺失x3daudio1 7.dll怎么修复？

计算机缺失x3daudio1 7.dll怎么修复？

电脑运行时常见问题解析与修复策略&#xff1a;以“x3daudio1_7.dll缺失”为例 在软件开发与日常电脑维护的广阔领域中&#xff0c;我们时常会遇到各种系统报错和文件问题。这些问题不仅影响我们的工作效率&#xff0c;还可能对数据安全构成潜在威胁。作为一位经验丰富的软件开…
阅读更多...
mysql找回误删除数据

mysql找回误删除数据

查看binlog日志是否开启以及日志文件位置 SHOW VARIABLES LIKE %log_bin%; log_bin 为 ON表示开启状态 /var/mysql/data/ 为binlog日志文件位置 查看正在使用的binlog日志文件 show master status; 通过第一步和第二步可以确定文件位置 将二进制文件转为txt或者sql文件 m…
阅读更多...
第五届神经网络、信息与通信工程国际学术会议（NNICE 2025）

第五届神经网络、信息与通信工程国际学术会议（NNICE 2025）

在线投稿&#xff1a;学术会议-学术交流征稿-学术会议在线-艾思科蓝 征稿主题&#xff1a; 神经网络 机器人控制 优化组合 知识工程 人工智能 逻辑程序设计 人机交互 深度学习 信号处理 信息提取 自然语言推论 信号与信息处理 信息管理与集成 实时信号处理与应用、 DSP应用 图…
阅读更多...
JVM对象内存结构

JVM对象内存结构

1对象内存结构说明 注意&#xff1a; 如果对象为数组对象&#xff0c;在对象头后面有4字节存储数组长度&#xff1b; 1.1对象头 对象头分为Mark Word和Class Pointer两部分&#xff1b; Mark Word&#xff1a;对象基础信息 32位操作系统中占4字节&#xff0c;64位操作系统中占8…
阅读更多...
创建并配置华为云虚拟私有云

创建并配置华为云虚拟私有云

目录 私有云 创建虚拟私有云 私有云 私有云是一种云计算模式&#xff0c;它将云服务部署在企业或组织内部的私有基础设施上&#xff0c;仅供该企业或组织内部使用&#xff0c;不对外提供服务.私有云的主要特点包括&#xff1a; 私密性&#xff1a;私有云的资源&#xff08;如…
阅读更多...
【FlutterDart】 拖动改变 widget 的窗口尺寸大小GestureDetector～简单实现（10 /100）

【FlutterDart】 拖动改变 widget 的窗口尺寸大小GestureDetector～简单实现（10 /100）

上效果 预期的是通过拖动一条边界线改变窗口大小&#xff0c;类似vscode里拖动效果。这个是简单的拖动实现 上代码&#xff1a; import package:flutter/material.dart;class MyDraggableViewDemo extends StatelessWidget {const MyDraggableViewDemo({super.key});override…
阅读更多...
并发服务器框架——zinx

并发服务器框架——zinx

zinx框架 Zinx 是一个用 Go 语言编写的高性能、轻量级的 TCP 服务器框架&#xff0c;它被设计为简单、快速且易于使用。Zinx 提供了一系列的功能&#xff0c;包括但不限于连接管理、数据编解码、业务处理、负载均衡等&#xff0c;适用于构建各种 TCP 网络服务&#xff0c;如游戏…
阅读更多...
前端（API）学习笔记（CLASS 4）：进阶

前端（API）学习笔记（CLASS 4）：进阶

1、日期对象 日期对象&#xff1a;用来表示事件的对象 作用&#xff1a;可以得到当前系统时间 1、实例化 在代码中发现了new关键字&#xff0c;一般将这个操作称为实例化 创建一个时间对象并获取时间 获得当前时间 const datenew Date() 使用日志查看&#xff0c;得到的…
阅读更多...
LeetCode：98.验证二叉搜索树

LeetCode：98.验证二叉搜索树

跟着carl学算法&#xff0c;本系列博客仅做个人记录&#xff0c;建议大家都去看carl本人的博客&#xff0c;写的真的很好的&#xff01; 代码随想录 LeetCode&#xff1a;98.验证二叉搜索树 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 …
阅读更多...
k8s基础(1)—Kubernetes-Pod

k8s基础(1)—Kubernetes-Pod

一、Pod简介 Pod是Kubernetes&#xff08;k8s&#xff09;系统中可以创建和管理的最小单元&#xff0c;是资源对象模型中由用户创建或部署的最小资源对象模型‌。Pod是由一个或多个容器组成的&#xff0c;这些容器共享存储和网络资源&#xff0c;可以看作是一个逻辑的主机‌。…
阅读更多...
vue 项目集成 electron 和 electron 打包及环境配置

vue 项目集成 electron 和 electron 打包及环境配置

vue electron 开发桌面端应用 安装 electron npm i electron -D记得加上-D&#xff0c;electron 需添加到devDependencies&#xff0c;如果添加到dependencies后面运行可能会报错 根目录创建electron文件夹&#xff0c;在electron文件夹创建main.js&#xff08;或者backgrou…
阅读更多...
Rabbitmq追问1

Rabbitmq追问1

如果消费端代码异常&#xff0c;未手动确认&#xff0c;那么这个消息去哪里 2024-12-31 21:19:12 如果消费端代码发生异常&#xff0c;未手动确认&#xff08;ACK&#xff09;的情况下&#xff0c;消息的处理行为取决于消息队列的实现和配置&#xff0c;以下是基于 RabbitMQ …
阅读更多...
第二十八周机器学习笔记：PINN求正反解求PDE文献阅读——反问题、动手深度学习

第二十八周机器学习笔记：PINN求正反解求PDE文献阅读——反问题、动手深度学习

第二十七周周报 一、文献阅读题目信息摘要Abstract网络架构实验——Data-driven discovery of partial differential equations&#xff08;偏微分方程的数据驱动发现&#xff09;1. Continuous time models&#xff08;连续时间模型&#xff09;例子&#xff1a;(Navier–Stok…
阅读更多...
02-1堆的概念

02-1堆的概念

2-1 堆的概念 开启实验步骤: 有两种创建工程的方式, 直接使用老师的文档, 然后进行调试 老师的工程 或者跳转我的步骤进行调试从零创建(ctrl 加鼠标左键,快速跳转) 视频观看地址: 韦东山freeRTOS快速入门视频教程 开始实验 (1) 我们定义一个空闲的数组heap_buf[1024], 它就…
阅读更多...
【HarmonyOS之旅】ArkTS语法(四) -＞ 使用限制与扩展

【HarmonyOS之旅】ArkTS语法(四) -＞ 使用限制与扩展

目录 1 -> 在生成器函数中的使用限制 2 -> 变量的双向绑定 3 -> 自定义组件成员变量初始化的方式与约束 1 -> 在生成器函数中的使用限制 ArkTS语言的使用在生成器函数中存在一定的限制&#xff1a; 表达式仅允许在字符串(${expression})、if条件、ForEach的参…
阅读更多...
大麦抢票科技狠活

大麦抢票科技狠活

仅供学习参考&#xff0c;切勿再令您所爱的人耗费高昂的价格去购置黄牛票 ⚠️核心内容参考: 据悉&#xff0c;于购票环节&#xff0c;大麦凭借恶意流量清洗技术&#xff0c;于网络层实时甄别并阻拦凭借自动化手段发起下单请求的流量&#xff0c;强化对刷票脚本、刷票软件以及…
阅读更多...
【C++】B2106 矩阵转置

【C++】B2106 矩阵转置

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 &#x1f4af;前言&#x1f4af;题目解析&#x1f4af;第一种实现方式&#xff1a;我的初始做法实现思路优缺点分析 &#x1f4af;第二种实现方式&#xff1a;我的优化做法实现思路优缺点分析 &#x1f4a…
阅读更多...
五月天TV 1.1.0 | 频道丰富的娱乐向电视直播应用

五月天TV 1.1.0 | 频道丰富的娱乐向电视直播应用

五月天IPTV是一款提供多种频道的电视直播应用&#xff0c;包括体育、动漫、音乐等。虽然频道种类繁多&#xff0c;但正经频道较少&#xff0c;更适合追求娱乐和轻松内容的用户群体。软件在测试中发现存在一些小问题&#xff0c;频道质量参差不齐。 大小&#xff1a;15M 下载地…
阅读更多...
最新文章

Copyright @ 2022~2023