链表和动态数组（从定义到作用）

一、链表

1. 链表的物理结构定义

链表由若干个节点（Node）组成。每个节点在内存中是一个独立分配的堆内存块。节点之间通过存储地址来建立连接。

节点（Node）的结构（用结构体定义）：

struct Node {
int data; // 数据域
struct Node *next; // 指针域，存储下一个节点的起始地址
};

物理内存特征（与数组的本质区别）：

• 数组：所有元素在堆上连续排列（0x1000, 0x1004, 0x1008…）。

• 链表：每个节点由 malloc 独立分配。节点之间的地址不需要连续（例如：节点1在 0x1000，节点2在 0x8000，节点3在 0x2000）。连接它们的唯一依据，是前一个节点 next 指针里存放的地址值。

2. 链表的三大核心组件

3. 创建第一个节点（动态分配）

创建节点的本质是：在堆上申请一块 sizeof(struct Node) 大小的内存，填入数据，并将 next 置为 NULL。

#include <stdlib.h>
struct Node* create_node(int value) {
struct Node *new_node = (struct Node*)malloc(sizeof(struct Node));
if (new_node == NULL) return NULL;
new_node->data = value;
new_node->next = NULL; // 非常重要：新节点的终点必须是 NULL
return new_node;
}

4. 头插法（在链表头部插入节点）

这是链表效率最高的操作（时间复杂度 O(1)），因为你不需要遍历链表。

操作步骤（严格顺序）：

代码实现

void push_front(struct Node **head, int value) {
struct Node *new = create_node(value);
if (new == NULL) return;
new->next = *head; // 新节点指向旧的头节点
*head = new; // 头指针指向新节点
}

5. 遍历链表（访问所有数据）

遍历就是从 head 出发，沿着 next 指针逐一跳转，直到遇到 NULL 为止。核心是使用一个临时指针 cur 来移动，不要直接移动 head（否则会丢失整个链表）。

代码实现：

void print_list(struct Node *head) {
struct Node *cur = head; // 临时指针
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next; // 跳到下一个节点的起始地址
}
}

6. 删除头部节点（唯一不需要遍历的删除）

删除头部节点只涉及 head 指针的移动和内存释放。

操作步骤（必须按此顺序，否则会丢失内存地址）：

代码实现：

void pop_front(struct Node **head) {
if (*head == NULL) return;
struct Node *temp = *head;
*head = (*head)->next;
free(temp);
}

7. 完整的释放整个链表（防止内存泄漏）

你必须逐个节点释放，不能只释放 head，否则后面的节点全部丢失。

void free_list(struct Node *head) {
struct Node *cur = head;
while (cur != NULL) {
struct Node *next = cur->next; // 先保存下一个地址
free(cur); // 释放当前
cur = next; // 移到下一个
}
}

8. 你必须建立的底层认知（与动态数组的关键区别）

二、动态数组

动态数组，是一种在程序运行时，可以根据实际存储的元素数量，自动调整自身内存大小的顺序存储结构。

1.为什么需要动态数组？（对比静态数组）

静态数组与动态数组的区别

结论：静态数组是“死”的，动态数组是“活”的。在写真正的项目（如聊天记录、游戏背包）时，动态数组是必需品。

2.动态数组的内存模型（核心概念）

动态数组在逻辑上是连续的，在物理上（堆内存）也是连续的。为了管理它，我们通常用一个结构体（管家）来捆绑三样东西：

typedef struct {
类型 *data; // ① 仓库钥匙（指向堆内存首地址）
size_t capacity; // ② 仓库总容量（最多能放多少件）
size_t length; // ③ 仓库已用面积（现在放了多少件）
} DynamicArray;

3.七个核心操作与算法要点

一个合格的动态数组，必须包含这七个操作。

1. 初始化（Init）

• 动作：向系统申请第一块地（malloc）。

• 检查：如果 malloc 返回了 NULL，一定要处理，否则后面使用会崩溃。

• 记账：把结构体的 data 指向那块地，capacity 设成申请的大小，length 设为 0。

2. 扩容（Resize / Expand）

• 触发条件：当 length == capacity 时，再添加就装不下了，必须扩容。

• 新容量选择：通常采用 “翻倍策略”（new_cap = capacity * 2）。这样做的目的是把多次扩容的操作均摊到每次插入上，整体效率最高。

• 移动逻辑：扩容不是“原地把墙推倒扩出去”，而是可能整个搬家。

• ⚠️ realloc 陷阱

  // 错误的写法（绝对禁止）
  data = realloc(data, new_size);
  // 如果 realloc 失败返回 NULL，原来的 data 丢失了（内存泄漏且数据丢失）！

  // 正确的写法（必背）
  int *temp = realloc(data, new_size);
  if (temp == NULL) {
  // 处理失败，原 data 依然有效，赶紧撤退
  return false;
  }
  data = temp; // 成功：换新钥匙

3. 尾部添加（Add / Push Back）

• 操作：在最末尾放一个数。

• 步骤：先看需不需要扩容，需要就扩。然后把值放进 data[length] 的位置，最后 length++。

4. 指定位置插入（Insert）—— 移动方向是核心难点

• 场景：在中间的某个下标（比如 index）插入一个数，后面的全部得让位。

• 步骤：

• 检查下标是否合理（index 必须在 0 到 length 之间）。

• 检查容量，满了就扩。

• 关键动作（后移）：必须从最后一个有效元素（length-1）开始，倒着往前搬，直到 index。

  • 为什么必须倒着？ 如果你从 index 开始正着往后搬，会把后面的数据覆盖掉。

• 在空出来的 index 位置放入新值。

• length++。

5. 按位置删除（Delete At）—— 移动方向反着来

• 场景：拿走中间的某个数，后面的要往前补位。

• 步骤：

• 检查下标是否合理（index 必须在 0 到 length-1 之间）。

• （可选）把被删的值存到外面给用户。

• 关键动作（前移）：必须从 index+1 开始，正着往后搬，直到最后。

  • 为什么必须正着？ 如果你倒着往前搬，同样会把前面的数据覆盖错乱。

• length–。

6. 清空（Clear）

• 动作：逻辑上清空。

• 做法：只需一行 length = 0。

• 注意：绝对不要在这里 free(data)！清空是“把货搬走，但仓库留下”，下次还能直接往里堆。

7. 销毁（Destroy）

• 动作：物理上拆除。

• 步骤（必须一步不落）：

• free(data)（把地还给系统）。

• data = NULL（把钥匙销毁，防止变成野指针）。

• capacity = 0; length = 0;（把账本清零，保持一致）。

4.必背的六条铁律（考试/面试常客）

铁律一：范围保护
所有涉及下标访问的操作，必须先判断 index < length。访问越界是C语言最致命的隐形炸弹。

铁律二：内存失败保护
只要用了 malloc 或 realloc，紧跟其后必须有 if (ptr == NULL) 的判断。

铁律三：realloc 必用临时指针
把这条当成肌肉记忆，写错就等着内存泄漏。

铁律四：移动数据的方向感

• 插入时：从后往前（防止被覆盖）。

• 删除时：从前往后（防止被覆盖）。

铁律五：无符号数的减法陷阱
size_t 是无符号的。永远不要写 if (x – y < 0)，因为这是不可能的。请写 if (x < y) 来判断是否越界。

铁律六：销毁后必须“三归零”
free 之后，一定要手动把 data 置 NULL，把长度和容量归零。否则就成了“虽然房子没了，但手里的账本还在说这里有人住”的野指针/悬空引用状态。

三、二者区别

1. 本质区别：地址能不能“心算”出来？

• 动态数组（连续内存）：

  • 地址规则：第 N 个元素地址 = 起始地址 + N × 字节数。

  • 访问代价：CPU 只需要做一次加法运算，就能直接定位到第 N 个元素。这叫 O(1) 随机访问。

  • 硬件优势：因为地址连续，CPU 会提前将相邻元素加载进高速缓存，读数据极快。

• 链表（离散内存）：

  • 地址规则：第 N 个元素地址 = 你得先找到 1 号，让 1 号告诉你 2 号在哪，让 2 号告诉你 3 号在哪……直到 N。

  • 访问代价：想访问第 100 个元素，你必须重复 99 次“取指针→跳转”的操作。这叫 O(N) 顺序访问。

  • 硬件劣势：每个节点的地址都散落在堆的各处，CPU 无法预判下一个地址在哪，只能频繁中断去内存里找，效率较低。

2. 插入/删除操作：你刚才的“感觉”是对的，但你漏看了“搬家费”

• 动态数组（插在头部）：

  • 你确实只需要写 arr[0] = new，但在此之前，你必须把现有的 100 个元素全部往后挪一格。这叫“内存搬移”，成本与数据量成正比。

• 链表（插在头部）：

  • 你只需要执行两步：new->next = head; head = new;。无论链表是 1 个还是 100 万个节点，操作耗时都是固定的。

结论：如果你的需求是“快速查找第 N 个值”，数组完胜；如果你的需求是“不断在头部插入新数据”，链表完胜。

四、从结构体角度解读二者区别

1. 数据存储位置不同

• 动态数组（arryress）：结构体内部只有一个指向堆内存数据区的指针。真正的元素数据在堆上的另一块连续空间中。

• 链表（Node + LinkedList）：结构体内部直接包含数据成员（data）和指向下一个节点的指针（next）。节点本身就是堆内存中一块完整的独立区域。

核心区别：动态数组的“元素”是结构体指向的东西；链表的“节点”就是结构体本身。

2. 结构体是否自引用

• 动态数组（arryress）：结构体成员中没有指向自身类型的指针。它只包含普通指针（ptr_arr）和两个整数。

• 链表（Node）：结构体内部必须包含一个指向自身类型（struct Node *next）的指针。这是链表的必要条件。

核心区别：链表的结构体具有“自引用性”（递归指向自身），动态数组的结构体没有。

3. 管理型结构体与数据型结构体是否分离

• 动态数组（arryress）：没有分离。arryress 结构体同时扮演“数据容器”和“元数据管理器”两个角色（ptr_arr存数据，lengt和arr_count管大小）。

• 链表：严格分离。Node 结构体只负责数据和链接（单一的“数据载具”），LinkedList 结构体专门负责管理（head指向第一个载具，length记录载具数量）。

核心区别：动态数组只有一个结构体类型；链表有两个结构体类型（一个节点，一个管理器）。

4. 结构体大小的确定方式

• 动态数组（arryress）：其 sizeof(arryress) 是固定且确定的（例如 24 字节）。因为它的成员（指针和两个 size_t）在编译时就完全确定了。

• 链表（Node 和 LinkedList）：

  • sizeof(Node) 是固定且确定的（例如 16 字节），但整个链表的大小是“节点大小 × 节点数”，这个总大小在编译时完全未知。

  • sizeof(LinkedList) 也是固定且确定的（例如 16 字节），但它只统计管理信息，不包括任何节点数据。

核心区别：动态数组的元素大小由“数组长度 × 元素大小”在运行时确定；链表的总大小由“节点数 × 节点大小”在运行时确定，但每个节点本身都是独立且大小固定的。

总结

• 动态数组的结构体：只有一份，在栈上，指向堆上一大块连续数据。

• 链表的结构体：有两份，管理者在栈上，节点数据在堆上，且每个节点都是独立分散的独立结构体实体。