C语言单链表实现方法详解

简介

单链表是常用的一种数据结构，它由节点组成，每个节点包含两个信息：数据和下一个节点的指针。单链表的优点在于插入和删除元素的效率高，但是随机访问的效率低。

在C语言中，单链表的实现方法非常简单，只需要定义一个节点结构体，再定义相应的节点操作函数，即可实现单链表的操作。

节点结构体

首先，我们需要定义一个节点结构体。每个节点包含两个信息：数据和指向下一个节点的指针。结构体可以定义为以下形式：

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

节点操作函数

创建节点

我们可以定义一个函数，用于创建一个新节点。函数接受一个整数作为参数，创建一个包含该整数的节点，并将节点的指针返回。

struct Node* createNode(int data) {
    struct Node* node = malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

插入节点

我们可以定义一个函数，用于在链表中插入一个新节点。函数接受一个指向链表头结点的指针，以及一个整数作为参数，创建一个包含该整数的节点，并将其插入到链表中。插入操作有两种情况：

1. 在链表的头部插入节点。
2. 在链表的中间或尾部插入节点。

下面是添加节点的代码实现：

void insertNode(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    // 如果链表为空，将新节点作为头结点
    if (*head == NULL) {
        *head = newNode;
    } else {
        struct Node* currentNode = *head;
        while (currentNode->next != NULL) {
            currentNode = currentNode->next;
        }
        currentNode->next = newNode;
    }
}

删除节点

我们可以定义一个函数，用于在链表中删除一个节点。函数接受一个指向链表头结点的指针，以及一个整数作为参数，查找链表中是否包含该整数，并删除该整数所在的节点。删除操作有两种情况：

1. 删除链表的头结点。
2. 删除链表中的中间节点或尾节点。

下面是删除节点的代码实现：

void deleteNode(struct Node** head, int data) {
    // 如果链表为空，无法删除节点
    if (*head == NULL) {
        return;
    }
    struct Node* currentNode = *head;
    struct Node* previousNode = NULL;
    // 遍历链表，查找需要删除的节点
    while (currentNode != NULL && currentNode->data != data) {
        previousNode = currentNode;
        currentNode = currentNode->next;
    }
    // 如果要删除的节点是头结点
    if (previousNode == NULL) {
        *head = currentNode->next;
    } else {
        previousNode->next = currentNode->next;
    }
    free(currentNode);
}

示例

下面是一个使用单链表的示例，用于将一组整数插入到链表中，并输出链表中所有节点的数据：

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

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

struct Node* createNode(int data) {
    struct Node* node = malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

void insertNode(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    // 如果链表为空，将新节点作为头结点
    if (*head == NULL) {
        *head = newNode;
    } else {
        struct Node* currentNode = *head;
        while (currentNode->next != NULL) {
            currentNode = currentNode->next;
        }
        currentNode->next = newNode;
    }
}

void deleteNode(struct Node** head, int data) {
    // 如果链表为空，无法删除节点
    if (*head == NULL) {
        return;
    }
    struct Node* currentNode = *head;
    struct Node* previousNode = NULL;
    // 遍历链表，查找需要删除的节点
    while (currentNode != NULL && currentNode->data != data) {
        previousNode = currentNode;
        currentNode = currentNode->next;
    }
    // 如果要删除的节点是头结点
    if (previousNode == NULL) {
        *head = currentNode->next;
    } else {
        previousNode->next = currentNode->next;
    }
    free(currentNode);
}

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

int main() {
    struct Node* head = NULL;
    for (int i = 1; i <= 5; i++) {
        insertNode(&head, i);
    }
    printf("链表中所有节点的数据：\n");
    printList(head);
    deleteNode(&head, 4);
    printf("删除节点4后，链表中所有节点的数据：\n");
    printList(head);
    return 0;
}

输出结果为：

链表中所有节点的数据：
1 2 3 4 5 
删除节点4后，链表中所有节点的数据：
1 2 3 5 

这个示例演示了如何使用单链表实现插入和删除操作，并输出链表中所有节点的数据。