028. 理解链表的构建和遍历

链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表的构建和遍历是C语言编程中的重要技能。以下将详细介绍如何在C语言中构建和遍历链表。

1. 定义链表节点

链表的每个节点通常包含两个部分：数据和指向下一个节点的指针。在C语言中，可以使用结构体来定义链表节点。

示例1：定义链表节点

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

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

2. 构建链表

构建链表通常涉及动态内存分配，使用malloc为每个节点分配内存，并将节点连接起来。

示例2：构建链表

#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("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

int main() {
    // 创建链表
    struct Node *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    return 0;
}

3. 遍历链表

遍历链表是指从链表的头节点开始，逐个访问每个节点，直到链表的末尾（即next指针为NULL）。

示例3：遍历链表

#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("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void printList(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);

    // 遍历链表并打印
    printList(head);

    return 0;
}

输出结果

1 -> 2 -> 3 -> NULL

4. 释放链表内存

在不再需要链表时，应释放链表占用的内存，以避免内存泄漏。

示例4：释放链表内存

#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("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

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

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

int main() {
    // 创建链表
    struct Node *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    // 遍历链表并打印
    printList(head);

    // 释放链表内存
    freeList(head);
    printf("Memory freed\n");

    return 0;
}

输出结果

1 -> 2 -> 3 -> NULL
Memory freed

5. 链表的插入操作

链表的插入操作包括在链表头部、尾部或中间插入节点。

示例5：在链表头部插入节点

#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("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

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

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

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

int main() {
    // 创建链表
    struct Node *head = NULL;
    insertAtHead(&head, 3);
    insertAtHead(&head, 2);
    insertAtHead(&head, 1);

    // 遍历链表并打印
    printList(head);

    // 释放链表内存
    freeList(head);
    printf("Memory freed\n");

    return 0;
}

输出结果

1 -> 2 -> 3 -> NULL
Memory freed

6. 链表的删除操作

链表的删除操作包括删除链表头部、尾部或中间的节点。

示例6：删除链表头部节点

#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("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

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

void deleteAtHead(struct Node **head) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node *temp = *head;
    *head = (*head)->next;
    free(temp);
}

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

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

int main() {
    // 创建链表
    struct Node *head = NULL;
    insertAtHead(&head, 3);
    insertAtHead(&head, 2);
    insertAtHead(&head, 1);

    // 遍历链表并打印
    printList(head);

    // 删除头部节点
    deleteAtHead(&head);
    printf("After deleting head:\n");
    printList(head);

    // 释放链表内存
    freeList(head);
    printf("Memory freed\n");

    return 0;
}

输出结果

1 -> 2 -> 3 -> NULL
After deleting head:
2 -> 3 -> NULL
Memory freed

链表是一种灵活的数据结构，适用于需要动态调整大小的场景。通过上述示例，你可以看到如何在C语言中构建和遍历链表：

定义链表节点：使用结构体定义链表节点。
构建链表：使用动态内存分配创建节点，并将节点连接起来。
遍历链表：从链表头节点开始，逐个访问每个节点。
释放链表内存：使用free释放链表占用的内存。
插入操作：在链表头部、尾部或中间插入节点。
删除操作：删除链表头部、尾部或中间的节点。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)