一、前置知识：什么是线性结构与抽象数据类型

在正式学习两种结构前，我们先理清基础概念。

早期编程使用机器语言，直接操作二进制和内存地址，存储、运算数据既低效又容易出错。于是高级语言引入数据类型，屏蔽了底层内存细节，还能校验运算合法性。

在此基础上延伸出抽象数据类型（ADT）：它是一个数学模型 + 一组配套操作，只定义数据范围和可执行行为，不限制具体实现。就像游戏角色马里奥，定义了前进、跳跃、射击等动作，至于代码如何实现并不关心。

而线性结构是一类特殊的数据组织形式，满足三条规则：

1. 除首尾元素外，每个元素仅有一个前驱、一个后继；
2. 第一个元素没有前驱；
3. 最后一个元素没有后继。

简单理解：数据像一条笔直的队伍，前后顺序固定，顺序表和单向链表，都是线性结构的落地实现。

二、顺序表：连续内存的线性表

2.1 基本概念

顺序表是利用一组地址连续的存储单元，依次存放线性表数据元素的结构，在 C 语言中底层由数组实现。 它的逻辑顺序和物理内存顺序完全一致，所有数据紧密排列，中间没有空闲空间。

内存布局示例：

下标:  [0]   [1]   [2]   [3]   [4]
数据:  10    20    30    40    50
地址: 0x100 0x104 0x108 0x10C 0x110

顺序表支持增、删、改、查、插入五大基础操作。

2.2 核心操作原理

1. 插入元素

插入分为三种场景：表头插入、中间插入、尾部插入，核心逻辑一致：

1. 将插入位置及后续所有元素整体向后移动一位，腾出空位；
2. 把新元素放入空位，表长度加一。

示例：在 {1,2,4,5,6,7} 第三个位置插入 3 原序列：1 2 4 5 6 7 元素后移：1 2 4 5 6 7 插入完成：1 2 3 4 5 6 7

2. 删除元素

找到目标元素后，将该元素后续所有数据整体向前移动一位，间接覆盖目标元素，最后表长度减一。

2.3 时间复杂度与优缺点

时间复杂度

• 随机访问（按下标查找）：\(O(1)\)。依靠下标直接定位，效率极高；
• 按值查找、中间 / 头部增删：\(O(n)\)。需要遍历或移动大量元素；
• 尾部增删：\(O(1)\)。无需移动元素，仅修改长度即可。

优点

1. 支持随机访问，查询速度快；
2. 内存连续，无额外冗余数据，空间利用率高。

缺点

1. 长度固定，初始化时必须指定最大容量，扩容需要重新开辟内存并拷贝所有数据，灵活性差；
2. 提前分配内存，容易出现空间不足或空间浪费的问题；
3. 在头部、中间位置插入 / 删除数据时，需要大量移动元素，效率低下。

2.4 适用场景

适合查询操作频繁、增删操作少、数据量相对固定的业务场景，例如静态配置表、固定人员名单等。

2.5 C 语言完整实现

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

#define MAX_SIZE 100  // 顺序表最大容量

// 定义顺序表结构体
typedef struct {
    int data[MAX_SIZE];
    int length;  // 当前元素个数
} SeqList;

// 初始化顺序表
void init(SeqList *L) {
    L->length = 0;
}

// 按下标插入元素
int insert(SeqList *L, int i, int x) {
    if (i < 0 || i > L->length || L->length >= MAX_SIZE) {
        return 0; // 插入失败
    }
    // 元素后移
    for (int j = L->length; j > i; j--) {
        L->data[j] = L->data[j - 1];
    }
    L->data[i] = x;
    L->length++;
    return 1;
}

// 按下标删除元素
int delete(SeqList *L, int i) {
    if (i < 0 || i >= L->length) {
        return 0; // 删除失败
    }
    // 元素前移
    for (int j = i; j < L->length - 1; j++) {
        L->data[j] = L->data[j + 1];
    }
    L->length--;
    return 1;
}

// 按值查找，返回下标，未找到返回-1
int find(SeqList *L, int x) {
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == x)
            return i;
    }
    return -1;
}

// 打印顺序表
void print(SeqList *L) {
    for (int i = 0; i < L->length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

三、单向链表：指针串联的动态线性表

为了解决顺序表长度固定、增删低效的问题，链表应运而生。链表是使用场景第二广的通用数据结构，而单向链表是链表中最简单的形态。

3.1 基本概念

单向链表的特点：物理内存不连续，逻辑顺序连续。它依靠节点和指针串联所有数据。 每个节点分为两部分：

• 数据域：存储业务数据；
• 指针域：存储下一个节点的内存地址，用来连接节点。

逻辑结构：[数据|指针] → [数据|指针] → [数据|指针] → NULL

重要概念：头指针 & 头结点

1. 头指针：必备元素，指向链表第一个节点，是访问整个链表的入口；
2. 头结点：可选的虚拟节点，一般不存储有效数据。

带头结点是开发主流写法：空链表、非空链表、表头插入删除，都可以使用同一套代码逻辑，无需额外特殊判断，大幅降低代码复杂度。而不带头结点的链表，操作首元素时需要单独处理，实用性较差。

3.2 核心操作原理

单向链表所有操作本质都是修改指针指向，无需移动数据。

1. 插入节点：找到目标前驱节点，修改指针指向即可完成插入；
2. 删除节点：必须先找到被删节点的前驱节点，让前驱节点的指针跳过目标节点，最后释放内存。

3.3 时间复杂度与优缺点

时间复杂度

• 已知位置的增删操作：\(O(1)\)，仅修改指针，效率极高；
• 查找、定位节点：\(O(n)\)，不支持随机访问，必须从表头逐个遍历。

优点

1. 动态内存分配，无需提前指定容量，长度不受限制，也不会造成空间浪费；
2. 任意位置增删节点效率高，无需移动大量数据；
3. 内存无需连续，对内存碎片化场景友好。

缺点

1. 无法随机访问，查找元素只能顺序遍历；
2. 每个节点都附带指针域，存在额外内存开销；
3. 指针操作复杂，容易出现断链、野指针等问题，调试难度高。

3.4 适用场景

适合数据量不确定、频繁执行插入 / 删除操作的场景，例如消息队列、动态列表等。

3.5 C 语言完整实现

1. 节点定义与初始化

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

// 定义链表节点
typedef struct ListNode {
    int data;
    struct ListNode* next;
} Node, *LinkList;

// 初始化带头结点的空链表
LinkList InitList() {
    Node* h = (Node*)malloc(sizeof(Node));
    if (h == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    h->next = NULL;
    return h;
}

2. 基础功能：头插、尾插、查找、插入、删除、求长度

// 头插法
LinkList Head_insert(LinkList l, int k) {
    Node* s = (Node*)malloc(sizeof(Node));
    s->data = k;
    s->next = l->next;
    l->next = s;
    return l;
}

// 尾插法
LinkList Rear_insert(LinkList l, int k) {
    Node* p = l;
    while (p->next != NULL)
        p = p->next;
    Node* s = (Node*)malloc(sizeof(Node));
    s->data = k;
    s->next = NULL;
    p->next = s;
    return l;
}

// 按值查找节点
Node* find(LinkList l, int x) {
    Node* p = l->next;
    while (p != NULL && p->data != x)
        p = p->next;
    return p;
}

// 在指定值之后插入元素
LinkList Insert(LinkList l, int x, int k) {
    Node* p = find(l, x);
    if (p == NULL) {
        printf("目标数据不存在\n");
        return l;
    }
    Node* s = (Node*)malloc(sizeof(Node));
    s->data = k;
    s->next = p->next;
    p->next = s;
    return l;
}

// 按值删除节点
LinkList Delet(LinkList l, int k) {
    if (l->next == NULL) {
        printf("链表为空\n");
        return l;
    }
    Node* p = l;
    Node* q = l->next;
    while (q != NULL && q->data != k) {
        p = q;
        q = q->next;
    }
    if (q == NULL) {
        printf("待删除数据不存在\n");
        return l;
    }
    p->next = q->next;
    free(q);
    q = NULL;
    return l;
}

// 获取链表长度
int get_size(LinkList l) {
    int sum = 0;
    Node* p = l->next;
    while (p != NULL) {
        sum++;
        p = p->next;
        sum++;
        p = p->next;
    }
    return sum;
}

3. 主函数测试

int main() {
    LinkList l = InitList();
    // 头插
    l = Head_insert(l, 3);
    l = Head_insert(l, 2);
    l = Head_insert(l, 1);
    // 尾插
    l = Rear_insert(l, 4);
    l = Rear_insert(l, 5);
    // 指定位置插入
    l = Insert(l, 4, 9);
    // 删除元素
    l = Delet(l, 5);
    // 输出长度
    printf("链表长度：%d\n", get_size(l));
    return 0;
}

四、顺序表 VS 单向链表 全面对比

对比维度	顺序表	单向链表
内存存储	物理地址连续	物理地址分散，逻辑连续
访问方式	支持随机访问，\(O(1)\)	仅顺序遍历，\(O(n)\)
增删效率	头尾增删\(O(1)\)，中间 / 头部\(O(n)\)	已知位置增删\(O(1)\)
空间特性	预分配内存，易浪费 / 不足，无额外开销	动态分配，有指针内存开销
容量	固定，扩容复杂	动态可变，灵活
适用场景	查询多、增删少、数据固定	频繁增删、数据量不确定