C语言如何实现动态链表

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表的大小可以动态调整，因此在需要频繁插入和删除操作的场景中，链表比数组更加高效。本文将介绍如何使用C语言实现一个动态链表。

1. 链表的基本概念

链表中的每个节点通常包含两个部分： - 数据域：存储节点的数据。 - 指针域：存储指向下一个节点的指针。

链表可以分为单向链表、双向链表和循环链表等类型。本文主要介绍单向链表的实现。

2. 定义链表节点结构

在C语言中，我们可以使用结构体来定义链表的节点。每个节点包含一个数据域和一个指向下一个节点的指针。

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

// 定义链表节点结构
struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域，指向下一个节点
};

3. 创建链表

创建链表的过程通常包括以下几个步骤： 1. 创建头节点。 2. 逐个添加新节点。

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

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

4. 遍历链表

遍历链表是指依次访问链表中的每个节点，并输出或处理节点的数据。

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

5. 插入节点

在链表中插入节点通常有三种情况： 1. 在链表头部插入节点。 2. 在链表中间插入节点。 3. 在链表尾部插入节点。

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

// 在链表中间插入节点
void insertAfter(struct Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("前一个节点不能为空\n");
        return;
    }
    struct Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

6. 删除节点

删除链表中的节点通常有两种情况： 1. 删除链表头部节点。 2. 删除链表中间或尾部节点。

// 删除链表头部节点
void deleteAtHead(struct Node** head) {
    if (*head == NULL) {
        printf("链表为空，无法删除\n");
        return;
    }
    struct Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

// 删除链表中的指定节点
void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;
    struct Node* prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("未找到要删除的节点\n");
        return;
    }

    prev->next = temp->next;
    free(temp);
}

7. 释放链表

在使用完链表后，应该释放链表占用的内存，以避免内存泄漏。

// 释放链表
void freeList(struct Node* head) {
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

8. 完整示例

下面是一个完整的示例程序，展示了如何创建、插入、删除和遍历链表。

#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));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void appendNode(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        struct Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

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

void insertAtHead(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

void insertAfter(struct Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("前一个节点不能为空\n");
        return;
    }
    struct Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

void deleteAtHead(struct Node** head) {
    if (*head == NULL) {
        printf("链表为空，无法删除\n");
        return;
    }
    struct Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

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

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("未找到要删除的节点\n");
        return;
    }

    prev->next = temp->next;
    free(temp);
}

void freeList(struct Node* head) {
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    struct Node* head = NULL;

    appendNode(&head, 10);
    appendNode(&head, 20);
    appendNode(&head, 30);

    printf("初始链表: ");
    printList(head);

    insertAtHead(&head, 5);
    printf("在头部插入5后的链表: ");
    printList(head);

    insertAfter(head->next, 15);
    printf("在20后插入15后的链表: ");
    printList(head);

    deleteAtHead(&head);
    printf("删除头部节点后的链表: ");
    printList(head);

    deleteNode(&head, 20);
    printf("删除20后的链表: ");
    printList(head);

    freeList(head);

    return 0;
}

9. 总结

本文介绍了如何使用C语言实现一个动态链表。通过定义节点结构、创建链表、插入节点、删除节点以及遍历链表等操作，我们可以灵活地管理链表中的数据。链表在处理动态数据时具有很大的优势，尤其是在需要频繁插入和删除操作的场景中。希望本文能帮助你理解并掌握链表的基本操作。