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

C语言之数据结构：链表（一）

article 2025/3/19 22:30:05

个人主页：云纳星辰怀自在

座右铭：“所谓坚持，就是觉得还有希望！”

1. 链表（Linked List）

定义：链表是一种动态数据结构，由一系列节点（Node）组成，每个节点包含数据域和指针域。链表的节点在内存中不必连续存储，通过指针将节点连接起来。是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。

1.1 链表的分类

链表可以根据指针的方向和节点的连接方式分为以下几类：

1.1.1 单链表（Singly Linked List）

  • 每个节点包含一个指向下一个节点的指针。
  • 只能从头节点开始单向遍历。

1.1.2 双向链表（Doubly Linked List）

  • 每个节点包含两个指针，分别指向前一个节点和后一个节点。
  • 可以双向遍历。

1.1.3 循环链表（Circular Linked List）

  • 单链表或双向链表的变种，尾节点的指针指向头节点。
  • 形成一个循环结构。

基于不同组合，可以实现以下方式

  1. 单向链表和双向链表
  2. 带头链表和无头链表
  3. 循环链表和非循环链表
  4. ……

实际中最常用的还是这两种结构：无头单向非循环链表和带头双向循环链表。

  1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。

1.2 链表的结构

1.2.1 链表的基本结构

链表的基本结构包括：

  • 节点（Node）​：包含：数据域和指针域，存储数据和指针。节点在运行时动态生成 （malloc）。
    struct Node {
        int data;           // 数据域
        struct Node *next;  // 指针域（单链表）
    };
  • 头指针（Head）：指向链表的第一个节点。
  • 尾节点（Tail）：链表的最后一个节点，其指针指向NULL（单链表）或头节点（循环链表）。
struct Node {
    int data;
    struct Node *next;
};

struct Node *head = NULL;
head = (struct Node *)malloc(sizeof(struct Node));
head->data = 10;
head->next = NULL;

区别：链表可以动态扩展，但访问元素需要遍历。

注意事项：注意内存管理，避免内存泄漏。

1.2.2 链表的物理结构

链表的物理结构指的是链表在计算机内存中的实际存储方式，特点：

  1. 非连续存储：链表的节点在内存中不必连续存储，每个节点可以分散在内存的不同位置。
  2. 动态分配：链表节点通过动态内存分配（如malloc）创建，内存大小可以根据需要动态调整。
  3. 指针连接：通过指针将各个节点连接起来，形成逻辑上的线性结构。

Table 1 物理存储

No.

内存地址

数据

指针

1

0x1000

10

0x2000

2

0x2000

20

0x3000

3

0x3000

30

NULL

头指针指向0x1000。

每个节点的指针指向下一个节点的内存地址。

1.2.3 链表的数据结构

链表的数据结构指的是链表的逻辑组织形式，包括节点定义和操作方式。

1.2.3.1 链表节点定义

参考链表的基本结构 中节点定义。

1.2.3.2 链表的逻辑结构

链表的逻辑结构是节点通过指针连接形成的线性序列。例如，单链表的逻辑结构如下：

Head -> [10] -> [20] -> [30] -> NULL

1.2.4 物理结构与数据结构的关系

物理结构是基础：链表的物理结构决定了链表的存储方式和内存分配方式。非连续存储和动态分配是链表灵活性的基础。

数据结构是逻辑组织：链表的数据结构定义了节点的逻辑组织方式和操作方式。通过指针连接节点，形成逻辑上的线性序列。

  • 物理结构：节点分散在内存中，通过指针连接。
  • 数据结构：节点通过指针形成逻辑上的链表。

1.3 链表的操作

链表的基本操作包括：

  1. 插入：在链表的头部、尾部或指定位置插入节点。
  2. 删除：删除链表的头部、尾部或指定位置的节点。
  3. 遍历：访问链表中的每个节点。
  4. 查找：在链表中查找指定数据的节点。
  5. 释放：释放链表占用的内存。

1.4 链表的实现

以“无头单向非循环链表”为例，定义一个结构体变量作为我们链表的每一个单元。那么链表的内容大致可以分为两部分，一部分是根据实际需求所要存储的信息，另一部分则是指向下一个结点【内存单元】的指针变量。为了提高链表的灵活性，我们还对存储信息的类型进行了重定义，方便后期的修改。具体代码如下：

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

    1.4.1 动态节点申请

    动态分配内存，创建一个新的链表节点。无论是对链表内容的头插、尾插、以及指定位置的插入都需要对结点的申请，因此定义一个函数专门用来动态申请一个结点，避免代码在多个函数中的重复。首先就是像内存申请一个结构体大小的内存，注意在申请后一定要对内存函数返回的参数进行判断，若是为空则说明结点的内存空间开辟失败，最后就是对所开辟空间的内容修改了，主要是依据个人需求来编写，具体代码实现如下：

    struct NoHeadSingleListNode *createNode(int data) {
    struct NoHeadSingleListNode *newNode = (struct NoHeadSingleListNode *)malloc(sizeof(struct NoHeadSingleListNode)); // 动态分配内存
    if (newNode == NULL) { // 检查内存分配是否成功
        printf("Memory allocation failed!\n"); // 分配失败时输出错误信息
        exit(1); // 退出程序
    }
    newNode->data = data; // 初始化节点的数据域
    newNode->next = NULL; // 初始化节点的指针域为NULL
    return newNode; // 返回新创建的节点
}

      1.4.2 单链表尾插

      在链表的尾部插入一个新节点。先要找到链表的最后一个结点并将其中的指针修改为所插入结构体的指针，这样便能通过这个指针找到新插入的指针。大致就是找尾和插入这两部分，要注意的是如果链表的内容为空时就无需经过找尾这个过程，直接插入便可以了。具体代码实现：

      void insertAtTail(struct NoHeadSingleListNode ​**head, int data) {

    struct NoHeadSingleListNode *newNode = createNode(data); // 创建新节点

    if (*head == NULL) { // 如果链表为空

        *head = newNode; // 新节点作为头节点

        return; // 结束函数

    }

    struct NoHeadSingleListNode *temp = *head; // 创建一个临时指针，指向头节点

    while (temp->next != NULL) { // 遍历链表，直到找到最后一个节点

        temp = temp->next; // 移动临时指针到下一个节点

    }

    temp->next = newNode; // 将新节点插入到链表尾部

}

        1.4.3 单链表头插

        在链表的头部插入一个新节点。只需将链表的首个指针修改成所要插入的结构体的指针，并将其指向原首个结点，代码实现：

        void insertAtHead(struct NoHeadSingleListNode ​**head, int data) {

    struct NoHeadSingleListNode *newNode = createNode(data); // 创建新节点

    newNode->next = *head; // 新节点的next指向当前头节点

    *head = newNode; // 更新头指针，使其指向新节点

}

          1.4.4 单链表头删

          删除链表的头节点。将第二个结点作为第一个结点，而将第一个结点的空间释放也无需尾删复杂，传来的参数就能直接找到第一个结点。不过要注意的一点依旧是链表的内容是否为空。与下面的尾删类似。

          void deleteAtHead(struct NoHeadSingleListNode ​**head) {

    if (*head == NULL) { // 如果链表为空

        printf("List is empty, cannot delete!\n"); // 输出提示信息

        return; // 结束函数

    }

    struct NoHeadSingleListNode *temp = *head; // 保存头节点

    *head = (*head)->next; // 更新头指针，使其指向下一个节点

    free(temp); // 释放原头节点的内存

}

            1.4.5 单链表尾删

            删除链表的尾节点。

            步骤如下：

            1. 在进行尾删的处理时先要判断链表是否为空，如果为空的话尾删就没有任何意义了。
            2. 在链表不为空的情况下，再进行尾删的处理。这一部分有几种思路，无论是哪种思路，共有的部分就是将释放最后一个结点空间，主要区别在于寻找这个结点的过程不同。其中一种思路，就是找到倒数第二个结点，将其指向最后一个结点的指针置空并释放其所指向的空间也就是最后一个结点的空间。
            void deleteAtTail(struct NoHeadSingleListNode ​**head) {

    if (*head == NULL) { // 如果链表为空

        printf("List is empty, cannot delete!\n"); // 输出提示信息

        return; // 结束函数

    }

    if ((*head)->next == NULL) { // 如果链表只有一个节点

        free(*head); // 释放头节点的内存

        *head = NULL; // 将头指针置为NULL

        return; // 结束函数

    }

    struct NoHeadSingleListNode *temp = *head; // 创建一个临时指针，指向头节点

    while (temp->next->next != NULL) { // 遍历链表，直到找到倒数第二个节点

        temp = temp->next; // 移动临时指针到下一个节点

    }

    free(temp->next); // 释放尾节点的内存

    temp->next = NULL; // 将倒数第二个节点的next置为NULL

}

              1.4.6 遍历链表

              打印链表中所有节点的数据。代码实现：

              void printList(struct NoHeadSingleListNode *head) {

    struct NoHeadSingleListNode *temp = head; // 创建一个临时指针，指向头节点

    while (temp != NULL) { // 遍历链表，直到链表结束

        printf("%d -> ", temp->data); // 打印当前节点的数据

        temp = temp->next; // 移动临时指针到下一个节点

    }

    printf("NULL\n"); // 打印NULL，表示链表结束

}

                1.4.7 释放链表

                释放链表中所有节点的内存。代码实现：

                void freeList(struct NoHeadSingleListNode *head) {

    struct NoHeadSingleListNode *temp; // 创建一个临时指针

    while (head != NULL) { // 遍历链表，直到链表结束

        temp = head; // 保存当前节点

        head = head->next; // 移动头指针到下一个节点

        free(temp); // 释放当前节点的内存

    }

}

                  1.5 完整代码

                  1.5.1 <no_head_single_list.h>

                  #ifndef NO_HEAD_SINGLE_LIST_H
#define NO_HEAD_SINGLE_LIST_H

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

// 链表节点结构定义

struct NoHeadSingleListNode {

    int data;                           // 数据域，存储节点的数据

    struct NoHeadSingleListNode *next;  // 指针域，指向下一个节点

};

// 函数声明

struct NoHeadSingleListNode *createNode(int data);                  // 动态节点申请

void insertAtHead(struct NoHeadSingleListNode ​**head, int data);    // 单链表头插

void insertAtTail(struct NoHeadSingleListNode ​**head, int data);    // 单链表尾插

void deleteAtHead(struct NoHeadSingleListNode ​**head);              // 单链表头删

void deleteAtTail(struct NoHeadSingleListNode ​**head);              // 单链表尾删

void printList(struct NoHeadSingleListNode *head);                  // 遍历链表

void freeList(struct NoHeadSingleListNode *head);                   // 释放链表

#endif // NO_HEAD_SINGLE_LIST_H

                    1.5.2 <no_head_single_list.h>

                    #include "no_head_single_list.h"

// 动态节点申请

struct NoHeadSingleListNode *createNode(int data) {

    struct NoHeadSingleListNode *newNode = (struct NoHeadSingleListNode *)malloc(sizeof(struct NoHeadSingleListNode)); // 动态分配内存

    if (newNode == NULL) { // 检查内存分配是否成功

        printf("Memory allocation failed!\n"); // 分配失败时输出错误信息

        exit(1); // 退出程序

    }

    newNode->data = data; // 初始化节点的数据域

    newNode->next = NULL; // 初始化节点的指针域为NULL

    return newNode; // 返回新创建的节点

}

// 单链表头插

void insertAtHead(struct NoHeadSingleListNode ​**head, int data) {

    struct NoHeadSingleListNode *newNode = createNode(data); // 创建新节点

    newNode->next = *head; // 新节点的next指向当前头节点

    *head = newNode; // 更新头指针，使其指向新节点

}

// 单链表尾插

void insertAtTail(struct NoHeadSingleListNode ​**head, int data) {

    struct NoHeadSingleListNode *newNode = createNode(data); // 创建新节点

    if (*head == NULL) { // 如果链表为空

        *head = newNode; // 新节点作为头节点

        return; // 结束函数

    }

    struct NoHeadSingleListNode *temp = *head; // 创建一个临时指针，指向头节点

    while (temp->next != NULL) { // 遍历链表，直到找到最后一个节点

        temp = temp->next; // 移动临时指针到下一个节点

    }

    temp->next = newNode; // 将新节点插入到链表尾部

}

// 单链表头删

void deleteAtHead(struct NoHeadSingleListNode ​**head) {

    if (*head == NULL) { // 如果链表为空

        printf("List is empty, cannot delete!\n"); // 输出提示信息

        return; // 结束函数

    }

    struct NoHeadSingleListNode *temp = *head; // 保存头节点

    *head = (*head)->next; // 更新头指针，使其指向下一个节点

    free(temp); // 释放原头节点的内存

}

// 单链表尾删

void deleteAtTail(struct NoHeadSingleListNode ​**head) {

    if (*head == NULL) { // 如果链表为空

        printf("List is empty, cannot delete!\n"); // 输出提示信息

        return; // 结束函数

    }

    if ((*head)->next == NULL) { // 如果链表只有一个节点

        free(*head); // 释放头节点的内存

        *head = NULL; // 将头指针置为NULL

        return; // 结束函数

    }

    struct NoHeadSingleListNode *temp = *head; // 创建一个临时指针，指向头节点

    while (temp->next->next != NULL) { // 遍历链表，直到找到倒数第二个节点

        temp = temp->next; // 移动临时指针到下一个节点

    }

    free(temp->next); // 释放尾节点的内存

    temp->next = NULL; // 将倒数第二个节点的next置为NULL

}

// 遍历链表

void printList(struct NoHeadSingleListNode *head) {

    struct NoHeadSingleListNode *temp = head; // 创建一个临时指针，指向头节点

    while (temp != NULL) { // 遍历链表，直到链表结束

        printf("%d -> ", temp->data); // 打印当前节点的数据

        temp = temp->next; // 移动临时指针到下一个节点

    }

    printf("NULL\n"); // 打印NULL，表示链表结束

}


// 释放链表

void freeList(struct NoHeadSingleListNode *head) {

    struct NoHeadSingleListNode *temp; // 创建一个临时指针

    while (head != NULL) { // 遍历链表，直到链表结束

        temp = head; // 保存当前节点

        head = head->next; // 移动头指针到下一个节点

        free(temp); // 释放当前节点的内存

    }

}

                    1.5.3 <main.c>

                    #include "no_head_single_list.h"

int main() {

    struct NoHeadSingleListNode *head = NULL; // 初始化链表为空

    // 尾插节点

    insertAtTail(&head, 10); // 在链表尾部插入10

    insertAtTail(&head, 20); // 在链表尾部插入20

    insertAtTail(&head, 30); // 在链表尾部插入30

    printf("尾插后链表: ");

    printList(head); // 输出: 10 -> 20 -> 30 -> NULL

    // 头插节点

    insertAtHead(&head, 5); // 在链表头部插入5

    insertAtHead(&head, 1); // 在链表头部插入1

    printf("头插后链表: ");

    printList(head); // 输出: 1 -> 5 -> 10 -> 20 -> 30 -> NULL

    // 头删节点

    deleteAtHead(&head); // 删除链表头部节点

    printf("头删后链表: ");

    printList(head); // 输出: 5 -> 10 -> 20 -> 30 -> NULL


    // 尾删节点

    deleteAtTail(&head); // 删除链表尾部节点

    printf("尾删后链表: ");

    printList(head); // 输出: 5 -> 10 -> 20 -> NULL

    // 释放链表

    freeList(head); // 释放链表占用的内存
    head = NULL; // 将头指针置为NULL
    return 0;
}

                    参考文章

                    C语言数据结构：数组


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

                    相关文章：

                  1. Web元件库 ElementUI元件库+后台模板页面（支持Axure9、10、11）
                  2. Spark 解析_spark.sparkContext.getConf().getAll()
                  3. Kafka详解——介绍与部署
                  4. 【Linux】Bash是什么？怎么使用？
                  5. 森林防火预警广播监控系统：以4G为纽带架构融合智能广播、远程监控、AI智能识别、告警提示、太阳能供电于一体的新一代森林防火预警系统
                  6. LeetCode 392. 判断子序列 java题解
                  7. 在 Ubuntu 中配置 NFS 共享服务的完整指南
                  8. C++ —— 线程同步（互斥锁）
                  9. OpenCV图像拼接（1）概述
                  10. 【Vue3+Vite指南】全局引入SCSS文件后出现Undefined mixin？一招解决命名空间陷阱！
                  11. 机器视觉工程师如何学习C#通讯
                  12. Flask实时监控：打造智能多设备在线离线检测平台（升级版）
                  13. 移动版 Edge ：插件安装功能全面指南
                  14. SpringBoot-MVC配置类与 Controller 的扫描
                  15. 【Java】链表（LinkedList）（图文版）
                  16. QT学习笔记1
                  17. c语言笔记 存储期
                  18. 【实习经历Two:参与开源项目，学习并应用Git】
                  19. 解决qt中自定插件加载失败，不显示问题。
                  20. 报数游戏/补种未成活胡杨[E卷-hw_od]