当前位置： 首页 > news >正文

数据结构（四）-双向链表

news 2025/7/30 1:41:51

双向链表

一、概念

对链表而言，双向均可遍历是最方便的，另外首尾相连循环遍历也可大大增加链表操作的便捷性。 因此，双向循环链表是在实际运用中最常见的链表形态。

二、基本操作

与普通的链表完全一致，双向循环链表虽然指针较多，但逻辑是完全一样的。基本的操作包括：

  1. 节点设计

  2. 初始化空链表

  3. 增删节点

  4. 链表遍历

  5. 销毁链表

三、代码实现

dlist.h
​
#ifndef _DLIST_H
#define _DLIST_H
​
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
​
typedef int DATA;
​
//定义双向链表节点
typedef struct node
{DATA data;     //节点数据struct node *prev;     //前驱指针struct node *next;     //后继指针
}NODE;
​
​
/*** 创建链表（初始化）* @param head 待操作的链表（默认头指针（头节点的指针））* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
extern int dlist_create(NODE **head, DATA data);
​
​
/*** 向链表的头部插入数据（头插法）* @param head 待操作的链表（默认头指针）* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
extern int dlist_addHead(NODE **head, DATA data);
​
​
/*** 向链表的尾部插入数据（尾插法）* @param head 待操作的链表（默认头指针）* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
extern int dlist_addTail(NODE **head, DATA data);
​
​
/*** 向链表的指定位置插入数据（中间插法）* @param head 待操作的链表（默认头指针）* @param pos  待插入节点的目标位置* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
extern int dlist_insert(NODE **head, DATA pos, DATA data);
​
​
/*** 遍历链表数据* @param head 待遍历的链表*/
extern void dlist_showAll(const NODE *head);
​
​
/*** 根据data找到对应的节点* @param head 待查找的链表* @param data目标数据* @return 目标数据匹配到的节点*/
extern NODE *dlist_find(const NODE *head, DATA data);
​/*** 根据old修改对应节点的数据为newdata* @param head 待操作的链表* @param old 待修改的节点数据* @param newdata 修改节点后的数据* @return 成功返回0，否则返回-1*/
extern int dlist_update(const NODE *head, DATA old, DATA newdata);
​
​
/*** 根据data删除对应的节点* @param head 待操作的链表* @param data 目标数据* @return 成功删除返回0，否则返回1*/
extern int dlist_delete(NODE **head, DATA data);
​
​
/*** 销毁双向链表* @param head 待操作链表*/
extern void dlist_destroy(NODE **head);
​
​
#endif //_DLIST_H
​
dlist.c
​
#include "dlist.h"
​
​
/*** 创建链表（初始化）* @param head 待操作的链表（默认头指针（头节点的指针））* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
int dlist_create(NODE **head, DATA data)
{//检测头节点是否存在if(*head){perror("链表已经存在!");return -1;}//创建新节点NODE *p = (NODE*)malloc(sizeof(NODE));//校验新节点是否创建成功if(!p){perror("链表创建失败!");return -1;}//初始化新节点p->data = data;p->prev = p->next = NULL;     //双向链表特性：新节点的前驱和后继指针初始化为NULL//将新节点作为链表的头节点*head = p;     //头节点指向新创建的节点return 0;}
​
​
/*** 向链表的头部插入数据（头插法）* @param head 待操作的链表（默认头指针）* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
int dlist_addHead(NODE **head, DATA data)
{//创建新节点NODE *p = (NODE*)malloc(sizeof(NODE));//校验新节点是否创建成功if(!p){perror("链表创建失败!");return -1;}//初始化新节点p->data = data;p->prev = NULL;     //新节点作为头节点，前驱指针必须置空（双向链表特性）p->next = *head;     //新节点的后继指针指向原头节点（连接链表主体）//处理原头节点的前驱指针（需防止空指针解引用）if(*head)(*head)->prev = p;     //原头节点的前驱指针指向新节点（建立双向链接）//更新头指针指向新节点*head = p;return 0;
}
​
​
/*** 向链表的尾部插入数据（尾插法）* @param head 待操作的链表（默认头指针）* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
int dlist_addTail(NODE **head, DATA data)
{//遍历链表的时候需要用到pNODE *pNew = (NODE*)malloc(sizeof(NODE));if(!pNew){fprintf(stderr, "节点创建失败！\n");return -1;}pNew->data = data;pNew->prev = NULL;pNew->next = NULL;//查找尾节点（从链表头开始遍历）NODE *p = *head;     //p指向当前遍历的节点//情景1：空链表（直接插入新节点）if(!p){//让头指针指向pNew*head = pNew;return 0;}else     //非空链表{//判断是否存在下一个节点while(p->next)     //当p的next为NULL时，那么p一定是尾节点{p = p->next;}     //此时p指向尾节点，p是尾指针}//更改指针的指向p->next = pNew;     //原尾节点的next指向新节点pNew->prev = p;     //新节点的prev指向原尾节点return 0;
}
​
​
/*** 向链表的指定位置插入数据（中间插法，插入到目标位置前）* @param head 待操作的链表（默认头指针）* @param pos  待插入节点的目标位置* @param data 待插入的数据* @return 成功返回0，否则返回-1*/
int dlist_insert(NODE **head, DATA pos, DATA data)
{//遍历链表的时候需要用到pNODE *pNew = (NODE*)malloc(sizeof(NODE));if(!pNew){fprintf(stderr, "节点创建失败！\n");return -1;}pNew->data = data;pNew->prev = NULL;pNew->next = NULL;NODE *p = *head;//空链表if(!p){*head = pNew;     //空链表时头指针指向新节点return 0;}//非空链表while(p){//寻找目标位置if(memcmp(&(p->data), &pos, sizeof(DATA)) == 0){//目标节点是头节点if(p->prev == NULL){pNew->next = p;     //新节点后继指向原头节点p->prev = pNew;     //原头节点前驱指向新节点*head = pNew;     //更新头指针为新节点}//目标节点是非头节点else{pNew->next = p;     //新节点后继指向目标节点pNew->prev = p->prev;     //新节点前驱指向目标节点的前驱p->prev->next = pNew;     //目标节点的上一个节点的后继指向新节点p->prev = pNew;     //目标节点的前驱指向新节点}return 0;}p = p->next;}return -1;
}
​
​
/*** 遍历链表数据* @param head 待遍历的链表*/
void dlist_showAll(const NODE *head)
{const NODE *p = head;//正序遍历（从头节点---尾节点）printf("正序遍历：");while(p){printf("%d\t", p->data);p = p->next;}printf("\n");//逆序遍历（从尾节点---头节点）printf("逆序遍历：");p = head;while(p->next)     //先让指针跑到尾节点p = p->next;while(p){printf("%d\t", p->data);p = p->prev;}printf("\n");}
​
​
/*** 根据data找到对应的节点* @param head 待查找的链表* @param data目标数据* @return 目标数据匹配到的节点*/
NODE *dlist_find(const NODE *head, DATA data)
{const NODE *p = head;//空链表if(!p)return NULL;while(p){if(memcmp(&(p->data), &data, sizeof(DATA)) == 0)return (NODE*)p;p = p->next;}return NULL;
}
​
​
/*** 根据old修改对应节点的数据为newdata* @param head 待操作的链表* @param old 待修改的节点数据* @param newdata 修改节点后的数据* @return 成功返回0，否则返回-1*/
int dlist_update(const NODE *head, DATA old, DATA newdata)
{NODE *p = NULL;if((p = dlist_find(head, old))){//更新数据p->data = newdata;return 0;}return -1;}
​
​
/*** 根据data删除对应的节点* @param head 待操作的链表* @param data 目标数据* @return 成功删除返回0，否则返回1*/
int dlist_delete(NODE **head, DATA data)
{//创建遍历指针指向链表头NODE *p = *head;//空链表if(!p)return -1;//遍历链表查找目标节点while(p){//查找节点if(memcmp(&(p->data), &data, sizeof(DATA)) == 0){//查找到的是头节点if(p->prev == NULL){//若该头节点是唯一节点if(p->next == NULL){//链表置空*head = NULL;}//若此链表包含其他节点else{p->next->prev = NULL;//更新头指针*head = p->next;}}//查找的非头节点else{p->prev->next = p->next;//当删除的目标不是尾节点时（非尾节点需要更新后继节点）if(p->next)p->next->prev = p->prev;     //尾节点的next是NULL，不能往前指}free(p);     //释放节点内存return 0;}p = p->next;}return -1;
}
​
​
/*** 销毁双向链表* @param head 待操作链表*/
void dlist_destroy(NODE **head)
{//用指针尾随法NODE *p = *head, *q = NULL;while(p){q = p;p = p->next;free(q);}*head = NULL;
}
app.c
#include "dlist.h"
​
int main(int argc, char const *argv[])
{NODE *head = NULL;
​// 创建链表dlist_create(&head, 111);      // 111
​// 向链表插入数据dlist_addHead(&head, 222);     // 222  111dlist_addHead(&head, 333);     // 333  222  111dlist_addHead(&head, 444);     // 444  333  222  111dlist_addTail(&head, 5555);    // 444  333  222  111 5555dlist_insert(&head, 333, 8888);// 444  8888 333  222 111  5555
​// 遍历链表dlist_showAll(head);
​// 修改链表数据dlist_update(head, 8888, 6666);dlist_showAll(head);           // 444  6666 333  222 111  5555
​// 删除节点数据dlist_delete(&head, 444);      // 6666 333  222 111  5555dlist_delete(&head, 5555);     // 6666 333  222 111  dlist_delete(&head, 222);      // 6666 333  111  dlist_showAll(head);           // 6666 333  111 
​// 销毁链表dlist_destroy(&head);return 0;
}
​

四、优缺点总结

优点

  1. 双向遍历：可以从头到尾或从尾到头遍历链表，灵活性高。

  2. 删除操作高效：在已知节点指针时，删除节点的时间复杂度为 O(1)（无需遍历前驱节点）

  3. 插入操作灵活：可在给定节点前或后快速插入新节点。

  4. 支持反向操作：适用于需要逆向操作的场景（如撤销功能）

缺点

  1. 内存占用高；每个节点需存储前驱和后继指针，空间开销比单链表大

  2. 操作复杂度略高：插入和删除需维护两个指针，代码实现稍复杂。

  3. 缓存不友好：节点分散存储，可能引发缓存命中率下降。

对比单链表：

  • 单链表：节省空间，但删除/插入需遍历前驱节点（O(n) 时间）

  • 双向链表：以空间换时间，适合频繁双向操作的场景（如浏览器历史记录）。

典型应用：

  • 需要双向遍历的数据结构（如LRU缓存、浏览器历史）

  • 频繁在任意位置插入/删除的场景

http://www.xdnf.cn/news/104041.html

相关文章：

  • C++入门基础（2）
  • 智能配送机器人控制系统设计
  • 边缘计算在工业自动化中的应用：开启智能制造新时代
  • 【ASR学习笔记】常见VAD模型识别语音活动的方式对比
  • Pthon流程控制
  • Ubuntu 环境下控制蓝牙适配器
  • 【CSS】层叠，优先级与继承（三）：超详细继承知识点
  • 如何在编译命令中添加灰度标识
  • 局部最小实验--用最小成本确保方向正确
  • Python实现孔填充与坐标转换
  • 基于STM32、HAL库的MCP42010T数字电位器驱动程序设计
  • 机器学习算法-朴素贝叶斯（附带拉普拉斯平滑处理）
  • 【JAVA】读取windows的串口信息
  • SqlSugar与Entity Framework (EF)的SWOT分析
  • Inxpect 新推高性价比版毫米波安全雷达：以经济实用护航工业安全
  • 游戏开发核心技术解析——从引擎架构到攻防体系的完整技能树
  • 阿里云 AI 搜索开放平台：RAG智能化工作流助力 AI 搜索
  • 【C语言】C语言中的字符函数和字符串函数全解析
  • Pingora vs. Nginx vs. 其他主流代理服务器性能对比
  • 2024从Maven-MySQL-Nginx部署
  • LeetCode热题100--283.移动零--简单
  • Linux中进程的属性：状态
  • 3.4 Agent的生命周期管理：任务分解、状态管理与反馈机制
  • leetcode-排序
  • 迅为RK3562开发板ARM四核A53核心板多种系统适配全开源
  • C++学习-入门到精通-【0】计算机和C++简介
  • C++学习：六个月从基础到就业——C++学习之旅：STL迭代器系统
  • 网站架构演进之路：从单体到垂直，再到缓存优化
  • Python爬虫（2）Python爬虫入门：从HTTP协议解析到豆瓣电影数据抓取实战
  • day31 学习笔记