C语言：链表

链表是一种常见的线性数据结构，其中每个元素（称为节点）包含两部分：数据和指向下一个节点的指针。链表的主要优点是插入和删除操作的时间复杂度较低，但随机访问的效率不如数组。

1. 链表的基本概念

• 节点（Node）：链表的基本单元，包含数据和指向下一个节点的指针。
• 头节点（Head）：链表的第一个节点。
• 尾节点（Tail）：链表的最后一个节点，其指针通常为 NULL。
• 空链表：没有节点的链表，头节点指针为 NULL。

链表是一种常见的数据结构，它由一系列节点组成。每个节点包含两部分：数据部分和指针部分。数据部分用于存储数据，指针部分用于指向下一个节点，从而将各个节点连接起来。链表可以动态地分配内存，方便地进行插入和删除操作。

2. 链表的操作

常见的链表操作包括：

• 插入：在链表的某个位置插入一个新节点。
• 删除：从链表中删除一个节点。
• 查找：在链表中查找一个节点。
• 遍历：遍历链表中的所有节点。

3. 实例

下面是一个用C语言实现单向链表的示例：

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

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

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// 在链表尾部插入节点
void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

// 删除链表中的节点
void deleteNode(Node** head, int data) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }

    if ((*head)->data == data) {
        Node* temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }

    Node* current = *head;
    while (current->next != NULL && current->next->data != data) {
        current = current->next;
    }

    if (current->next == NULL) {
        printf("Node with value %d not found\n", data);
        return;
    }

    Node* temp = current->next;
    current->next = current->next->next;
    free(temp);
}

// 查找链表中的节点
Node* search(Node* head, int data) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == data) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

// 遍历链表并打印所有节点
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 清空链表
void clearList(Node** head) {
    Node* current = *head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    *head = NULL;
}

int main() {
    Node* head = NULL;

    insertAtHead(&head, 10);
    insertAtHead(&head, 20);
    insertAtTail(&head, 30);

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

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

    Node* foundNode = search(head, 30);
    if (foundNode != NULL) {
        printf("Found node with value: %d\n", foundNode->data);
    } else {
        printf("Node not found\n");
    }

    clearList(&head);
    printList(head);  // 输出: NULL

    return 0;
}

• 代码解释

  • 节点结构 Node：包含一个整数 data 和一个指向下一个节点的指针 next。
  • 创建新节点 createNode：分配内存并初始化节点的数据和指针。
  • 在链表头部插入节点 insertAtHead：创建新节点并将其插入到链表的头部。
  • 在链表尾部插入节点 insertAtTail：创建新节点并将其插入到链表的尾部。
  • 删除链表中的节点 deleteNode：从链表中删除指定值的节点。
  • 查找链表中的节点 search：在链表中查找指定值的节点。
  • 遍历链表并打印所有节点 printList：遍历链表并打印所有节点的数据。
  • 清空链表 clearList：释放链表中所有节点的内存并设置头节点为 NULL。
  • 主函数 main:
    • 创建一个空的链表 head。
    • 插入一些节点并打印链表。
    • 删除一个节点并打印链表。
    • 查找一个节点并输出结果。
    • 清空链表并打印链表。

• 运行结果：
  

链表的优势在于其动态大小、高效的插入和删除操作、灵活的内存使用。链表适合需要频繁插入和删除元素的场景，尤其是当元素数量不确定时。