学习使用C语言编写基本的数据结构：链表

# 1. 理解数据结构和链表的概念

在计算机科学中，数据结构是指在计算机中组织和存储数据的方式。数据结构的设计直接影响到算法的性能和效率，是程序设计中至关重要的部分。常见的数据结构包括数组、栈、队列、树、图等。而链表是一种基本的数据结构，它由节点组成，每个节点包含数据和指向下一个节点的指针。相较于数组，链表具有动态分配内存的优势，插入和删除操作更加高效。

理解数据结构和链表的概念，不仅有助于设计高效的算法，还能提高代码的可读性和可维护性。深入学习数据结构和链表，将为解决实际问题提供更多的可能性和思路。

# 2. 掌握链表的基本操作

在本章节中，我们将深入掌握链表的基本操作，包括创建链表和遍历链表等内容。

### 创建链表

#### 静态链表与动态链表

静态链表：静态链表是指在程序运行前就分配好内存空间的链表，需要预先指定链表的长度，不灵活。动态链表：动态链表是在程序运行时动态分配内存空间的链表，可以根据需求动态调整链表长度，更灵活。

#### 如何在C语言中创建链表

在C语言中创建链表，首先需要定义节点结构体，包含数据和指向下一个节点的指针。然后通过动态内存分配函数`malloc()`来为节点分配内存空间，并按需连接各节点。

#### 示例代码：创建一个简单的链表

#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;
}

// 创建一个简单的链表：1 -> 2 -> 3
int main() {
    struct Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    struct Node* current = head;
    while(current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
    return 0;
}

### 遍历链表

#### 遍历链表的两种方法

1. 使用循环遍历：从头节点开始，逐个访问每个节点，直到链表末尾为止。
2. 使用递归遍历：通过递归调用的方式依次访问每个节点，直到链表末尾。

#### 如何在C语言中遍历链表

在C语言中，可以使用`while`循环或递归函数来遍历链表。遍历过程中，逐个输出或处理每个节点的数据。

#### 示例代码：遍历操作的实现

// 辅助函数：遍历输出链表
void traverseList(struct Node* head) {
    struct Node* current = head;
    while(current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    // 使用循环遍历链表
    traverseList(head);

    // 或使用递归遍历链表
    void traverseRecursively(struct Node* node) {
        if(node == NU