解锁C/C++：链表数据结构的奇幻之旅

一、引言

在数据结构的广阔领域中，链表作为一种基础且重要的数据结构，占据着不可或缺的地位。链表是一种线性表，但其与数组这种线性表有着显著的区别，链表中的元素在内存中并非连续存储，而是通过指针将各个节点串联起来，这种独特的存储方式赋予了链表在某些操作上的高效性和灵活性。

链表在计算机科学的众多领域都有着广泛的应用。

• 在操作系统中，链表常被用于管理内存分配，通过链表可以有效地跟踪和分配内存块，实现动态内存管理，提高内存的利用率；
• 在文件系统里，链表可以用来表示文件的目录结构，方便文件的查找和管理；
• 在各种算法实现中，链表也是重要的基础，例如在实现栈和队列等数据结构时，链表能够提供高效的插入和删除操作，使得这些数据结构的实现更加简洁和高效 。

C 和 C++ 语言作为强大的编程语言，在实现链表方面具有独特的优势。

• C 语言提供了指针这一强大的工具，使得我们能够直接操作内存地址，从而方便地实现链表节点之间的连接和操作。通过指针，我们可以灵活地分配和释放内存，创建、插入、删除和遍历链表节点。
• 而 C++ 语言在 C 语言的基础上，进一步引入了类和对象的概念，使得链表的实现更加面向对象化，代码的封装性、可读性和可维护性更强。我们可以将链表的操作封装在一个类中，通过类的成员函数来实现链表的各种功能，这样可以更好地组织代码，提高代码的复用性。

在 C 和 C++ 中实现链表，不仅能够深入理解链表这种数据结构的原理和机制，还能锻炼我们对指针、内存管理等重要编程概念的掌握和运用能力。无论是对于学习数据结构和算法的初学者，还是对于有一定编程经验的开发者来说，通过 C 和 C++ 实现链表都是一项非常有价值的实践。它能够帮助我们提升编程技能，培养解决问题的能力，为进一步学习和应用更复杂的数据结构和算法打下坚实的基础。

二、链表基础概念

2.1 链表是什么

链表是一种线性数据结构，它由一系列节点（nodes）组成。每个节点包含两个主要部分：数据域和指针域。数据域用于存储数据元素，而指针域则存储着下一个节点的内存地址，通过指针将各个节点按顺序连接起来，形成一个链式结构 。链表与数组都是线性表，但它们在存储方式和访问方式上有着显著的区别。

在存储方式上，数组在内存中占据连续的存储空间，例如，当我们定义一个包含 5 个整数的数组int arr[5]时，系统会在内存中分配一块连续的、足以容纳 5 个整数的空间来存储这些元素。而链表中的节点在内存中并不要求连续存储，它们可以分散在内存的不同位置，通过指针来建立逻辑上的顺序关系。比如，有三个节点 A、B、C，节点 A 的指针指向节点 B 的内存地址，节点 B 的指针又指向节点 C 的内存地址，这样就形成了一个简单的链表结构，即使 A、B、C 在内存中的实际存储位置并不相邻，也不影响它们通过指针构成链表。

在访问方式上，数组支持随机访问，我们可以通过数组的索引（下标）直接快速地访问到数组中的任何元素。例如，对于数组arr，我们可以使用arr[2]直接访问到数组中的第 3 个元素（数组索引从 0 开始），这种访问方式的时间复杂度为 ，因为无论数组有多大，通过索引访问元素的时间几乎是固定的。而链表不支持随机访问，如果要访问链表中的某个元素，通常需要从头节点开始，沿着指针逐个遍历，直到找到目标节点。例如，要访问链表中第 n 个节点，需要从第一个节点开始，依次通过指针访问下一个节点，直到到达第 n 个节点，这个过程的时间复杂度为 ，其中 n 是链表的长度，链表越长，访问特定节点所需的时间就越长。

2.2 链表的类型

链表根据其结构特点可以分为单向链表、双向链表和循环链表，它们在结构和功能上各有特点。

单向链表是最简单的链表形式，每个节点只包含一个指针，该指针指向下一个节点。在单向链表中，表头指针指向第一个节点，而最后一个节点的指针则为空（通常用 NULL 表示），表示链表的结束。例如，我们有一个单向链表，包含节点 1、节点 2、节点 3，节点 1 的指针指向节点 2，节点 2 的指针指向节点 3，节点 3 的指针为 NULL。单向链表的优点是结构简单，实现容易，占用的内存空间相对较小，因为每个节点只需要存储一个指针。但是它也有明显的缺点，由于只能从前往后遍历，若要访问某个节点的前驱节点（前一个节点），则需要从头开始重新遍历链表，这在某些情况下会导致效率较低。 如在实现一个文本编辑功能时，使用单向链表存储文本内容，当用户需要将光标向上移动一行（即访问前一个节点）时，就需要从链表的头部开始，逐个节点遍历，直到找到前一个节点，这会消耗较多的时间。

双向链表在单向链表的基础上，每个节点增加了一个指向前驱节点的指针。这样，双向链表中的每个节点都有两个指针，一个指向前一个节点，另一个指向后一个节点。表头指针指向第一个节点，表尾指针指向最后一个节点，并且第一个节点的前驱指针和最后一个节点的后继指针都可以根据需要进行设置，通常在双向循环链表中，第一个节点的前驱指针指向最后一个节点，最后一个节点的后继指针指向第一个节点。双向链表的优势在于可以双向遍历链表，大大提高了某些操作的效率。例如，在实现一个双端队列时，使用双向链表可以方便地在队列的两端进行插入和删除操作，因为可以直接通过指针访问到前一个和后一个节点，而不需要像单向链表那样从头遍历。在需要频繁进行插入和删除操作，特别是在已知节点位置的情况下，双向链表的操作效率更高。但双向链表的缺点是每个节点需要额外存储一个指针，因此会占用更多的内存空间，空间复杂度相对较高。

循环链表的特点是链表的尾节点的指针不再指向 NULL，而是指向头节点，从而形成一个闭环。在循环链表中，从任何一个节点出发，都可以遍历到链表中的所有节点，因为链表没有真正的结束点。循环链表又可以分为单向循环链表和双向循环链表。单向循环链表中，节点之间的连接方向是单向的，只能沿着一个方向循环遍历；双向循环链表则结合了双向链表和循环链表的特点，节点可以双向循环遍历。例如，在实现一个循环播放列表时，就可以使用循环链表来存储歌曲信息，当播放到最后一首歌曲时，通过循环链表的特性，可以直接跳转到第一首歌曲继续播放，实现无缝循环播放的效果。循环链表在一些需要循环操作的场景中非常有用，比如操作系统中的进程调度，就可以使用循环链表来管理进程，按照一定的顺序依次调度每个进程，当所有进程都调度一遍后，又回到第一个进程继续调度。

三、C 语言实现链表

3.1 定义链表节点

在 C 语言中，通常使用结构体来定义链表节点。以下是一个简单的单向链表节点定义示例：

// 定义链表节点结构体
typedef struct Node {
   
    int data;           // 数据域，这里假设存储整数，可根据实际需求修改
    struct Node* next;  // 指针域，指向下一个节点
} Node;

在这段代码中，typedef关键字用于为结构体struct Node定义一个别名Node，这样在后续代码中可以更方便地使用Node来声明节点变量。结构体Node包含两个成员：data用于存储数据，next是一个指向struct Node类型的指针，用于指向下一个节点，从而构建链表的链式结构。

3.2 创建链表

创建链表的过程通常包括初始化头节点，以及向链表中添加节点。常见的添加节点方法有头插法和尾插法。
初始化头节点是创建链表的第一步，代码如下：

Node* createList() {
   
    Node* head = (Node*)malloc(sizeof(Node));
    if (head == NULL) {
   
        printf("内存分配失败\n");
        return NULL;
    }
    head->next = NULL;  // 初始化头节点的指针域为NULL，表示链表为空
    return head;
}

上述代码中，createList函数使用malloc函数为头节点分配内存空间，如果内存分配失败，打印错误信息并返回NULL。成功分配内存后，将头节点的next指针设置为NULL，表示这是一个空链表，最后返回头节点指针。
头插法是将新节点插入到链表头部的方法，代码实现如下：

void insertAtHead(Node* head, int data) {
   
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
   
        printf("内存分配失败\n");
        return;
    }
    newNode->data = data;
    newNode->next = head->next;  // 新节点的next指针指向原头节点的下一个节点
    head->next = newNode;        // 头节点的next指针指向新节点，新节点成为新的头节点
}

在insertAtHead函数中，首先为新节点分配内存，若分配失败则打印错误信息并返回。然后将新节点的数据设置为传入的data，接着让新节点的next指针指向原头节点的下一个节点，最后更新头节点的next指针，使其指向新节点，这样新节点就被插入到了链表的头部。
尾插法是将新节点插入到链表尾部的方法，代码实现如下：

void insertAtTail(Node* head, int data) {
   
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
   
        printf("内存分配失败\n");
        return;
    }
    newNode->data = data;
    newNode->next = NULL;

    Node* current = head;
    while (current->next!= NULL) {
   
        current = current->next;  // 找到链表的最后一个节点
    }
    current->next = newNode;  // 将新节点插入到链表的尾部
}

在insertAtTail函数中，同样先为新节点分配内存，若失败则处理错误。将新节点的数据设置好并将其next指针置为NULL。然后通过一个循环找到链表的最后一个节点（即当前节点的next指针为NULL的节点），最后将最后一个节点的next指针指向新节点，完成新节点在链表尾部的插入。

3.3 链表操作

3.3.1 遍历链表

遍历链表是指依次访问链表中的每个节点。通过一个指针从链表的头节点开始，沿着next指针逐个移动，直到指针为NULL，表示到达链表末尾。以下是遍历链表并打印每个节点数据的代码：

void traverseList(Node* head) {
   
    Node* current = head->next;  // 跳过头节点，因为头节点可能不存储实际数据
    while (current!= NULL) {
   
        printf("%d ", current->data);  // 打印当前节点的数据
        current = current->next;      // 移动到下一个节点
    }
    printf("\n");
}

在traverseList函数中，定义了一个current指针，初始化为头节点的下一个节点（如果头节点存储实际数据，则可从head开始）。在循环中，不断打印当前节点的数据，并将current指针移动到下一个节点，直到current为NULL，此时遍历结束，打印换行符。

3.3.2 插入节点

在指定位置插入节点需要先找到插入位置的前一个节点，然后调整指针完成插入。假设要在第pos个位置插入节点（从 1 开始计数），代码实现如下：

void insertAtPosition(Node* head, int data, int pos) {
   
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
   
        printf("内存分配失败\n");
        return;
    }
    newNode->data = data;

    Node* current = head;
    int i;
    for (i = 1; i < pos && current->next!= NULL; i++) {
   
        current = current->next;  // 找到插入位置的前一个节点
    }

    if (i == pos) {
   
        newNode->next = current->next;  // 新节点的next指针指向当前节点的下一个节点
        current->next = newNode;        // 当前节点的next指针指向新节点
    } else {
   
        printf("插入位置无效\n");
        free(newNode);  // 释放分配的内存
    }
}

在insertAtPosition函数中，首先为新节点分配内存，若失败则处理错误。然后通过一个循环找到插入位置的前一个节点（如果pos超过链表长度，则current会指向链表末尾）。如果找到了正确的插入位置（i等于pos），则调整指针将新节点插入到链表中；如果插入位置无效（i不等于pos且current已经到达链表末尾），则打印错误信息并释放新节点分配的内存。

3.3.3 删除节点

删除指定节点需要找到要删除节点的前一个节点，调整指针跳过要删除的节点，并释放被删除节点的内存。假设要删除第pos个节点（从 1 开始计数），代码实现如下：

void deleteNode(Node* head, int pos) {
   
    Node* current = head;
    Node* temp;
    int i;
    for (i = 1; i < pos && current->next!= NULL; i++) {
   
        current = current->next;  // 找到要删除节点的前一个节点
    }

    if (i == pos && current->next!= NULL) {
   
        temp = current->next;       // 保存要删除的节点
        current->next = temp->next;  // 前一个节点的next指针指向要删除节点的下一个节点
        free(temp);                  // 释放要删除节点的内存
    } else {
   
        printf("删除位置无效\n");
    }
}

在deleteNode函数中，通过循环找到要删除节点的前一个节点。如果找到了正确的位置且当前节点的下一个节点存在（即要删除的节点存在），则保存要删除的节点，调整前一个节点的next指针跳过要删除的节点，最后释放要删除节点的内存；如果删除位置无效（i不等于pos或者current已经到达链表末尾且未找到要删除的节点），则打印错误信息。

3.3.4 查找节点

查找特定数据的节点，需要从链表头节点开始，逐个比较节点的数据，直到找到目标节点或遍历完整个链表。以下是查找节点的代码：

Node* searchNode(Node* head, int data) {
   
    Node* current = head->next;
    while (current!= NULL) {
   
        if (current->data == data) {
   
            return current;  // 找到目标节点，返回节点指针
        }
        current = current->next;  // 继续查找下一个节点
    }
    return NULL;  // 未找到目标节点，返回NULL
}

在searchNode函数中，从链表的头节点的下一个节点开始遍历链表。在循环中，每次比较当前节点的数据是否等于目标数据data，如果相等，则返回当前节点的指针，表示找到了目标节点；如果遍历完整个链表都未找到目标数据，则返回NULL。

3.4 完整示例代码

下面是一个完整的 C 语言链表操作示例，包含上述所有功能：