线性表基础：从数组到链表，我踩过的那些坑

大家好，我是你们的老朋友。今天咱们聊聊线性表——这个数据结构里最基础、也最容易被忽视的东西。

说实话，我刚开始学C语言那会儿，觉得线性表不就是数组嘛，有啥好讲的？直到后来做嵌入式项目，内存紧张得要命，才发现数组和链表的选择，直接决定了你的程序能不能跑起来。

嗯，咱们今天就把线性表掰开揉碎了讲清楚。

什么是线性表？

线性表，说白了就是一组数据排成一排。每个元素有且只有一个前驱和一个后继（除了头和尾）。

你想想看，排队买奶茶的队伍，就是线性表。第一个人后面跟着第二个人，第二个人后面跟着第三个人……就这么简单。

但在计算机里，实现线性表有两种主流方式：

• 顺序存储——用数组实现，数据在内存里是挨着的
• 链式存储——用链表实现，数据在内存里东一个西一个，靠指针串起来

这两种方式各有各的脾气，咱们一个一个说。

顺序存储结构：数组实现

数组，大家太熟了。但你真的会用吗？

我在项目中遇到过一件事：一个同事用数组存传感器数据，每次插入新数据就把后面的全往后挪。数据量小的时候没事，后来传感器频率一高，CPU直接跑满。为什么？因为数组插入的时间复杂度是O(n)，你想想看，挪一次还好，挪一万次呢？

数组的优点很明显：

• 随机访问快——O(1)就能拿到第i个元素
• 内存连续，缓存友好
• 实现简单，代码量少

缺点也很致命：

• 插入和删除要移动大量元素
• 大小固定，扩容麻烦
• 容易浪费内存（你申请了100个，只用了10个）

来看一个简单的数组实现：

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int length;  // 当前元素个数
} SeqList;

// 初始化
void initList(SeqList *L) {
    L->length = 0;
}

// 插入元素（在第i个位置插入e）
int insertElem(SeqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) return -1;  // 位置不合法
    if (L->length >= MAX_SIZE) return -1;       // 表满了

    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j-1];  // 从后往前挪
    }
    L->data[i-1] = e;
    L->length++;
    return 0;
}

// 删除第i个元素
int deleteElem(SeqList *L, int i) {
    if (i < 1 || i > L->length) return -1;

    for (int j = i; j < L->length; j++) {
        L->data[j-1] = L->data[j];  // 从前往后挪
    }
    L->length--;
    return 0;
}

链式存储结构：单链表实现

链表就不一样了。每个节点不光存数据，还存一个指向下一个节点的指针。就像寻宝游戏，每个线索指向下一个线索。

我建议你记住这个比喻：数组是住集体宿舍，大家门挨着门；链表是住别墅，每家每户有路牌指向下一家。

链表的优点：

• 插入和删除快——O(1)，只要改指针就行
• 动态扩容——用多少就申请多少
• 不浪费内存（除了指针本身的开销）

缺点：

• 不能随机访问——要找第i个，得从头一个个数过去
• 每个节点多存一个指针，内存开销大
• 缓存不友好——节点在内存里东一个西一个

来看单链表的实现：

typedef struct Node {
    int data;
    struct Node *next;
} Node, *LinkList;

// 初始化（带头节点）
void initList(LinkList *L) {
    *L = (Node*)malloc(sizeof(Node));
    (*L)->next = NULL;
}

// 头插法
void headInsert(LinkList L, int e) {
    Node *s = (Node*)malloc(sizeof(Node));
    s->data = e;
    s->next = L->next;
    L->next = s;
}

// 尾插法
void tailInsert(LinkList L, int e) {
    Node *p = L;
    while (p->next != NULL) {
        p = p->next;
    }
    Node *s = (Node*)malloc(sizeof(Node));
    s->data = e;
    s->next = NULL;
    p->next = s;
}

// 删除值为e的节点
int deleteNode(LinkList L, int e) {
    Node *p = L;
    while (p->next != NULL && p->next->data != e) {
        p = p->next;
    }
    if (p->next == NULL) return -1;  // 没找到

    Node *q = p->next;
    p->next = q->next;
    free(q);
    return 0;
}

基本操作：增删改查

不管是数组还是链表，核心操作就四个：增、删、改、查。咱们对比着看：

操作	数组（顺序表）	单链表
查找（按值）	O(n)，从头扫到尾	O(n)，也得从头扫
查找（按位置）	O(1)，直接下标访问	O(n)，得一个个数过去
插入	O(n)，要挪元素	O(1)，改指针就行
删除	O(n)，要挪元素	O(1)，改指针就行
修改	O(1)，直接赋值	O(n)，先找到再改

看到没？没有绝对的好坏。如果你的程序频繁查找，用数组；如果频繁插入删除，用链表。

我曾经在一个嵌入式项目里，需要维护一个任务队列。任务频繁添加和删除，但很少查找。我一开始用了数组，结果每次插入都要挪动几百个元素，CPU占用率飙升。后来改成链表，问题立刻解决了。

嗯，这就是经验。

知识体系总览

下面这张图，把咱们今天讲的内容串起来了：

好了，线性表的基础就讲到这里。记住，数据结构没有好坏，只有合不合适。下次写代码前，先想想你的数据是怎么用的——是频繁查找还是频繁插入？想清楚了，选型就简单了。

我是你们的嵌入式老司机，咱们下期见。

---

公众号:蓝海资料掘金营，微信deep3321