跳到主要内容
极客日志极客日志面向AI+效率的开发者社区
首页博客我的书GitHub 精选镜像AI 生图工具UI配色美学关于
搜索内容 / 工具 / 仓库 / 镜像...⌘K搜索
注册
博客列表
C算法

数据结构入门：带头双向循环链表实现

带头双向循环链表的数据结构定义及核心接口实现，包括节点创建、初始化、销毁、打印、判空、头尾插删、查找及指定位置插入删除。通过对比顺序表与链表特性，阐述了链表在频繁增删场景下的优势，并提供了完整的 C 语言代码示例（List.h 与 List.c），帮助理解双链表指针操作逻辑。

人间失格发布于 2026/3/15更新于 2026/8/645 浏览
数据结构入门：带头双向循环链表实现

双链表概述

本篇介绍双链表，是一种链表数据结构。它的每个节点除了包含数据域（用于存储数据）之外，还包含两个指针域，一个指向前一个节点（prev），另一个指向后一个节点（next）。

1. 双链表接口实现

本次实现的是带头双向循环的链表。不仅有指向前一个节点的 prev 指针，还有指向下一个节点的 next 指针。最后一个节点有指向开头的指针 next，开头的节点有指向结尾的指针 prev，形成循环。

双链表结构图

双链表定义

typedef int LTDataType;
typedef struct ListNode {
    struct ListNode* next;
    struct ListNode* prev;
    LTDataType data;
} LTNode;

为便于修改数据类型，建议统一使用 typedef 定义。

1.1 双链表节点创建

LTNode* BuyListNode(LTDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        perror("malloc failed");
        return NULL;
    }
    newnode->data = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

1.2 双链表初始化

LTNode* LTInit() {
    LTNode* phead = BuyListNode(-1);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

通常会在主函数创建一个指针接收初始化指针。prev 和 next 都指向自己形成循环，也就是一个哨兵位，间接规避了链表为空的情况，可以直接 PushBack 节点。

1.3 双链表销毁

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

head 是哨兵位需要开始时被访问，所以从 phead->next 开始。先保存下一个节点的指针，然后释放当前移动指针指向的节点，再把保存过的节点赋值给移动指针实现遍历节点，最后再释放哨兵位 head。

1.4 双链表打印

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

要根据双链表的特性来，双链表有哨兵位，所以打印要从哨兵位的下一个节点开始打印，直到遇到的节点的 next 指针指向哨兵位。

1.5 双链表检查是否为空

int LTEmpty(LTNode* phead) {
    assert(phead);
    return phead->next == phead ? 0 : 1;
}

为了方便在增删查改中避免链表为空的情况，且多处需使用到，所以特别写一个判空函数。因为是循环链表，所以指向自己表明链表只有一个哨兵位，则返回 0，否则返回 1。

1.6 双链表尾插

void LTPushBack(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    phead->prev->next = newnode;
    newnode->prev = phead->prev;
    newnode->next = phead;
    phead->prev = newnode;
}

由于是带头循环，所以每个节点都有逻辑线连接着。通常先修改两个节点间的链接，再修改循环的链接。

1.7 双链表头插

void LTPushFront(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    newnode->next = phead->next;
    phead->next->prev = newnode;
    phead->next = newnode;
    newnode->prev = phead;
}

无论是什么情况下，都要注意连接的顺序是否会影响到其他步骤的正常赋值，所以头插就需要先链接 newnode 的 next 指针，即通常先链接后面的节点。

1.8 双链表尾删

void LTPopBack(LTNode* phead) {
    assert(phead);
    assert(!LTEmpty(phead));
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    tailPrev->next = phead;
    phead->prev = tailPrev;
    free(tail);
    tail = NULL;
}

首先遇到删除就要注意是不是空链表，存不存在节点来删除，然后要分别存储最后一个节点和倒数第二个节点，方便进行链接释放的操作。

1.9 双链表头删

void LTPopFront(LTNode* phead) {
    assert(phead);
    assert(!LTEmpty(phead));
    LTNode* first = phead->next;
    phead->next = first->next;
    first->next->prev = phead;
    free(first);
    first = NULL;
}

相同的操作，无论是删除还是销毁，都要记得存储需要释放的节点相关指针，因为需要在删除之后将其连接的节点连接起来。

1.10 双链表查找

LTNode* LTFind(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) {
        if (cur->data == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

我们在查找时肯定是查找有效的数据，所以我们查找是从哨兵位后一个节点开始的。查找方法也很简单，遍历整个双链表，看看能否找到相应的数据，找得到就返回对应节点，找不到就返回空。

1.11 双链表在 pos 位置插入 x

void LTInsert(LTNode* pos, LTDataType x) {
    assert(pos);
    LTNode* newnode = BuyListNode(x);
    pos->prev->next = newnode;
    newnode->prev = pos->prev;
    pos->prev = newnode;
    newnode->next = pos;
}

因为双向链表有 prev，就不用在意是 pos 前还是 pos 后插入，这里用的是 pos 前插入。

1.12 双链表在 pos 位置删除 x

void LTErase(LTNode* phead, LTNode* pos) {
    assert(phead);
    assert(!LTEmpty(phead));
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
}

其实和头删尾删的原理是一样的，直接删除，然后将剩余两个断开的节点链接就行了。

2. 顺序表和链表对比

顺序表与链表对比

顺序表和链表各有各的好处。

顺序表： 适用于对随机访问性能要求高，元素数量可预估，且不需要频繁进行插入和删除操作的场景。

链表： 适用于需要频繁插入和删除元素，元素数量动态变化，难以预估元素数量的场景。

3. 代码展示

3.1 List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;
typedef struct ListNode {
    struct ListNode* next;
    struct ListNode* prev;
    LTDataType data;
} LTNode;

LTNode* LTInit();
void LTDestroy(LTNode* phead);
void LTPrint(LTNode* phead);
LTNode* BuyListNode(LTDataType x);
int LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* phead, LTNode* pos);

3.2 List.c

#define _CRT_SECURE_NO_WARNINGS
#include "List.h"

// 初始化
LTNode* LTInit() {
    LTNode* phead = BuyListNode(-1);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

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

// 打印
void LTPrint(LTNode* phead) {
    assert(phead);
    printf("<= head =>");
    LTNode* cur = phead->next;
    while (cur != phead) {
        printf(" %d =>", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// 创建节点
LTNode* BuyListNode(LTDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        perror("malloc failed");
        return NULL;
    }
    newnode->data = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

// 判空
int LTEmpty(LTNode* phead) {
    assert(phead);
    return phead->next == phead ? 0 : 1;
}

// 尾插
void LTPushBack(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;
}

// 尾删
void LTPopBack(LTNode* phead) {
    assert(phead);
    assert(!LTEmpty(phead));
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    tailPrev->next = phead;
    phead->prev = tailPrev;
    free(tail);
    tail = NULL;
}

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

// 头删
void LTPopFront(LTNode* phead) {
    assert(phead);
    assert(!LTEmpty(phead));
    LTNode* first = phead->next;
    phead->next = first->next;
    first->next->prev = phead;
    free(first);
    first = NULL;
}

// 查找
LTNode* LTFind(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) {
        if (cur->data == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

// 在 pos 处插入 x
void LTInsert(LTNode* pos, LTDataType x) {
    assert(pos);
    LTNode* newnode = BuyListNode(x);
    pos->prev->next = newnode;
    newnode->prev = pos->prev;
    pos->prev = newnode;
    newnode->next = pos;
}

// 在 pos 处删除 x
void LTErase(LTNode* phead, LTNode* pos) {
    assert(phead);
    assert(!LTEmpty(phead));
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
}

鼓励图片

目录

  1. 双链表概述
  2. 1. 双链表接口实现
  3. 双链表定义
  4. 1.1 双链表节点创建
  5. 1.2 双链表初始化
  6. 1.3 双链表销毁
  7. 1.4 双链表打印
  8. 1.5 双链表检查是否为空
  9. 1.6 双链表尾插
  10. 1.7 双链表头插
  11. 1.8 双链表尾删
  12. 1.9 双链表头删
  13. 1.10 双链表查找
  14. 1.11 双链表在 pos 位置插入 x
  15. 1.12 双链表在 pos 位置删除 x
  16. 2. 顺序表和链表对比
  17. 3. 代码展示
  18. 3.1 List.h
  19. 3.2 List.c
  • 免费图片AI生成工具免费生成了解详情
  • Magick API 一键接入全球大模型注册送1000万token查看
  • 免费图片视频在线生成30秒，将你的创意变成现实开始设计
  • X/Twitter免费视频下载器免登陆无限额度免费视频解析下载了解详情
  • 100+免费在线小游戏爽一把
极客日志微信公众号二维码

微信扫一扫，关注极客日志

微信公众号「极客日志V2」，在微信中扫描左侧二维码关注。展示文案：极客日志V2 zeeklog

更多推荐文章

查看全部
  • Python ABM 框架 Mesa 3.0 重塑多智能体建模体验
  • AIGC 核心技术解析：GPT、BERT 与 Transformer 工作原理
  • AIGC 时代的网络安全威胁与应急响应机制构建
  • 电科金仓发布融合数据库 KES V9 2025 及 AI 产品体系
  • JavaScript 比较与逻辑运算符基础
  • 算法实战：替换所有问号与提莫攻击的模拟解法
  • 基于 Python 与 Flask 的旅游景点推荐系统实现
  • 本地 AI 绘图实战：Z-Image-Turbo_UI 界面体验与性能测试
  • 英伟达 GTC 2026 发布新一代推理芯片与 Rubin 架构
  • LLaMA3：开源战胜闭源意味着什么
  • 全球老龄化社会护理机器人发展研究
  • 跳槽薪资谈判技巧：为何同事能翻倍涨薪而你没有？
  • Stable Diffusion WebUI 云服务器部署实战
  • 飞算 JavaAI 实战：47 分钟重构高耦合遗留系统
  • C++ STL list 模拟实现：从底层链表到容器封装
  • Llama 3.1 模型部署实践与体验
  • C++ 模板机制与 string 类详解
  • C++ 多态核心解析：虚函数重写与动态绑定原理
  • Windows Server 2022/2025 搭建 Web 服务器实战指南
  • DeepSeek 大模型在云平台的优化实践与应用落地

相关免费在线工具

  • 加密/解密文本

    使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online

  • Gemini 图片去水印

    基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online

  • Base64 字符串编码/解码

    将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online

  • Base64 文件转换器

    将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online

  • Markdown转HTML

    将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online

  • HTML转Markdown

    将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online