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

数据结构之双链表

article 2025/3/26 6:14:13

目录

1 简介

2 双链表的基本概念

2.1 节点结构

2.2 头插法和尾插法

3 代码实现 

4 代码解析（部分）

4.1 初始化双链表

4.2 添加节点

4.3 删除节点

4.4 获取节点

4.5 插入节点

4.6 反转链表

4.7 打印链表

4.8 核心操作分析

5 总结 

1 简介

双向链表（Doubly Linked List）是一种链式存储结构，每个节点包含数据域和前驱、后继指针，支持双向遍历。本代码实现了双向链表的初始化、插入、删除、查找、反转等操作，并维护头尾指针以优化性能。相比单链表，双向链表在插入和删除时无需额外查找前驱节点，适用于频繁修改数据结构的场景，如缓存管理、文本编辑器等。

2 双链表的基本概念

2.1 节点结构

双向链表的每个节点包含：

  • 数据域：存储数据

  • 前驱指针（prev）：指向前一个节点

  • 后继指针（next）：指向后一个节点

typedef struct node {
    int val;           // 数据域
    struct node* prev; // 前驱指针
    struct node* next; // 后继指针
} DListNode;

2.2 头插法和尾插法

  • 头插法：新节点插入链表头部，时间复杂度为 O(1)

  • 尾插法：新节点插入链表尾部，需维护尾指针，时间复杂度为 O(1)

3 代码实现 

// Dlink.c
// 双向链表
#include <stdio.h>
#include <stdlib.h>

// 定义双链表节点
typedef struct node
{
    char data;         // 数据域
    struct node *prev; // 指针域(前驱节点)
    struct node *next; // 指针域(后继节点)
} Node;

// 定义双链表
typedef struct list
{
    struct node *head; // 头指针
    struct node *tail; // 尾指针
    int size;          // 大小
} List;

void init(List *list);
void add(List *list, char n);
void show(List *list);
void insert(List *list, int index, char n);
void insert2(Node *node, char n);
Node *get(List *list, int index);
void del(List *list, int index);
void reverse(List *list);

int main(int argc, char const *argv[])
{
    List *list = malloc(sizeof(List));
    init(list);
    add(list, 'a');
    add(list, 'b');
    add(list, 'c');
    add(list, 'd');
    add(list, 'e');
    show(list);
    insert(list, 0, 'x');
    show(list);
    del(list, 5);
    show(list);
    reverse(list);
    show(list);
    return 0;
}

// 反转链表
void reverse(List *list)
{
    Node *current = list->head->next; // 从第一个有效节点开始
    Node *prev = NULL;
    Node *next = NULL;

    list->tail = current; // 原头节点将成为新的尾节点

    while (current != NULL)
    {
        next = current->next; // 保存下一个节点
        current->next = prev; // 反转当前节点的后继指针
        current->prev = next; // 反转当前节点的前驱指针
        prev = current;       // 更新前一个节点为当前节点
        current = next;       // 移动到下一个节点
    }

    list->head->next = prev; // 更新头节点的后继为新的头节点
    if (prev != NULL)
    {
        prev->prev = list->head; // 更新新头节点的前驱为头节点
    }
}

// 删除节点
void del(List *list, int index)
{
    if (index < 0 || index >= list->size) // 检查索引是否有效
    {
        return;
    }

    Node *node;
    if (index == 0) // 删除头节点的特殊情况
    {
        node = list->head->next;
        list->head->next = node->next;
        if (node->next != NULL)
        {
            node->next->prev = list->head;
        }
        else
        {
            list->tail = list->head; // 如果删除的是唯一节点，更新尾指针
        }
    }
    else
    {
        node = get(list, index - 1); // 获取前驱节点
        Node *p = node->next;
        node->next = p->next;
        if (p->next != NULL)
        {
            p->next->prev = node;
        }
        else
        {
            list->tail = node; // 如果删除的是尾节点，更新尾指针
        }
        node = p;
    }

    free(node);
    list->size--;
}

// 获取节点
Node *get(List *list, int index)
{
    if (index < 0 || index >= list->size)
    {
        return NULL;
    }
    if (index <= list->size / 2)
    {
        Node *n = list->head;
        for (int i = 0; i <= index; i++)
        {
            n = n->next;
        }
        return n;
    }
    else
    {
        Node *n = list->tail;
        for (int i = 1; i < list->size - index; i++)
        {
            n = n->prev;
        }
        return n;
    }
}

// 插入节点
void insert(List *list, int index, char n)
{
    Node *node = get(list, index );          // 获取要插入位置的前驱节点
    if (node == NULL)
    {
        add(list, n);
        return;
    }
    Node *newN = malloc(sizeof(Node));
    newN->data = n;
    newN->prev = node->prev;
    newN->next = node;
    node->prev->next = newN;
    node->prev = newN;
    list->size++;
}

// 插入节点
void insert2(Node *node, char n)
{
    Node *p = node->prev;
    Node *newN = malloc(sizeof(Node));
    newN->data = n;
    node->next = p->next;
    node->prev = p;
    p->next->prev = newN;
    p->next = newN;
}

// 初始化双链表
void init(List *list)
{
    list->head = malloc(sizeof(Node));
    list->tail = malloc(sizeof(Node));
    list->tail = list->head; // 头尾指针指向同一个节点
    list->size = 0;
}

// 添加节点
void add(List *list, char n)
{
    Node *node = malloc(sizeof(Node));
    node->data = n;
    node->prev = list->tail; // 新节点的前驱节点指向原来的尾节点
    node->next = NULL;       // 新节点的后继节点指向空
    list->tail->next = node; // 新节点成为最后一个节点(尾指针)的后继节点
    list->tail = node;       // 尾指针指向新节点
    list->size++;
}

// 打印双链表
void show(List *list)
{
    printf("大小:%d\n", list->size);
    printf("链表:");
    Node *node = list->head->next;
    while (node != NULL)
    {
        printf("->%c", node->data);
        node = node->next;
    }
    printf("\n");
}

4 代码解析（部分）

4.1 初始化双链表

void init(List *list) {
    list->head = malloc(sizeof(Node));  // 为头节点分配内存
    list->tail = malloc(sizeof(Node));  // 为尾节点分配内存
    list->tail = list->head;            // 头尾指针指向同一个节点，链表初始化为空
    list->size = 0;                     // 初始化链表大小为0
}

初始化双链表时，分配了头节点和尾节点的内存，并将头尾指针都指向同一个节点，表示链表为空，大小初始化为0。

4.2 添加节点

void add(List *list, char n) {
    Node *node = malloc(sizeof(Node));  // 为新节点分配内存
    node->data = n;                     // 将数据赋值给新节点
    node->prev = list->tail;            // 新节点的前驱指向当前尾节点
    node->next = NULL;                  // 新节点的后继指针为NULL
    list->tail->next = node;            // 当前尾节点的后继指向新节点
    list->tail = node;                  // 更新尾指针指向新节点
    list->size++;                       // 更新链表大小
}

此函数向链表尾部添加一个新节点。首先为新节点分配内存，并设置数据域和前后指针。然后更新尾指针。

4.3 删除节点

void del(List *list, int index) {
    if (index < 0 || index >= list->size) {  // 检查索引是否有效
        return;
    }

    Node *node;
    if (index == 0) {  // 删除头节点的特殊情况
        node = list->head->next;
        list->head->next = node->next;
        if (node->next != NULL) {
            node->next->prev = list->head;
        } else {
            list->tail = list->head;  // 删除唯一节点时更新尾指针
        }
    } else {
        node = get(list, index - 1);  // 获取前驱节点
        Node *p = node->next;
        node->next = p->next;
        if (p->next != NULL) {
            p->next->prev = node;
        } else {
            list->tail = node;  // 删除尾节点时更新尾指针
        }
        node = p;
    }

    free(node);  // 释放删除节点的内存
    list->size--; // 更新链表大小
}

删除节点时，首先检查索引是否合法。删除头节点时直接更新头节点的 next，并更新尾节点指针（如果链表只剩一个节点）。删除其他节点时，获取前驱节点并更新前后节点的指针，释放节点内存并更新链表大小。

4.4 获取节点

Node *get(List *list, int index) {
    if (index < 0 || index >= list->size) {
        return NULL;
    }
    if (index <= list->size / 2) {  // 优化：从头部开始遍历
        Node *n = list->head;
        for (int i = 0; i <= index; i++) {
            n = n->next;
        }
        return n;
    } else {  // 优化：从尾部开始遍历
        Node *n = list->tail;
        for (int i = 1; i < list->size - index; i++) {
            n = n->prev;
        }
        return n;
    }
}

此函数根据给定索引获取节点。如果索引在链表的前半部分，则从头节点开始遍历；否则，从尾节点开始遍历，优化了查询性能。

4.5 插入节点

void insert(List *list, int index, char n) {
    Node *node = get(list, index); // 获取目标位置的前驱节点
    if (node == NULL) {             // 如果目标位置无效，调用add函数
        add(list, n);
        return;
    }
    Node *newN = malloc(sizeof(Node));  // 为新节点分配内存
    newN->data = n;                    // 设置数据域
    newN->prev = node->prev;           // 新节点的前驱指向目标节点的前驱
    newN->next = node;                 // 新节点的后继指向目标节点
    node->prev->next = newN;           // 前驱节点的后继指向新节点
    node->prev = newN;                 // 目标节点的前驱指向新节点
    list->size++;                      // 更新链表大小
}

插入节点时，首先获取目标位置的前驱节点。如果目标位置无效，则调用 add 函数将新节点添加到尾部。否则，分配新节点并将其插入到指定位置，更新前后节点的指针，并增加链表大小。

4.6 反转链表

void reverse(List *list) {
    Node *current = list->head->next; // 从第一个有效节点开始
    Node *prev = NULL;
    Node *next = NULL;

    list->tail = current; // 原头节点成为新的尾节点

    while (current != NULL) {
        next = current->next;  // 保存下一个节点
        current->next = prev;  // 反转当前节点的后继指针
        current->prev = next;  // 反转当前节点的前驱指针
        prev = current;        // 更新前驱节点
        current = next;        // 移动到下一个节点
    }

    list->head->next = prev; // 更新头节点的后继为新的头节点
    if (prev != NULL) {
        prev->prev = list->head;  // 更新新头节点的前驱为头节点
    }
}

此函数通过反转链表中的每个节点的前后指针来实现链表的反转，最后更新头尾节点指针。

4.7 打印链表

void show(List *list) {
    printf("大小:%d\n", list->size);  // 输出链表大小
    printf("链表:");
    Node *node = list->head->next;    // 从头节点的下一个节点开始遍历
    while (node != NULL) {
        printf("->%c", node->data);   // 输出节点的数据
        node = node->next;            // 移动到下一个节点
    }
    printf("\n");
}

此函数遍历链表并打印每个节点的 data 字段，帮助显示链表的内容。

4.8 核心操作分析

5 总结 

本文介绍了双向链表的基本概念及其在 C 语言中的实现，涵盖了链表的初始化、节点插入、删除、查找、反转等核心操作。双向链表相比单链表，能够支持双向遍历，具有更高的操作效率，特别是在插入和删除节点时不需要额外查找前驱节点。通过维护头尾指针，能够有效优化性能。通过对每个操作的详细解析，我们可以看到双向链表在动态数据结构中的应用价值，尤其在缓存管理、文本编辑等场景中，能够提高数据处理的灵活性和效率。

源码地址：0315/Dlink.c · jkh111/Niuer_C - 码云 - 开源中国


http://www.kler.cn/a/598128.html

相关文章：

  • 解码未来：DeepSeek开源FlashMLA，推理加速核心技术，引领AI变革
  • 高项第十四章——项目沟通管理
  • SAP SD学习笔记35 - ATP(可用性检查)的各种Pattern
  • 基于springboot的“衣依”服装销售平台（043）
  • 第43章：企业级密钥管理：Vault与Kubernetes集成
  • 运行时智控：PanLang 开发者指南（一）运行时系统核心模块实现——PanLang 原型全栈设计方案与实验性探索5
  • 使用OpenCV进行图像处理：边界填充、阈值处理
  • 第16章：基于CNN和Transformer对心脏左心室的实验分析及改进策略
  • Centos7搭建Zabbix4.x监控HCL模拟网络设备：zabbix-server搭建及监控基础04
  • 【第13届蓝桥杯】软件赛CB组省赛
  • Trie树（字典树）/（前缀树）
  • JVM 学习前置知识
  • 12、Python 异常处理与调试技巧
  • 《Java到Go的平滑转型指南》
  • 轻松认识 SQL 关键字，打开数据库操作大门
  • Java-SpringBootWeb入门、Spring官方脚手架连接不上解决方法
  • 案例：网络命名空间模拟隔离主机场景
  • 人工智能（AI）系统化学习路线
  • Vue 入门到实战 五
  • Java算法队列和栈经常用到的ArrayDeque