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

Day23 双向链表

java 2025/8/21 13:43:25

day23 双向链表

链表的逆序

链表逆序的核心思想是通过三个指针（prev、tmp、next）逐个反转节点的 next 指针，最终将整个链表方向翻转。

图示说明如下：

在这里插入图片描述

逆序算法流程（基于头指针）

int ReviseLinkList(LinkList *list)
{int size = GetSizeLinkList(list);if (size < 2)  // 若链表为空或只有一个节点，无需逆序{return 1;}LinkNode *Prev = NULL;           // 当前节点的新后继（逆序后的下一个）LinkNode *Tmp = list->head;      // 当前正在处理的节点LinkNode *Next = Tmp->next;      // 保存原链表中当前节点的下一个节点while (1){Tmp->next = Prev;            // 核心操作：反转当前节点的指针方向Prev = Tmp;                  // 向后移动 Prev 指针Tmp = Next;                  // 向后移动 Tmp 指针if (NULL == Tmp)             // 当 Tmp 为 NULL 时，表示已处理完所有节点{break;}Next = Next->next;           // 更新 Next 指针，指向下一个待处理节点}list->head = Prev;               // 逆序完成后，Prev 指向原链表最后一个节点，即新头节点return 0;
}

代码运行理想结果：链表从 A→B→C→NULL 变为 C→B→A→NULL，头指针指向原尾节点。

使用链表实现字典查询

通过单向链表实现一个简易字典系统，支持单词插入、查找、修改、删除和逆序等功能。

数据结构定义（linklist.h）

#ifndef _LINKLIST_H_
#define _LINKLIST_H_// 存储字典条目：单词与释义
typedef struct person
{char word[50];     // 单词char mean[256];    // 释义
} DATATYPE;// 链表节点结构
typedef struct node
{DATATYPE data;             // 数据域struct node *next;         // 指针域，指向下一个节点
} LinkNode;// 链表管理结构
typedef struct list
{LinkNode *head;            // 头节点指针int clen;                  // 当前有效元素个数
} LinkList;// 函数声明
LinkList *CreateLinkList();
int InsertHeadLinkList(LinkList *list, DATATYPE *data);
int InsertTailLinkList(LinkList *list, DATATYPE *data);
int InsertPosLinkList(LinkList *list, DATATYPE *data, int pos);
int ShowLinkList(LinkList *list);
LinkNode *FindLinkList(LinkList *list, char *name);
int DeleteLinkList(LinkList *list, char *name);
int ModifyLinkList(LinkList *list, char *name, DATATYPE *data);
int DestroyLinkList(LinkList *list);
int IsEmptyLinkList(LinkList *list);
int GetSizeLinkList(LinkList *list);
int ReviseLinkList(LinkList *list);
int ShowLinkListOne(LinkList *list, LinkNode *node);#endif  // !_LINKLIST_H_

链表操作实现（linklist.c）

#include "linklist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 创建空链表
LinkList *CreateLinkList()
{LinkList *ll = malloc(sizeof(LinkList));if (NULL == ll){perror("CreateLinkList malloc");return NULL;}ll->head = NULL;ll->clen = 0;return ll;
}// 判断链表是否为空
int IsEmptyLinkList(LinkList *list)
{return 0 == list->clen;
}// 获取链表长度
int GetSizeLinkList(LinkList *list)
{return list->clen;
}// 头插法插入节点
int InsertHeadLinkList(LinkList *list, DATATYPE *data)
{LinkNode *newnode = malloc(sizeof(LinkNode));if (NULL == newnode){perror("InsertHeadLinkList malloc");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;if (!IsEmptyLinkList(list)){newnode->next = list->head;  // 新节点指向原头节点}list->head = newnode;            // 更新头指针list->clen++;return 0;
}// 尾插法插入节点
int InsertTailLinkList(LinkList *list, DATATYPE *data)
{if (IsEmptyLinkList(list)){return InsertHeadLinkList(list, data);  // 空链表则头插}else{LinkNode *tmp = list->head;while (tmp->next)                    // 找到最后一个节点{tmp = tmp->next;}LinkNode *newnode = malloc(sizeof(LinkNode));if (NULL == newnode){perror("InsertTailLinkList malloc");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;tmp->next = newnode;                 // 连接新节点}list->clen++;return 0;
}// 在指定位置插入节点
int InsertPosLinkList(LinkList *list, DATATYPE *data, int pos)
{int len = GetSizeLinkList(list);if (pos < 0 || pos > len){fprintf(stderr, "InsertPosLinkList pos error\n");return 1;}if (0 == pos) return InsertHeadLinkList(list, data);else if (pos == len) return InsertTailLinkList(list, data);else{LinkNode *tmp = list->head;int off = pos - 1;while (off--) tmp = tmp->next;       // 移动到插入位置前一个节点LinkNode *newnode = malloc(sizeof(LinkNode));if (NULL == newnode){perror("InsertposLinkList malloc");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;newnode->next = tmp->next;           // 新节点连接后续tmp->next = newnode;                 // 前驱连接新节点list->clen++;}return 0;
}// 显示整个链表内容
int ShowLinkList(LinkList *list)
{LinkNode *tmp = list->head;while (tmp){printf("word:%s mean:%s\n", tmp->data.word, tmp->data.mean);tmp = tmp->next;}return 0;
}// 显示单个节点信息
int ShowLinkListOne(LinkList *list, LinkNode *node)
{printf("word:%s mean:%s\n", node->data.word, node->data.mean);return 0;
}// 查找指定单词的节点
LinkNode *FindLinkList(LinkList *list, char *name)
{LinkNode *tmp = list->head;while (tmp){if (0 == strcmp(tmp->data.word, name)){return tmp;}tmp = tmp->next;}return NULL;
}// 删除指定单词的节点
int DeleteLinkList(LinkList *list, char *name)
{if (IsEmptyLinkList(list)){fprintf(stderr, "DeleteLinkList empty list\n");return 1;}LinkNode *tmp = list->head;if (0 == strcmp(tmp->data.word, name)){list->head = list->head->next;free(tmp);list->clen--;}else{while (tmp->next){if (0 == strcmp(tmp->next->data.word, name)){LinkNode *del = tmp->next;tmp->next = tmp->next->next;free(del);list->clen--;break;}tmp = tmp->next;}}return 0;
}// 修改指定单词的内容
int ModifyLinkList(LinkList *list, char *name, DATATYPE *data)
{LinkNode *tmp = FindLinkList(list, name);if (NULL == tmp){printf("modify error\n");return 1;}memcpy(&tmp->data, data, sizeof(DATATYPE));return 0;
}// 销毁整个链表
int DestroyLinkList(LinkList *list)
{LinkNode *tmp = list->head;while (tmp){list->head = list->head->next;free(tmp);tmp = list->head;}free(list);return 0;
}// 链表逆序（已在上文详述）
int ReviseLinkList(LinkList *list)
{int size = GetSizeLinkList(list);if (size < 2){return 1;}LinkNode *Prev = NULL;LinkNode *Tmp = list->head;LinkNode *Next = Tmp->next;while (1){Tmp->next = Prev;Prev = Tmp;Tmp = Next;if (NULL == Tmp){break;}Next = Next->next;}list->head = Prev;return 0;
}

主程序（main.c）

#include <stdio.h>
#include <string.h>
#include "linklist.h"int main(int argc, char** argv)
{LinkList* ll = CreateLinkList();FILE* fp = fopen("/home/linux/dict.txt", "r");if (NULL == fp){perror("fopen error\n");return 1;}DATATYPE data = {0};char linebuf[1024] = {0};while (1){bzero(&data, sizeof(DATATYPE));bzero(linebuf, sizeof(linebuf));char* word = NULL;char* mean = NULL;if (NULL == fgets(linebuf, sizeof(linebuf), fp)){break;}word = strtok(linebuf, " ");mean = strtok(NULL, "\r");if (NULL == word || NULL == mean){perror("strtok error\n");fclose(fp);DestroyLinkList(ll);return 1;}strcpy(data.word, word);strcpy(data.mean, mean);InsertHeadLinkList(ll, &data);}// 交互式查询while (1){char want_word[50] = {0};printf("pls input word:");fgets(want_word, sizeof(want_word), stdin);want_word[strlen(want_word) - 1] = '\0';  // 去除换行符if (0 == strcmp(want_word, "#quit")){break;}LinkNode* tmp = FindLinkList(ll, want_word);if (tmp){ShowLinkListOne(ll, tmp);}else{printf("cant find,%s\n", want_word);}}fclose(fp);DestroyLinkList(ll);return 0;
}

运行理想结果：成功读取 dict.txt 中的单词与释义，构建链表；用户输入单词后可实时查询释义，输入 #quit 退出程序。

找到倒数第k个节点

使用 快慢指针法 实现高效查找。

思路

快指针 fast 先走 k-1 步；
然后 fast 和 slow 同步前进；
当 fast 到达末尾（NULL）时，slow 所指即为倒数第 k 个节点。

LinkNode *GetLastKNode(LinkList *list, int k)
{LinkNode *fast = list->head;LinkNode *slow = list->head;int len = GetSizeLinkList(list);if (len < k){printf("GetLastKNode k error\n");return NULL;}int off = k - 1;while (off--){fast = fast->next;}while (fast){fast = fast->next;if (NULL == fast) break;slow = slow->next;}return slow;
}

代码运行理想结果：若链表为 A→B→C→D→E→NULL，调用 GetLastKNode(ll, 2) 返回指向 D 的节点（倒数第二个）。

测试代码：

int k = 2;
LinkNode* tmp = GetLastKNode(ll, k);
if (NULL == tmp)
{printf("cant find last k = %d\n", k);
}
else
{printf("get last k name:%s score:%d\n", tmp->data.name, tmp->data.score);
}

找到中间节点

同样使用 快慢指针法。

思路

fast 每次走两步，slow 每次走一步；
当 fast 到达末尾时，slow 正好在中间。

LinkNode *GetMidNode(LinkList *list)
{LinkNode *fast = list->head;LinkNode *slow = list->head;while (fast){fast = fast->next;if (NULL == fast){break;}slow = slow->next;fast = fast->next;}return slow;
}

代码运行理想结果：

奇数长度（5）：返回第 3 个节点；
偶数长度（6）：返回第 4 个节点（偏右中间）。

测试代码：

LinkNode* tmp = GetMidNode(ll);
if (NULL == tmp)
{printf("cant find mid node\n");
}
else
{printf("get midnode name:%s score:%d\n", tmp->data.name, tmp->data.score);
}

双向链表

双向链表每个节点包含前驱（prev）和后继（next）指针，支持双向遍历。

结构示意：

head↓
prev|data|next <-> prev|data|next <-> prev|data|next

在这里插入图片描述

数据结构定义（DouLink.h）

#ifndef _DOULINK_H_
#define _DOULINK_H_typedef struct person
{char name[32];char sex;int age;int score;
} DATATYPE;typedef struct dou_node
{DATATYPE data;struct dou_node *prev;struct dou_node *next;
} DouLinkNode;typedef struct list
{DouLinkNode *head;int clen;
} DouLinkList;typedef enum
{DIR_FORWARD,DIR_BACKWARD
} DIRECT;typedef int (*PFUN)(DATATYPE *data, void *arg);// 函数声明
DouLinkList *CreateDouLinkList();
int InsertHeadDouLinkList(DouLinkList *dl, DATATYPE *data);
int InsertTailDouLinkList(DouLinkList *dl, DATATYPE *data);
int InsertPosDouLinkList(DouLinkList *dl, DATATYPE *data, int pos);
DouLinkNode *FindDouLinkList(DouLinkList *dl, PFUN fun, void* arg);
int ModifyDouLinkList(DouLinkList *dl, char *name, DATATYPE *newdata);
int DeleteDouLinkList(DouLinkList *dl, char *name);
int GetSizeDouLinkList(DouLinkList *dl);
int IsEmptyDouLinkList(DouLinkList *dl);
int DestroyDouLinkList(DouLinkList *dl);
int ShowDouLinkList(DouLinkList *dl, DIRECT direct);#endif

双向链表实现（DouLink.c）

#include "DouLink.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>DouLinkList *CreateDouLinkList()
{DouLinkList *dl = malloc(sizeof(DouLinkList));if (NULL == dl){perror("CreateDouLinkList malloc");return NULL;}dl->head = NULL;dl->clen = 0;return dl;
}int IsEmptyDouLinkList(DouLinkList *dl)
{return 0 == dl->clen;
}int InsertHeadDouLinkList(DouLinkList *dl, DATATYPE *data)
{DouLinkNode *newnode = malloc(sizeof(DouLinkNode));if (NULL == newnode){perror("InsertHeadDouLinkList malloc");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;newnode->prev = NULL;if (IsEmptyDouLinkList(dl)){dl->head = newnode;}else{newnode->next = dl->head;dl->head->prev = newnode;dl->head = newnode;}dl->clen++;return 0;
}int InsertTailDouLinkList(DouLinkList *dl, DATATYPE *data)
{if (IsEmptyDouLinkList(dl)){return InsertHeadDouLinkList(dl, data);}else{DouLinkNode* newnode = malloc(sizeof(DouLinkNode));if (NULL == newnode){perror("InsertTailDouLinkList malloc");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;newnode->prev = NULL;DouLinkNode* tmp = dl->head;while (tmp->next){tmp = tmp->next;}newnode->prev = tmp;tmp->next = newnode;}dl->clen++;return 0;
}int InsertPosDouLinkList(DouLinkList *dl, DATATYPE *data, int pos)
{int size = GetSizeDouLinkList(dl);if (pos < 0 || pos > size){printf("InsertPosDouLinkList pos error\n");return 1;}if (0 == pos) return InsertHeadDouLinkList(dl, data);else if (size == pos) return InsertTailDouLinkList(dl, data);else{DouLinkNode* newnode = malloc(sizeof(DouLinkNode));if (NULL == newnode){perror("InsertPosDouLinkList malloc");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;newnode->prev = NULL;DouLinkNode* tmp = dl->head;while (pos--) tmp = tmp->next;newnode->next = tmp;newnode->prev = tmp->prev;tmp->prev = newnode;newnode->prev->next = newnode;dl->clen++;}return 0;
}int GetSizeDouLinkList(DouLinkList *dl)
{return dl->clen;
}DouLinkNode* FindDouLinkList(DouLinkList *dl, PFUN fun, void* arg)
{DouLinkNode* tmp = dl->head;while (tmp){if (fun(&tmp->data, arg)){return tmp;}tmp = tmp->next;}return NULL;
}int ShowDouLinkList(DouLinkList *dl, DIRECT direct)
{DouLinkNode *tmp = dl->head;if (DIR_FORWARD == direct){while (tmp){printf("name:%s sex:%c age:%d score:%d\n", tmp->data.name, tmp->data.sex, tmp->data.age, tmp->data.score);tmp = tmp->next;}}else{while (tmp->next){tmp = tmp->next;}while (tmp){printf("name:%s sex:%c age:%d score:%d\n", tmp->data.name, tmp->data.sex, tmp->data.age, tmp->data.score);tmp = tmp->prev;}}return 0;
}

主程序测试（main.c）

#include <stdio.h>
#include <stdlib.h>
#include "DouLink.h"
#include <string.h>int findperbyname(DATATYPE* data, void* arg)
{return 0 == strcmp(data->name, (char*)arg);
}int findperbyage(DATATYPE* data, void* arg)
{return data->age == *(int*)arg;
}int main(int argc, char** argv)
{DouLinkList* dl = CreateDouLinkList();DATATYPE data[] = {{"zhangsan", 'm', 20, 80},{"lisi", 'f', 23, 84},{"wangmaizi", 'f', 32, 90},{"guanerge", 'm', 50, 91},{"liubei", 'm', 51, 92},};InsertHeadDouLinkList(dl, &data[0]);InsertHeadDouLinkList(dl, &data[1]);InsertHeadDouLinkList(dl, &data[2]);printf("-----------show forward--------\n");ShowDouLinkList(dl, DIR_FORWARD);printf("-----------show backward--------\n");ShowDouLinkList(dl, DIR_BACKWARD);InsertTailDouLinkList(dl, &data[3]);printf("-----------tail--------\n");ShowDouLinkList(dl, DIR_FORWARD);InsertPosDouLinkList(dl, &data[4], 2);printf("-----------pos--------\n");ShowDouLinkList(dl, DIR_FORWARD);printf("-----------rev show--------\n");ShowDouLinkList(dl, DIR_BACKWARD);int age = 50;DouLinkNode* tmp = FindDouLinkList(dl, findperbyage, &age);if (NULL == tmp){printf("can't find per with age %d\n", age);}else{printf("find it, name:%s score:%d\n", tmp->data.name, tmp->data.score);}return 0;
}

运行理想结果：成功插入节点，正向/反向打印一致，查找年龄为 50 的人员信息成功输出。

Makefile

SRC=main.o
SRC+=DouLink.o
DST=all
CC=gcc%.o:%.c$(CC) $^ -c -o $@$(DST):$(SRC)$(CC) $(SRC) -o $(DST)clean:rm $(DST) *.o

gdb段错误检测

使用 gdb 调试段错误步骤：

编译时加 -g：gcc -g main.c linklist.c -o app
启动调试：gdb app
运行程序：(gdb) run
发生段错误后查看堆栈：(gdb) bt
查看变量值、代码行等辅助定位问题。

常用命令：

list：显示源码
print var：打印变量
next / step：单步执行
continue：继续运行

回顾

双向链表特点

每个节点包含：数据域 + next 指针 + prev 指针
支持双向遍历，灵活性更高

核心操作要点

插入/删除：需将 tmp 指针定位到待操作节点或其前驱
头插/尾插/中间插：注意边界判断和指针连接顺序
查找功能扩展：使用函数指针（回调函数）实现通用查找，提升解耦性和扩展性

例如通过 FindDouLinkList(dl, findperbyage, &age) 可实现按任意条件查找，无需修改链表查找逻辑。

查看全文

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

计算机网络--HTTP协议

亚马逊新品爆单策略：从传统困境到智能突破

【Grafana】grafana-image-renderer配合python脚本实现仪表盘导出pdf

给你的Unity编辑器添加实现类似 Odin 的条件显示字段 (ShowIf/HideIf) 功能

word——如何给封面、目录、摘要、正文设置不同的页码

路由器NAT的类型测定

vue：vue中的ref和reactive

【LLMs篇】18：基于EasyR1的Qwen2.5-VL GRPO训练

层在init中只为创建线性层，forward的对线性层中间加非线性运算。且分层定义是为了把原本一长个代码的初始化和运算放到一个组合中。

机械革命电竞控制台一直加载无法点击故障

MySQL事务及原理详解

牛津大学xDeepMind 自然语言处理（3）

精品方案 | GCKontrol与OMNeT++联合仿真在机载网络性能分析中的应用

mvdr波束形成

Linux系统之部署nullboard任务管理工具

ios八股文 -- Objective-c

iOS 应用上架常见问题与解决方案，多工具组合的实战经验

Node.js中的Prisma应用：现代数据库开发的最佳实践

单片机通信协议核心关系梳理笔记（UART/USART/232/485/SPI/12C/LIN/BLE/WIFI）

leetcode7二分查找_69 and 34

SQL-leetcode— 2356. 每位教师所教授的科目种类的数量