AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C语言】深入浅出：C语言链表的全面解析

2024-12-02 20
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
公共DNS（含HTTPDNS解析），每月1000万次HTTP解析
全局流量管理 GTM，标准版 1个月
云解析 DNS，旗舰版 1个月
简介： 链表是一种重要的基础数据结构，适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现，以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。

链表是一种常见的数据结构，由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的最大特点是节点在内存中不必连续存储，因而在插入和删除操作时更加高效。下面我们将详细讲解C语言中单链表、双向链表和循环链表的基本概念、实现方法及其相关操作。

以下是本文中提到的重要内容及其简要描述的表格：

内容 描述
单链表（Singly Linked List） 每个节点包含一个数据域和一个指针域，指向下一个节点。头节点指向链表的第一个节点，尾节点指向 NULL。
双向链表（Doubly Linked List） 每个节点包含数据域、前驱指针和后继指针，允许双向遍历。前驱指针指向前一个节点，后继指针指向后一个节点。
循环链表（Circular Linked List） 最后一个节点的指针域指向头节点，形成一个环形结构。可以是单向的或双向的。
创建节点 动态分配内存，为链表创建新节点。
插入节点 将新节点插入到链表中的特定位置或链表末尾。
删除节点 从链表中移除特定节点，并释放相应的内存。
动态内存分配 链表节点在运行时动态分配和释放内存，不需要在编译时指定大小。
插入和删除效率 插入和删除操作效率高，在已知节点位置的情况下时间复杂度为 O(1)。
随机访问效率 随机访问效率低，无法通过索引直接访问元素，必须从头开始遍历，时间复杂度为 O(n)。
应用 常用于实现队列、栈、图和网络的表示等数据结构，以及内存管理中的空闲块管理。

一、单链表

1. 基本概念

单链表（Singly Linked List）是一种链表结构，其中每个节点包含一个数据域和一个指针域，指针域指向下一个节点。链表的第一个节点称为头节点，最后一个节点的指针域指向NULL，表示链表的结束。

节点结构定义

struct Node {
   
    int data;          // 数据域
    struct Node* next; // 指针域，指向下一个节点
};

2. 创建链表

示例代码

#include <stdio.h>
#include <stdlib.h>

// 节点结构定义
struct Node {
   
    int data;
    struct Node* next;
};

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

// 添加节点到链表末尾
void append(struct Node** headRef, int data) {
   
    struct Node* newNode = createNode(data);
    if (*headRef == NULL) {
   
        *headRef = newNode;
    } else {
   
        struct Node* temp = *headRef;
        while (temp->next != NULL) {
   
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 打印链表
void printList(struct Node* head) {
   
    struct Node* temp = head;
    while (temp != NULL) {
   
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
   
    struct Node* head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    printList(head);
    return 0;
}

输出结果

1 -> 2 -> 3 -> NULL

3. 插入节点

示例代码

// 在特定位置插入新节点
void insertAfter(struct Node* prevNode, int data) {
   
    if (prevNode == NULL) {
   
        printf("前置节点不能为空\n");
        return;
    }
    struct Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

int main() {
   
    struct Node* head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    insertAfter(head->next, 4); // 在第二个节点后插入4
    printList(head);
    return 0;
}

输出结果

1 -> 2 -> 4 -> 3 -> NULL

4. 删除节点

示例代码

// 删除包含特定数据的节点
void deleteNode(struct Node** headRef, int key) {
   
    struct Node* temp = *headRef;
    struct Node* prev = NULL;

    if (temp != NULL && temp->data == key) {
   
        *headRef = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
   
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

int main() {
   
    struct Node* head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    deleteNode(&head, 2); // 删除包含数据2的节点
    printList(head);
    return 0;
}

输出结果

1 -> 3 -> NULL

二、双向链表

1. 基本概念

双向链表（Doubly Linked List）是一种链表结构，其中每个节点包含三个部分：数据域、前驱指针域和后继指针域。前驱指针指向前一个节点，后继指针指向后一个节点。双向链表允许双向遍历。

节点结构定义

struct DNode {
   
    int data;
    struct DNode* prev; // 前驱指针
    struct DNode* next; // 后继指针
};

2. 创建双向链表

示例代码

#include <stdio.h>
#include <stdlib.h>

// 双向链表节点结构定义
struct DNode {
   
    int data;
    struct DNode* prev;
    struct DNode* next;
};

// 创建新节点
struct DNode* createDNode(int data) {
   
    struct DNode* newNode = (struct DNode*)malloc(sizeof(struct DNode));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 添加节点到链表末尾
void appendD(struct DNode** headRef, int data) {
   
    struct DNode* newNode = createDNode(data);
    if (*headRef == NULL) {
   
        *headRef = newNode;
    } else {
   
        struct DNode* temp = *headRef;
        while (temp->next != NULL) {
   
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

// 打印双向链表
void printDList(struct DNode* head) {
   
    struct DNode* temp = head;
    while (temp != NULL) {
   
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
   
    struct DNode* head = NULL;
    appendD(&head, 1);
    appendD(&head, 2);
    appendD(&head, 3);
    printDList(head);
    return 0;
}

输出结果

1 <-> 2 <-> 3 <-> NULL

3. 插入节点

示例代码

// 在特定节点后插入新节点
void insertAfterD(struct DNode* prevNode, int data) {
   
    if (prevNode == NULL) {
   
        printf("前置节点不能为空\n");
        return;
    }
    struct DNode* newNode = createDNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
    newNode->prev = prevNode;
    if (newNode->next != NULL) {
   
        newNode->next->prev = newNode;
    }
}

int main() {
   
    struct DNode* head = NULL;
    appendD(&head, 1);
    appendD(&head, 2);
    appendD(&head, 3);
    insertAfterD(head->next, 4); // 在第二个节点后插入4
    printDList(head);
    return 0;
}

输出结果

1 <-> 2 <-> 4 <-> 3 <-> NULL

4. 删除节点

示例代码

// 删除包含特定数据的节点
void deleteDNode(struct DNode** headRef, int key) {
   
    struct DNode* temp = *headRef;

    while (temp != NULL && temp->data != key) {
   
        temp = temp->next;
    }

    if (temp == NULL) return;

    if (temp->prev != NULL) {
   
        temp->prev->next = temp->next;
    } else {
   
        *headRef = temp->next;
    }

    if (temp->next != NULL) {
   
        temp->next->prev = temp->prev;
    }

    free(temp);
}

int main() {
   
    struct DNode* head = NULL;
    appendD(&head, 1);
    appendD(&head, 2);
    appendD(&head, 3);
    deleteDNode(&head, 2); // 删除包含数据2的节点
    printDList(head);
    return 0;
}

输出结果

1 <-> 3 <-> NULL

三、循环链表

1. 基本概念

循环链表（Circular Linked List）是一种链表结构，其中最后一个节点的指针域指向链表的头节点，形成一个环形结构。循环链表可以是单向的或双向的。

节点结构定义

struct CNode {
   
    int data;
    struct CNode* next;
};

2. 创建循环链表

示例代码

#include <stdio.h>
#include <stdlib.h>

// 循环链表节点结构定义
struct CNode {
   
    int data;
    struct CNode* next;
};

// 创建新节点
struct CNode* createCNode(int data) {
   
    struct CNode* newNode = (struct CNode*)malloc(sizeof(struct CNode));
    newNode->data = data;
    newNode->next = newNode; // 初始时，节点的next指向自身
    return newNode;
}

// 添加节点到循环链表末尾
void appendC(struct CNode** headRef, int data) {
   
    struct CNode* newNode = createCNode(data);
    if (*headRef == NULL) {
   
        *headRef = newNode;
    } else {
   
        struct CNode* temp = *headRef;
        while (temp->next != *headRef) {
   
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = *headRef;
    }
}

// 打印循环链表
void printCList(struct CNode* head) {
   
    if (head == NULL) return;
    struct CNode* temp = head;
    do {
   
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(back to head)\n");
}

int main() {
   
    struct CNode* head = NULL;
    appendC(&head, 1);
    appendC(&head, 2);
    appendC(&head, 3);
    printCList(head);
    return 0;
}

输出结果

1 -> 2 -> 3 -> (back to head)

3. 插入节点

在循环链表中插入节点时，需要特别小心处理环的连接，以确保新节点正确地链接到链表中。

示例代码

// 在特定位置后插入新节点
void insertAfterC(struct CNode* prevNode, int data) {
   
    if (prevNode == NULL) {
   
        printf("前置节点不能为空\n");
        return;
    }
    struct CNode* newNode = createCNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

int main() {
   
    struct CNode* head = NULL;
    appendC(&head, 1);
    appendC(&head, 2);
    appendC(&head, 3);
    insertAfterC(head->next, 4); // 在第二个节点后插入4
    printCList(head);
    return 0;
}

输出结果

1 -> 2 -> 4 -> 3 -> (back to head)

4. 删除节点

在循环链表中删除节点时，特别要注意处理头节点的删除和尾节点的循环连接。

示例代码

// 删除包含特定数据的节点
void deleteCNode(struct CNode** headRef, int key) {
   
    if (*headRef == NULL) return;

    struct CNode *curr = *headRef, *prev = NULL;

    // 处理头节点可能是目标节点的情况
    if (curr->data == key) {
   
        while (curr->next != *headRef) {
   
            curr = curr->next;
        }
        if (curr == *headRef) {
    // 链表只有一个节点
            free(*headRef);
            *headRef = NULL;
        } else {
    // 链表有多个节点
            curr->next = (*headRef)->next;
            free(*headRef);
            *headRef = curr->next;
        }
        return;
    }

    // 查找目标节点
    do {
   
        prev = curr;
        curr = curr->next;
    } while (curr != *headRef && curr->data != key);

    // 未找到目标节点
    if (curr == *headRef) return;

    // 解除目标节点
    prev->next = curr->next;
    free(curr);
}

int main() {
   
    struct CNode* head = NULL;
    appendC(&head, 1);
    appendC(&head, 2);
    appendC(&head, 3);
    deleteCNode(&head, 2); // 删除包含数据2的节点
    printCList(head);
    return 0;
}

输出结果

1 -> 3 -> (back to head)

四、链表的优缺点与应用

1. 优点

  1. 动态内存分配：链表可以在运行时动态分配和释放内存，不需要在编译时指定大小。
  2. 插入和删除效率高：在已知节点位置的情况下，链表的插入和删除操作非常高效，时间复杂度为 O(1)。

2. 缺点

  1. 额外的存储开销：每个节点需要存储指针，增加了内存使用。
  2. 随机访问不便：无法通过索引直接访问元素，必须从头开始遍历，时间复杂度为 O(n)。

3. 常见应用

  1. 实现数据结构：如队列、栈等。
  2. 内存管理：如动态内存分配器的空闲块管理。
  3. 图和网络的表示：如邻接表表示法。

五、总结

链表是一种重要的基础数据结构，适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现，以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。

六、结束语

  1. 本节内容已经全部介绍完毕，希望通过这篇文章，大家对C语言链表有了更深入的理解和认识。
  2. 感谢各位的阅读和支持，如果觉得这篇文章对你有帮助，请不要吝惜你的点赞和评论，这对我们非常重要。再次感谢大家的关注和支持！
文章标签：
云解析DNS
C语言
存储
索引
算法
LuckiBit
目录
相关文章
鲜于言悠
|
7月前
|
存储 安全 编译器
c语言从入门到实战——初识指针
C语言指针是一种变量，它存储了另一个变量的内存地址。通过指针，我们可以直接访问内存中的数据，从而实现灵活的数据操作。 指针是编程中的一个概念，它存储的是内存地址，指向某个变量。通过指针，可以直接访问和操作内存中的数据，提高程序效率。但使用指针时需小心，避免空指针和野指针等问题，确保程序安全稳定。
鲜于言悠
82 0
蛇蛇keying
|
编译器 C语言
C语言指针进阶(上)
C语言指针进阶(上)
蛇蛇keying
103 1
蛇蛇keying
|
C语言
C语言指针进阶(下)
C语言指针进阶(下)
蛇蛇keying
59 1
root8042965
|
7月前
|
C语言
C语言中指针的基础知识
C语言中指针的基础知识
root8042965
77 0
平凡程序猿~
|
2月前
|
存储 C语言
深入浅出C语言指针(基础篇)
深入浅出C语言指针(基础篇)
平凡程序猿~
31 1
CaojunjiaOnly
|
7月前
|
存储 C语言 C++
C语言指针详解进阶1
C语言指针详解进阶1
CaojunjiaOnly
47 1
春人.
|
C语言
【C语言进阶】 带你玩转指针（二）
【C语言进阶】 带你玩转指针（二）
春人.
46 0
-初生-
|
C语言
C语言 指针进阶 （下）
C语言 指针进阶
-初生-
77 0
起飞的风筝
|
7月前
|
存储 C语言 C++
【指针的进阶】C语言
【指针的进阶】C语言
起飞的风筝
62 0
玛丽亚后
|
7月前
|
存储 C语言
C语言——指针进阶（三）
C语言——指针进阶（三）
玛丽亚后
40 0

热门文章

最新文章

  • 1
    使用MaxCompute访问TableStore（OTS） 简明手册
  • 2
    从超模转职成为程序媛是一种怎样的体验
  • 3
    阿里巴巴NACOS（6）- 在k8s上部署Nacos
  • 4
    将任意应用窗口置顶显示，这个工具太强了。
  • 5
    Wi-Fi物联网设备配网的N种方式
  • 6
    WCF分布式安全开发实践(8):消息安全模式之用户名身份验证:Message_UserName_WSHttpBinding
  • 7
    TechED2010与我（二）—— Windows Phone 7 Develop
  • 8
    华尔街认为Twitter出售毫无悬念 只是不会在今年发生
  • 9
    迂者趣事之——下错楼层
  • 10
    Unix Regex
  • 1
    检测指定TCP端口开放状态免费API接口教程
    22
  • 2
    Python 语言：强大、灵活与高效的编程之选
    27
  • 3
    发现一肉鸡接口，快来围攻啦~
    28
  • 4
    深入解析PID控制算法：从理论到实践的完整指南
    26
  • 5
    《C++ 模型训练之早停法：有效预防过拟合的关键策略》
    24
  • 6
    C++构建 GAN 模型：生成器与判别器平衡训练的关键秘籍
    22
  • 7
    通过matlab分别对比PSO,反向学习PSO,多策略改进反向学习PSO三种优化算法
    24
  • 8
    【C语言】宏定义详解
    22
  • 9
    【C语言】进程和线程详解
    17
  • 10
    【C语言】宏定义详解
    20

    • 相关课程

    更多
  • C语言学习教程
  • 你的第一门C语言课
  • Go语言核心编程 - 数据结构和算法
  • Go语言核心编程 - 基础语法、数组、切片、Map
  • Python语言基础 - 语法入门
  • Python语言基础 - 函数、面向对象、异常处理

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册

    • 相关实验场景

    更多
  • 语言入门-2：基本类型
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月