链式存储结构C语言如何实现线性表操作？-C语言-盈思创科技

与顺序存储（数组）不同，链式存储不要求逻辑上相邻的元素在物理上也相邻，它通过指针将一系列分散的内存块链接起来，形成一个数据序列。

（图片来源网络，侵删）

核心概念：节点

链表中的每一个元素都被称为一个节点，节点包含两部分：

数据域：存储数据元素本身，可以是任何数据类型（如 int, float, struct 等）。
指针域：存储指向下一个节点的内存地址。

一个典型的节点结构体定义如下：

// 定义节点结构
typedef struct Node {
    int data;             // 数据域，这里以 int 类型为例
    struct Node *next;    // 指针域，指向下一个节点
} Node;

typedef 为 struct Node 定义了一个别名 Node，使得代码更简洁。
struct Node *next; 是关键，它表明这个结构体包含一个指向同类型结构体（即另一个节点）的指针，这种“自己包含自己”的结构是链表的基石。

链表的分类

根据节点间连接方式的不同,链表主要分为以下几种：

单链表：每个节点只包含一个指向下一个节点的指针，这是最基础的形式。
双向链表：每个节点包含两个指针，一个指向前驱节点，一个指向后继节点。
循环链表：链表的最后一个节点的 next 指针不是 NULL，而是指向链表的第一个节点，形成一个环。

下面我们以最常用的单链表为例，进行详细讲解和代码实现。

（图片来源网络，侵删）

单链表的完整 C 语言实现

下面是一个完整的、包含基本操作的单链表实现，代码中包含了详细的注释，解释了每一步的作用。

1. 定义节点和链表结构

#include <stdio.h>
#include <stdlib.h> // 用于 malloc 和 free
// 定义节点结构
typedef struct Node {
    int data;
    struct Node *next;
} Node;
// 为了方便管理，可以定义一个链表结构，包含头指针和链表长度
// 但为了简化，我们这里直接使用一个 Node* 作为头指针来操作
typedef struct {
    Node *head;
    int length;
} LinkedList;

2. 基本操作函数

初始化链表

创建一个“头节点”（不存储数据，仅作为哨兵，简化边界条件判断），并将头指针指向它。

// 初始化链表
void initList(LinkedList *list) {
    // 创建头节点
    list->head = (Node *)malloc(sizeof(Node));
    if (list->head == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    // 头节点的 next 指向 NULL
    list->head->next = NULL;
    list->length = 0;
    printf("链表初始化成功，\n");
}

在链表尾部插入节点

遍历链表找到最后一个节点,然后将新节点连接到它后面。

// 在链表尾部插入节点
void append(LinkedList *list, int value) {
    // 1. 创建新节点
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;
    // 2. 找到链表的最后一个节点
    Node *current = list->head;
    while (current->next != NULL) { // 循环直到 current 是最后一个节点
        current = current->next;
    }
    // 3. 将新节点连接到尾部
    current->next = newNode;
    list->length++;
    printf("在尾部插入元素 %d 成功，\n", value);
}

在链表头部插入节点

这是链表的优势操作,时间复杂度为 O(1)。

（图片来源网络，侵删）

// 在链表头部插入节点
void insertAtHead(LinkedList *list, int value) {
    // 1. 创建新节点
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return;
    }
    newNode->data = value;
    // 2. 将新节点的 next 指向原来的第一个数据节点
    newNode->next = list->head->next;
    // 3. 将头节点的 next 指向新节点
    list->head->next = newNode;
    list->length++;
    printf("在头部插入元素 %d 成功，\n", value);
}

在指定位置插入节点

需要找到插入位置的前一个节点。

// 在指定位置插入节点 (位置从 1 开始)
void insertAtPosition(LinkedList *list, int position, int value) {
    if (position < 1 || position > list->length + 1) {
        printf("插入位置无效！\n");
        return;
    }
    // 1. 创建新节点
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        return;
    }
    newNode->data = value;
    // 2. 找到 position-1 位置的节点
    Node *current = list->head;
    for (int i = 1; i < position; i++) {
        current = current->next;
    }
    // 3. 插入新节点
    newNode->next = current->next;
    current->next = newNode;
    list->length++;
    printf("在位置 %d 插入元素 %d 成功，\n", position, value);
}

删除指定位置的节点

同样需要找到要删除节点的前一个节点。

// 删除指定位置的节点 (位置从 1 开始)
void deleteAtPosition(LinkedList *list, int position) {
    if (position < 1 || position > list->length) {
        printf("删除位置无效！\n");
        return;
    }
    // 1. 找到要删除节点的前一个节点
    Node *current = list->head;
    for (int i = 1; i < position; i++) {
        current = current->next;
    }
    // 2. temp 指向要删除的节点
    Node *temp = current->next;
    // 3. 前一个节点绕过要删除的节点，直接指向下下个节点
    current->next = temp->next;
    // 4. 释放被删除节点的内存
    free(temp);
    list->length--;
    printf("删除位置 %d 的元素成功，\n", position);
}

查找元素

遍历链表,查找第一个匹配的元素。

// 查找元素，返回其位置（从1开始），如果没找到返回-1
int findElement(LinkedList *list, int value) {
    Node *current = list->head->next; // 从第一个数据节点开始
    int position = 1;
    while (current != NULL) {
        if (current->data == value) {
            return position;
        }
        current = current->next;
        position++;
    }
    return -1; // 未找到
}

打印链表

遍历链表并打印所有节点的数据。

// 打印链表
void printList(LinkedList *list) {
    if (list->head->next == NULL) {
        printf("链表为空，\n");
        return;
    }
    Node *current = list->head->next; // 从第一个数据节点开始
    printf("链表内容: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

销毁链表

释放所有动态分配的节点内存,防止内存泄漏。

// 销毁链表，释放所有内存
void destroyList(LinkedList *list) {
    Node *current = list->head;
    Node *nextNode;
    while (current != NULL) {
        nextNode = current->next; // 先保存下一个节点的地址
        free(current);           // 释放当前节点
        current = nextNode;      // 移动到下一个节点
    }
    list->head = NULL;
    list->length = 0;
    printf("链表已销毁，\n");
}

3. 主函数：测试所有操作

int main() {
    LinkedList myList;
    initList(&myList);
    // 测试尾部插入
    append(&myList, 10);
    append(&myList, 20);
    append(&myList, 30);
    printList(&myList); // 预期: 10 -> 20 -> 30 -> NULL
    // 测试头部插入
    insertAtHead(&myList, 5);
    printList(&myList); // 预期: 5 -> 10 -> 20 -> 30 -> NULL
    // 测试指定位置插入
    insertAtPosition(&myList, 3, 15);
    printList(&myList); // 预期: 5 -> 10 -> 15 -> 20 -> 30 -> NULL
    // 测试查找
    int pos = findElement(&myList, 20);
    if (pos != -1) {
        printf("元素 20 的位置是: %d\n", pos); // 预期: 4
    }
    // 测试删除
    deleteAtPosition(&myList, 2); // 删除位置2的元素 (10)
    printList(&myList); // 预期: 5 -> 15 -> 20 -> 30 -> NULL
    // 测试销毁
    destroyList(&myList);
    printList(&myList); // 预期: 链表为空。
    return 0;
}

链式存储 vs. 顺序存储（数组）

特性	链式存储 (链表)	顺序存储 (数组)
空间	不需要预先分配固定大小，按需申请，但每个节点需额外空间存储指针。	需要预先分配连续内存空间，可能导致空间浪费或溢出。
插入/删除	高效，在已知节点位置的情况下，插入和删除操作只需修改指针，时间复杂度为 O(1)。	低效，插入或删除元素需要移动大量后续元素，平均时间复杂度为 O(n)。
随机访问	低效，访问第 `i` 个元素必须从头开始遍历，时间复杂度为 O(n)。	高效，可以通过直接计算地址访问，时间复杂度为 O(1)。
缓存性能	较差，节点在内存中是分散的，访问时容易发生缓存未命中。	较好，元素在内存中是连续的，访问时具有良好的局部性，缓存命中率高。
内存碎片	可能产生较多内存碎片。	产生外部内存碎片。

链表的核心在于节点和指针，它将逻辑上连续的数据通过物理上分散的节点动态链接起来。
优点：插入和删除操作非常快，不需要预先确定大小，内存利用率灵活。
缺点：随机访问效率低，每个节点需要额外的指针空间，实现比数组复杂。

选择使用链表还是数组,取决于具体的应用场景，如果应用需要频繁的插入和删除操作，且不经常需要随机访问，那么链表是更好的选择，反之，如果应用主要是进行大量的随机访问，那么数组会更高效。

链式存储结构C语言如何实现线性表操作？

核心概念：节点

链表的分类

单链表的完整 C 语言实现

1. 定义节点和链表结构

2. 基本操作函数

初始化链表

在链表尾部插入节点

在链表头部插入节点

在指定位置插入节点

删除指定位置的节点

查找元素

打印链表

销毁链表

3. 主函数：测试所有操作

链式存储 vs. 顺序存储（数组）

相关文章

目录[+]