跳到主要内容

C 语言单链表

介绍​

单链表（Singly Linked List）是一种常见的数据结构，它由一系列节点（Node）组成，每个节点包含数据和指向下一个节点的指针。与数组不同，单链表的节点在内存中不必连续存储，这使得它在插入和删除操作时更加灵活。

单链表的基本结构如下：

每个节点包含两个部分：

  • 数据域：存储实际的数据。
  • 指针域：存储指向下一个节点的地址。

单链表的实现​

定义节点结构​

在C语言中，我们可以使用结构体来定义单链表的节点：

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

创建单链表​

要创建一个单链表，我们需要动态分配内存来存储节点，并将它们连接起来。以下是一个简单的示例，展示如何创建一个包含三个节点的单链表：

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

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

int main() {
    // 创建三个节点
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // 分配内存
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    // 赋值并连接节点
    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    // 遍历链表并打印数据
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");

    // 释放内存
    free(head);
    free(second);
    free(third);

    return 0;
}

输出：

1 -> 2 -> 3 -> NULL
提示

在实际开发中，记得在使用完链表后释放内存，以避免内存泄漏。

单链表的常见操作​

插入节点​

在单链表中插入节点有多种方式，包括在链表头部插入、在链表尾部插入以及在链表中间插入。以下是一个在链表头部插入节点的示例：

c
void insertAtHead(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}

删除节点​

删除节点的操作通常需要找到要删除的节点，并调整前一个节点的指针。以下是一个删除指定值节点的示例：

c
void deleteNode(struct Node** head_ref, int key) {
    struct Node* temp = *head_ref;
    struct Node* prev = NULL;

    // 如果要删除的节点是头节点
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next;
        free(temp);
        return;
    }

    // 查找要删除的节点
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // 如果找到节点，删除它
    if (temp != NULL) {
        prev->next = temp->next;
        free(temp);
    }
}

查找节点​

查找节点的操作通常需要遍历链表，直到找到目标节点或到达链表末尾。以下是一个查找指定值节点的示例：

c
struct Node* searchNode(struct Node* head, int key) {
    struct Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

实际应用场景​

单链表在许多实际应用中都有广泛的使用，例如：

  • 实现栈和队列：单链表可以用于实现栈（LIFO）和队列（FIFO）数据结构。
  • 动态内存管理：单链表可以用于管理动态分配的内存块。
  • 任务调度：在操作系统中，单链表可以用于管理任务队列。

总结​

单链表是一种简单但强大的数据结构，适用于需要频繁插入和删除操作的场景。通过本文，你应该已经掌握了单链表的基本概念、实现方法以及常见操作。希望你能通过实践进一步巩固这些知识。

附加资源与练习​

  • 练习1：实现一个单链表，并编写函数在链表尾部插入节点。
  • 练习2：编写一个函数，反转一个单链表。
  • 练习3：实现一个函数，检测单链表中是否存在环。
备注

如果你在练习中遇到困难，可以参考相关的C语言教材或在线资源，进一步学习和理解单链表的操作。