线性表基础：从定义到链式实现

大家好，我是你们的老朋友。今天我们来聊聊线性表——这个数据结构里最基础、最常用的结构之一。

说实话，我做了十几年嵌入式开发，线性表几乎天天都在用。从传感器数据采集到通信协议栈，到处都有它的影子。你想想看，如果连线性表都搞不明白，后面的栈、队列、树这些就更别想了。

线性表的定义

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

举个例子：一个班级的学生名单、一天的温湿度采样值、一个字符串中的字符——这些都是线性表。

这里有个容易混淆的点：数组下标从0开始，但线性表的位序从1开始。我在项目中见过不少新手因为这个搞出越界bug，嗯，要注意。

顺序存储结构

顺序存储，就是用一块连续的存储空间来存放线性表。说白了就是数组。

它的特点很鲜明：

• 随机存取：O(1) 时间就能访问任意位置
• 插入删除麻烦：平均要移动一半的元素
• 空间固定：一旦分配，扩容很痛苦

我记得有一次做数据采集系统，用了顺序表存采样数据。结果客户突然要求把采样率翻倍，原来的数组大小直接不够用。改代码改得我头皮发麻——这就是顺序存储的典型痛点。

顺序表的实现

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];  // 用数组存数据
    int length;         // 当前长度
} SeqList;

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

// 插入操作
int ListInsert(SeqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) return 0;  // 位置不合法
    if (L->length >= MAXSIZE) return 0;         // 表满了
    
    for (int j = L->length; j >= i; j--) {
        L->data[j] = L->data[j-1];  // 后移元素
    }
    L->data[i-1] = e;
    L->length++;
    return 1;
}

链式存储结构

链式存储就不一样了。每个元素不光存数据，还存一个指针指向下一个元素。这样就不需要连续空间了，东一块西一块都能串起来。

你想想看，这就像寻宝游戏——每个线索指向下一个线索的位置。只要找到头，就能顺着指针走完整个表。

单链表的结构

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} LNode, *LinkList;

每个节点包含两部分：

• 数据域：存放实际数据
• 指针域：存放下一个节点的地址

单链表的基本操作

单链表的操作，核心就是玩指针。我建议你画图理解，光看代码容易晕。

1. 创建链表（头插法）

LinkList CreateList_Head(int n) {
    LinkList L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;  // 带头结点的空链表
    
    for (int i = 0; i < n; i++) {
        LNode *p = (LNode*)malloc(sizeof(LNode));
        scanf("%d", &p->data);
        p->next = L->next;  // 新节点指向第一个节点
        L->next = p;        // 头结点指向新节点
    }
    return L;
}

头插法每次把新节点插在头结点后面。这样最后得到的链表顺序和输入顺序是相反的。如果你想要正序，就用尾插法。

2. 查找操作

// 按位查找
LNode *GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    LNode *p = L;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;  // 如果i大于表长，返回NULL
}

链表的查找只能从头开始遍历，时间复杂度O(n)。这就是为什么我说链表适合"写多读少"的场景。

3. 插入操作

int ListInsert(LinkList L, int i, int e) {
    LNode *p = GetElem(L, i-1);  // 找到第i-1个节点
    if (p == NULL) return 0;
    
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;  // 新节点指向原第i个节点
    p->next = s;        // 前驱节点指向新节点
    return 1;
}

4. 删除操作

int ListDelete(LinkList L, int i, int *e) {
    LNode *p = GetElem(L, i-1);  // 找到前驱
    if (p == NULL || p->next == NULL) return 0;
    
    LNode *q = p->next;  // q是要删除的节点
    *e = q->data;
    p->next = q->next;   // 跳过q
    free(q);              // 释放内存
    return 1;
}

删除操作要注意释放内存。在嵌入式开发中，内存泄漏是大事。我有个项目就是因为频繁malloc/free导致内存碎片，最后系统跑着跑着就挂了。

顺序表 vs 链表：怎么选？

对比项	顺序表	单链表
存取方式	随机存取 O(1)	顺序存取 O(n)
插入/删除	平均 O(n)	O(1)（已知位置）
空间分配	静态，一次性分配	动态，按需分配
存储密度	高（只存数据）	低（还要存指针）
适用场景	读多写少，大小已知	写多读少，大小不确定

我个人习惯是：能用顺序表就用顺序表。为什么？因为数组的缓存局部性好，CPU访问起来快。链表虽然插入删除方便，但指针跳来跳去，缓存命中率低，实际性能往往不如预期。

知识体系总览

下面这张图把本章的核心内容串起来了，你可以对照着复习：

好了，线性表的基础就讲到这里。顺序表和链表各有千秋，关键是根据实际场景选对工具。下一节我们会深入栈和队列，你会发现它们本质上就是受限的线性表——有了今天的基础，后面学起来会轻松很多。

---

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