C语言中数组与链表的核心差异及适用场景解析

作为大一B.Tech学生，刚接触数据集合处理时搞不清数组和链表很正常，下面直接拆解两者的核心区别、适用场景，再给你代码示例和练习，帮你快速上手。

一、核心差异 #

• 内存布局：
  数组是连续的内存块，所有元素紧挨着存储；链表是分散的内存块（节点），每个节点通过指针连接，内存地址不连续。
• 访问效率：
  数组支持随机访问，通过索引arr[i]可以直接定位元素，时间复杂度O(1)；链表只能顺序访问，要找第n个元素必须从头节点遍历到目标节点，时间复杂度O(n)。
• 插入/删除效率：
  数组插入或删除中间元素时，需要移动后面所有元素，时间复杂度O(n)；链表插入/删除只需要修改指针指向，不需要移动元素，时间复杂度O(1)（前提是已经找到目标节点）。
• 内存分配：
  数组需要预先分配固定大小的内存（静态数组），或者运行时分配但大小固定（动态数组malloc）；链表是动态分配，每添加一个节点才分配一块内存，不需要预先确定总大小。
• 空间开销：
  数组只存储数据元素，无额外开销；链表每个节点除了存储数据，还要存一个/多个指针（单链表存一个next指针），有额外的内存开销。

二、适用场景 #

优先用数组的情况： #

• 需要频繁随机访问元素（比如根据索引快速取数据、排序算法中交换元素）。
• 数据集合大小固定或可以提前预估，不会频繁扩容。
• 对内存开销敏感，希望尽可能节省内存。
• 场景示例：存储班级学生的考试成绩、查找数组中的最大值/最小值、实现栈（用数组更简单）。

优先用链表的情况： #

• 需要频繁在集合中间或头部/尾部插入、删除元素（比如实现队列、链表版栈）。
• 数据集合大小不确定，需要动态扩容/缩容。
• 场景示例：动态添加的待办事项列表、LRU缓存的底层实现、链表版的队列。

三、实用代码示例 #

1. 数组示例：存储并遍历学生成绩 #

#include <stdio.h>

int main() {
    // 静态数组存储5个学生的成绩
    int scores[5] = {85, 92, 78, 90, 88};
    
    // 随机访问第3个学生的成绩（索引从0开始）
    printf("第3个学生的成绩：%d\n", scores[2]);
    
    // 遍历所有成绩
    printf("所有学生成绩：");
    for (int i = 0; i < 5; i++) {
        printf("%d ", scores[i]);
    }
    printf("\n");
    
    // 修改第2个学生的成绩
    scores[1] = 95;
    printf("修改后第2个学生的成绩：%d\n", scores[1]);
    
    return 0;
}

2. 单链表示例：动态添加并遍历节点 #

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

// 定义链表节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 向链表尾部添加节点
Node* append(Node* head, int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = value;
    new_node->next = NULL;
    
    if (head == NULL) {
        return new_node; // 空链表，新节点作为头节点
    }
    
    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = new_node;
    return head;
}

// 遍历链表
void traverse(Node* head) {
    Node* current = head;
    printf("链表元素：");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

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

int main() {
    Node* head = NULL;
    
    // 动态添加节点
    head = append(head, 10);
    head = append(head, 20);
    head = append(head, 30);
    
    traverse(head);
    
    // 插入节点到头部
    Node* new_head = (Node*)malloc(sizeof(Node));
    new_head->data = 5;
    new_head->next = head;
    head = new_head;
    
    traverse(head);
    
    free_list(head);
    return 0;
}

四、编程练习 #

1. 数组练习：

   • 实现一个函数，接收一个整数数组和长度，返回数组中的最大值和最小值。
   • 实现数组反转：将[1,2,3,4,5]变成[5,4,3,2,1]，要求在原数组上修改，不使用额外数组。

2. 链表练习：

   • 实现一个函数，删除链表中第一个值等于指定值的节点。
   • 实现单链表的反转：将1->2->3->4变成4->3->2->1，要求用迭代方式实现。

3. 对比练习：

   • 分别用数组和链表实现一个简单的待办事项列表，支持添加事项、删除指定位置的事项、遍历所有事项。完成后对比两种实现的代码复杂度和操作效率（比如删除中间元素时的差异）。

内容的提问来源于stack exchange，提问作者BISWAMBAR PRADHAN