百科问答小站 logo   百科问答小站
问题

有没有大佬可以详细的讲讲链表？

回答
好嘞，兄弟姐妹们，今天咱们就来唠唠链表这个玩意儿。别看它名字听起来有点“链”来链去的，感觉挺高级，其实它就是数据存储的一种方式，而且是相当灵活的一种。网上那些写得跟教科书一样、一看就是AI批量生产出来的文章，咱们今天就得把它给扒拉出来，用最接地气的方式，把链表讲透了。

咱们先来点开胃菜：什么是链表？

想象一下，你手头有很多张小纸条，每张纸条上都写着一个数据（比如一个数字，或者一个名字）。你想把这些纸条按顺序整理好。

数组是咋干的呢？ 数组就像一个盒子，里面有编号的格子，你可以直接把纸条塞进某个格子（比如第5个格子）。如果你想在第3个格子前面加一张新纸条，你得先把第3、4、5…那些格子里的纸条都挪一挪，腾出位置来。这麻烦不？特别是当你要插入或删除的时候，就得搬来搬去，效率有时候不高。

链表又是咋干的呢？ 链表不给你编号的格子，它让你每张纸条不仅写上数据，还在纸条的背面（或者旁边）写上下一张纸条在哪里。所以，你拿到第一张纸条，看到了数据，然后看到了它指着下一张纸条的位置。你跟着它指的方向找到第二张纸条，又看到数据和下一张纸条的提示，以此类推，直到找到最后一张纸条，它会告诉你“到头了”。

这就好比是一串项链，每一颗珠子都连接着下一颗珠子。所以叫“链表”，名副其实。

链表的核心构成：节点（Node）

每张纸条，在计算机里我们称它为节点（Node）。一个节点通常包含两部分：

1. 数据域（Data）: 就是你这张纸条上真正要存储的信息，比如数字10、字符串“你好”。
2. 指针域（Pointer/Next）: 就是纸条背面的“下一张纸条在哪里”的指示。它指向内存中下一个节点的地址。如果它是链表的最后一张纸条，这个指针就会指向一个特殊的标记，表示“这里是终点”，通常我们叫它`NULL`或者`nullptr`。

链表的“头”和“尾”

头节点（Head）: 链表的第一张纸条，或者说第一个节点。你得知道从哪里开始找，这个“头”就是入口。
尾节点（Tail）: 链表的最后一张纸条，或者说最后一个节点。它的指针域指向`NULL`。

链表的种类：单向链表 vs 双向链表 vs 循环链表

刚才我们说的，每张纸条只指着下一张，这种是最基础的，叫做单向链表（Singly Linked List）。

但是，有时候我们不仅想知道下一张在哪，还想知道上一张在哪，方便往前走。这时候就需要双向链表（Doubly Linked List）。

双向链表的节点：除了数据域和指向下一张纸条的指针（我们叫`next`），它还会有一个指向上一张纸条的指针（我们叫`prev`）。这样，你就可以自由地往前、往后走了。

还有一种叫循环链表（Circular Linked List）。它的特点是，最后一张纸条的指针不是指向`NULL`，而是指向链表的第一个节点，就像项链闭合成了一个圈。

为什么我们要用链表？它的优点在哪？

就像前面说的，相比于数组，链表有几个关键优势：

1. 动态内存分配，大小灵活: 数组一旦创建，大小就固定了，你塞不下就得重新开个更大的数组，然后把旧数据搬过去，麻烦。链表不一样，你随时随地可以创建新节点，添加到链表的任何位置，需要多少内存就申请多少，非常灵活。就像你要加一串珍珠，直接找个地方把新的珍珠串进去就行，不需要把整个项链都拆了重弄。
2. 插入和删除效率高:
在链表头部插入: 只需要创建一个新节点，让它的指针指向原来的头节点，然后更新链表的头指针指向新节点。O(1)复杂度，嗖嗖的。
在链表任意位置插入/删除: 找到要插入/删除位置的前一个节点，稍微修改一下指针就行。虽然找到那个节点可能需要遍历，但一旦找到了前驱节点，插入和删除操作本身只需要O(1)的时间。这比数组需要挪动大量数据高效多了。
3. 内存使用效率: 链表可以分散存储在内存中，不像数组那样要求连续的内存空间。这在内存不充裕或者需要存储大量不连续数据时很有用。

链表的缺点也不能忽略

凡事有利有弊嘛，链表也不是万能的：

1. 查找效率低: 如果你想找链表中的第N个节点，你没法像数组那样直接通过下标“跳”过去，你必须从头节点开始，一个一个地往下找，直到找到第N个。这叫做顺序查找，时间复杂度是O(N)。想随机访问某个元素，链表就比较吃力了。
2. 内存开销大: 每个节点除了存储数据，还要额外存储一个或两个指针，这占用了额外的内存空间。对于存储大量小数据的场景，这可能是一个不小的开销。
3. 无法进行二分查找等高效查找: 由于无法随机访问，那些依赖于快速定位的算法（比如二分查找）在链表上是无法直接使用的。

链表常见的操作：怎么用它？

虽然讲理论很重要，但实际操作更能体现链表的精髓。我们来看看几个常见的链表操作：

创建链表: 就是根据数据创建一系列节点，并将它们按顺序连接起来。
遍历链表: 从头节点开始，沿着指针域一个一个访问每个节点。
插入节点:
头部插入: 创建新节点，新节点的`next`指向原头节点，然后更新链表的头。
尾部插入: 找到最后一个节点，让它的`next`指向新节点，然后更新链表的尾（如果维护了尾指针的话）。
中间插入: 找到要插入位置的前一个节点，让新节点的`next`指向该节点原本的`next`，然后让前一个节点的`next`指向新节点。
删除节点:
删除头节点: 更新链表的头指向原头节点的`next`。
删除尾节点: 找到倒数第二个节点，将其`next`设为`NULL`。
删除中间节点: 找到要删除节点的前一个节点，让它的`next`指向要删除节点`next`的`next`。
查找节点: 从头开始遍历，逐个比较节点数据，直到找到或者遍历结束。

举个实际点的例子：用链表实现一个简单的通讯录（只存名字）

假设我们要存储一系列名字，链表就非常适合。

1. 定义节点结构:
```
struct PersonNode {
string name; // 存储名字
PersonNode next; // 指向下一个人的指针
};
```
2. 创建一个空的通讯录 (头指针为空):
`PersonNode head = nullptr;`
3. 添加一个人（插入到链表末尾）:
创建一个新的 `PersonNode`，比如叫 `newNode`，并存储名字。
让 `newNode>next` 指向 `nullptr`。
如果链表是空的 (`head == nullptr`)，就把 `head` 指向 `newNode`。
如果链表不是空的，就得从 `head` 开始遍历，找到最后一个节点（就是 `next` 是 `nullptr` 的那个），然后把它的 `next` 指向 `newNode`。
4. 查找一个人:
从 `head` 开始遍历。
在每个节点，检查 `name` 是否是我们要找的那个。
如果找到了，就返回那个节点或者一个表示找到的信号。
如果遍历完都没有找到，就表示不存在。
5. 删除一个人:
找到要删除节点的前一个节点（假设叫 `prevNode`）和要删除的节点本身（假设叫 `deleteNode`）。
让 `prevNode>next` 指向 `deleteNode>next`。
然后释放 `deleteNode` 的内存。
处理特殊情况：如果删除的是头节点，需要更新 `head` 指针。

链表在现实中的应用（别以为它只是个概念）

链表可不是书本里的花架子，很多地方都在用它：

操作系统: 实现进程的就绪队列、等待队列等。比如，CPU调度的任务链表。
浏览器历史记录: 后退、前进功能很可能就是用双向链表实现的，方便在页面之间跳转。
音乐播放器: 播放列表的下一首、上一首功能。
内存管理: 内存分配器经常使用链表来跟踪空闲的内存块。
实现其他数据结构: 比如栈、队列，以及哈希表中的冲突解决等。

总结一下，链表这玩意儿

它就像一串串珠子，通过指针一个一个连接起来。

优点: 动态增长、插入删除方便。
缺点: 查找慢、额外内存开销。

理解了链表的核心思想——节点与指针的连接，你就能理解它的各种操作和应用了。下次再看到“链表”，你就知道它不是什么高不可攀的东西，而是你数据世界里一个灵活的小帮手。

希望这篇讲得够详细，也够接地气，别像那些千篇一律的AI文章了。如果还有啥不明白的，随时可以继续问哈！咱们一起把这些基础打牢固了，再去征服更高级的算法和数据结构！

网友意见

user avatar

这么多东西一股脑儿混在一起学确实很麻烦，一样一样来就好了。

既然你觉得动态内存分配和指针学得不扎实，影响你理解链表。那我们先不用动态内存分配和指针，只用普通数组，是不是就可以理解了呢？

       #include <stdio.h>  int main() {     struct node {         char payload;           // 节点的负载数据         int next_index;         // 下一个节点的索引号     };     struct node nodes[16];      // 索引号索引的是这个数组      // 设置 4 个节点，在内存中不连续     nodes[1].payload = 'A';     nodes[1].next_index = 11;      nodes[11].payload = 'B';     nodes[11].next_index = 3;      nodes[3].payload = 'C';     nodes[3].next_index = 7;      nodes[7].payload = 'D';     nodes[7].next_index = -1;   // 用无效的索引号表示链表结束      int head_index = 1;         // 链表头节点索引号      // 遍历输出 A -> B -> C -> D -> END     for (int cur = head_index; cur != -1; cur = nodes[cur].next_index) {         printf("%c -> ", nodes[cur].payload);     }     puts("END");      // 删除位置是 2 的节点（C）     // 如果删除的是 0，就更简单了，调整 head_index 就行     {         // 找到这个位置的前一个节点         int prev_index = head_index;         for (int i = 1; i < 2; i++) {             prev_index = nodes[prev_index].next_index;         }         // 在 B->C->D 里删除 C         // 直接让 B->D 就行了         nodes[prev_index].next_index = nodes[nodes[prev_index].next_index].next_index;     }      // 遍历输出 A -> B -> D -> END     for (int cur = head_index; cur != -1; cur = nodes[cur].next_index) {         printf("%c -> ", nodes[cur].payload);     }     puts("END");      // 在 1 号位置（A 之后）插入新节点     // 如果在 0 插入，就更简单了，调整 head_index 就行     {         // 找到这个位置的前一个节点         int prev_index = head_index;         for (int i = 1; i < 1; i++) {             prev_index = nodes[prev_index].next_index;         }         // 在 A->B 之间插入 X         // 很多网文里说，一定要先让 X->B 再让 A->X         // 没必要这么教条，如果你记录了 B 是什么，完全可以把顺序反过来         int const next_index = nodes[prev_index].next_index;         nodes[prev_index].next_index = 4; // A->X         nodes[4].payload = 'X';         nodes[4].next_index = next_index; // X->B     }      // 遍历输出 A -> X -> B -> D -> END     for (int cur = head_index; cur != -1; cur = nodes[cur].next_index) {         printf("%c -> ", nodes[cur].payload);     }     puts("END"); }

理解之后，你大概率就会觉得索引号用起来太麻烦了，还得写这种又臭又长的：

       // 装修前 nodes[prev_index].next_index = nodes[nodes[prev_index].next_index].next_index

翻翻书，复习一下指针怎么用，就可以把索引号都换成指针，代码也会简洁不少：

       // 装修后 prev->next = prev->next->next;

整个代码就变成了：

       #include <stdio.h>  int main() {     struct node {         char payload;           // 节点的负载数据         struct node *next;      // 下一个节点的指针     };     struct node nodes[16];      // 指针指向的内容都在这个数组里      // 设置 4 个节点，在内存中不连续     nodes[1].payload = 'A';     nodes[1].next = &nodes[11];      nodes[11].payload = 'B';     nodes[11].next = &nodes[3];      nodes[3].payload = 'C';     nodes[3].next = &nodes[7];      nodes[7].payload = 'D';     nodes[7].next = NULL;       // 用空指针表示链表结束      struct node *head = &nodes[1];  // 链表头节点指针      // 遍历输出 A -> B -> C -> D -> END     for (struct node *cur = head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END");      // 删除位置是 2 的节点（C）     // 如果删除的是 0，就更简单了，调整 head_index 就行     {         // 找到这个位置的前一个节点         struct node *prev = head;         for (int i = 1; i < 2; i++) {             prev = prev->next;         }         // 在 B->C->D 里删除 C         // 直接让 B->D 就行了         prev->next = prev->next->next;     }      // 遍历输出 A -> B -> D -> END     for (struct node *cur = head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END");      // 在 1 号位置（A 之后）插入新节点     // 如果在 0 插入，就更简单了，调整 head_index 就行     {         // 找到这个位置的前一个节点         struct node *prev = head;         for (int i = 1; i < 1; i++) {             prev = prev->next;         }         // 在 A->B 之间插入 X         // 很多网文里说，一定要先让 X->B 再让 A->X         // 没必要这么教条，如果你记录了 B 是什么，完全可以把顺序反过来         struct node *const next = prev->next;         prev->next = &nodes[4]; // A->X         nodes[4].payload = 'X';         nodes[4].next = next;   // X->B     }      // 遍历输出 A -> X -> B -> D -> END     for (struct node *cur = head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END"); }

然后你可能觉得写死数组里的索引号太傻了，1、11、3、7、4 什么的一点意义都没有。那么就可以放弃 nodes 数组改用动态分配： 

       #include <stdio.h> #include <stdlib.h>  int main() {     struct node {         char payload;           // 节点的负载数据         struct node *next;      // 下一个节点的指针     };      // 设置 4 个节点，在内存中不连续     struct node *a = malloc(sizeof(struct node));     struct node *b = malloc(sizeof(struct node));     struct node *c = malloc(sizeof(struct node));     struct node *d = malloc(sizeof(struct node));     a->payload = 'A';     a->next = b;     b->payload = 'B';     b->next = c;     c->payload = 'C';     c->next = d;     d->payload = 'D';     d->next = NULL;         // 用空指针表示链表结束      struct node *head = a;  // 链表头节点指针      // 遍历输出 A -> B -> C -> D -> END     for (struct node *cur = head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END");      // 删除位置是 2 的节点（C）     // 如果删除的是 0，就更简单了，调整 head_index 就行     {         // 找到这个位置的前一个节点         struct node *prev = head;         for (int i = 1; i < 2; i++) {             prev = prev->next;         }         // 在 B->C->D 里删除 C         // 直接让 B->D 就行了         prev->next = prev->next->next;     }      // 遍历输出 A -> B -> D -> END     for (struct node *cur = head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END");      // 在 1 号位置（A 之后）插入新节点     // 如果在 0 插入，就更简单了，调整 head_index 就行     struct node *x = malloc(sizeof(struct node));     {         // 找到这个位置的前一个节点         struct node *prev = head;         for (int i = 1; i < 1; i++) {             prev = prev->next;         }         // 在 A->B 之间插入 X         // 很多网文里说，一定要先让 X->B 再让 A->X         // 没必要这么教条，如果你记录了 B 是什么，完全可以把顺序反过来         struct node *const next = prev->next;         prev->next = x;     // A->X         x->payload = 'X';         x->next = next;     // X->B     }      // 遍历输出 A -> X -> B -> D -> END     for (struct node *cur = head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END");      free(a);     free(b);     free(c);     free(d);     free(x); }

然后你觉得，这么长一串代码挤在 main 里看起来太累了，于是简单地封装了几个函数：

       #include <stdio.h> #include <stdlib.h>  struct node {     char payload;           // 节点的负载数据     struct node *next;      // 下一个节点的指针 };  struct list {     struct node *head;      // 链表头节点指针 };  // 初始化 void list_init(struct list *l) {     l->head = NULL;         // 用空指针表示链表结束 }  // 遍历输出 void list_print(struct list *l) {     for (struct node *cur = l->head; cur != NULL; cur = cur->next) {         printf("%c -> ", cur->payload);     }     puts("END"); }  // 指定位置插入节点 void list_insert(struct list *l, int pos, struct node *node) {     if (pos == 0) {         // 如果在 0 插入，就更简单了，调整 head_index 就行         node->next = l->head;         l->head = node;     } else {         // 找到这个位置的前一个节点         struct node *prev = l->head;         for (int i = 1; i < pos; i++) {             prev = prev->next;         }         // 在 A->B 之间插入 X         // 很多网文里说，一定要先让 X->B 再让 A->X         // 没必要这么教条，如果你记录了 B 是什么，完全可以把顺序反过来         struct node *const next = prev->next;         prev->next = node;  // A->X         node->next = next;  // X->B     } }  // 指定位置删除 void list_erase(struct list *l, int pos) {     if (pos == 0) {         // 如果删除的是 0，就更简单了，调整 head_index 就行         l->head = l->head->next;     } else {         // 找到这个位置的前一个节点         struct node *prev = l->head;         for (int i = 1; i < pos; i++) {             prev = prev->next;         }         // 在 B->C->D 里删除 C         // 直接让 B->D 就行了         struct node *const next = prev->next->next;         prev->next = next;     } }  int main() {     struct list l;      list_init(&l);      // 设置 4 个节点，在内存中不连续     struct node *a = malloc(sizeof(struct node));     a->payload = 'A';     list_insert(&l, 0, a);      struct node *b = malloc(sizeof(struct node));     b->payload = 'B';     list_insert(&l, 1, b);      struct node *c = malloc(sizeof(struct node));     c->payload = 'C';     list_insert(&l, 2, c);      struct node *d = malloc(sizeof(struct node));     d->payload = 'D';     list_insert(&l, 3, d);      // 遍历输出 A -> B -> C -> D -> END     list_print(&l);      // 删除位置是 2 的节点（C）     list_erase(&l, 2);      // 遍历输出 A -> B -> D -> END     list_print(&l);      // 在 1 号位置（A 之后）插入新节点     struct node *x = malloc(sizeof(struct node));     x->payload = 'X';     list_insert(&l, 1, x);      // 遍历输出 A -> X -> B -> D -> END     list_print(&l);      free(a);     free(b);     free(c);     free(d);     free(x); }

到目前为止，我们（链表的使用方）都在手动管理内存，链表自身只负责组织节点。

于是我现在表示看 main 结尾的那五个free 不爽，不想自己管理内存了，于是修改一下插入和删除节点的逻辑，再添加一个释放整个链表的函数就可以了：

       // 指定位置插入节点 void list_insert(struct list *l, int pos, char value) {     struct node *node = malloc(sizeof(struct node));     node->payload = value;      if (pos == 0) {         // 如果在 0 插入，就更简单了，调整 head_index 就行         node->next = l->head;         l->head = node;     } else {         // 找到这个位置的前一个节点         struct node *prev = l->head;         for (int i = 1; i < pos; i++) {             prev = prev->next;         }         // 在 A->B 之间插入 X         // 很多网文里说，一定要先让 X->B 再让 A->X         // 没必要这么教条，如果你记录了 B 是什么，完全可以把顺序反过来         struct node *const next = prev->next;         prev->next = node;  // A->X         node->next = next;  // X->B     } }  // 指定位置删除 void list_erase(struct list *l, int pos) {     if (pos == 0) {         // 如果删除的是 0，就更简单了，调整 head_index 就行         struct node *const next = l->head->next;         free(l->head);         l->head = next;     } else {         // 找到这个位置的前一个节点         struct node *prev = l->head;         for (int i = 1; i < pos; i++) {             prev = prev->next;         }         // 在 B->C->D 里删除 C         struct node *const next = prev->next->next;         free(prev->next);         // 直接让 B->D 就行了         prev->next = next;     } }  // 结束 void list_terminate(struct list *l) {     struct node *cur = l->head;     while (cur) {         struct node *const next = cur->next;         free(cur);         cur = next;     } }  int main() {     struct list l;      list_init(&l);      // 设置 4 个节点，在内存中不连续     list_insert(&l, 0, 'A');     list_insert(&l, 1, 'B');     list_insert(&l, 2, 'C');     list_insert(&l, 3, 'D');      // 遍历输出 A -> B -> C -> D -> END     list_print(&l);      // 删除位置是 2 的节点（C）     list_erase(&l, 2);      // 遍历输出 A -> B -> D -> END     list_print(&l);      // 在 1 号位置（A 之后）插入新节点     list_insert(&l, 1, 'X');      // 遍历输出 A -> X -> B -> D -> END     list_print(&l);      list_terminate(&l); }

最后，你想对外隐藏链表的实现细节，于是单独搞了一个头文件。

       #ifndef DEMO_LIST_H_ #define DEMO_LIST_H_  struct list;  // 初始化 struct list *list_init(); // 结束 void list_terminate(struct list *l);  // 遍历输出 void list_print(struct list *l); // 指定位置插入节点 void list_insert(struct list *l, int pos, char value); // 指定位置删除 void list_erase(struct list *l, int pos);  #endif  // DEMO_LIST_H_

当然这样一来，struct list 就不能在栈上创建了，必须使用指针。那么就干脆把 list_init 也改了，整个链表都动态分配：

       // 初始化 struct list *list_init() {     struct list *l = malloc(sizeof(struct list));     l->head = NULL;         // 用空指针表示链表结束     return l; }  // 结束 void list_terminate(struct list *l) {     struct node *cur = l->head;     while (cur) {         struct node *const next = cur->next;         free(cur);         cur = next;     }     free(l); }

这样原来的代码就看上去顺眼多了：

       #include "list.h"  int main() {     struct list *l = list_init();      // 设置 4 个节点，在内存中不连续     list_insert(l, 0, 'A');     list_insert(l, 1, 'B');     list_insert(l, 2, 'C');     list_insert(l, 3, 'D');      // 遍历输出 A -> B -> C -> D -> END     list_print(l);      // 删除位置是 2 的节点（C）     list_erase(l, 2);      // 遍历输出 A -> B -> D -> END     list_print(l);      // 在 1 号位置（A 之后）插入新节点     list_insert(l, 1, 'X');      // 遍历输出 A -> X -> B -> D -> END     list_print(l);      list_terminate(l); }

当然代码是我临时在知乎这个超难用的 Markdown 编辑器里瞎写的，错误处理也没做，但原理是这样的，不保证没有 BUG :D
user avatar

理解链表的确是应该和内存空间分配以及指针联系起来的。但糅合起来前，先把每个元素分别弄清楚会事半功倍。

先说指针。

其实指针很容易理解：比如你声明了一个整型变量A，这个A就对应着内存条上的某几个门电路，你修改A的值就是让这几个门电路记录你给出的某些信息，读取A的值就是从这些门电路把信息读取出来。

既然内存条可以存储8G、16G甚至更多数据，变量A又只占用了其中几个“格子”；那么问题来了：你是怎么从内存条上海量的“格子”中，找到变量A对应的那几个呢？

事实上，为了能够使用内存条，它的每个格子我们都会编个地址。

C系编程语言可以用&A取出变量A对应的那几个格子的地址。比如令int *p=&A，于是就取出一个值0x12397AB0存到指向整型数据的指针p里面去了——意思是变量A的内容就存储在地址0x12397AB0开头的八个格子里（对64位系统来说）。



注意这里一定要清楚区分变量A的值、A这个符号以及变量A的地址三者。


比如，声明变量A，并设置A的值为123，对应的程序语句就是：

       int A=123；

而

       printf("%d", A);

就可以把123打出来。


A这个符号是帮助你记忆的，因此实际程序里最好不要用A、B、C之类没有意义的名字。你应该根据用途，为每个变量起一个含义明确的名字，比如sumOfMoney（现金总计）等。

注意A、sumOfMoney这类符号在程序编译之后就会消失，编译器只会记录变量A对应的地址，不会再记A、sumOfMoney之类东西。因为CPU不需要知道这些。

但这样我们调试程序时就很不方便了，一堆数字谁看得懂什么意思啊。因此我们会要求编译器把程序编译成debug版。这会额外生成个符号表，把内存地址和变量名称联系起来，方便我们理解。


A的地址就是前面提到的0x12397AB0之类东西。这个东西必须在程序运行时才能得到，因为操作系统不一定把你的程序加载到内存条的哪个位置；因此必须程序运行起来了，A才会得到自己的地址（对局部变量的话还必须执行到对应的函数、且函数未曾返回前，这个变量才是有效的）——这就涉及到进程的概念，考验你基础知识牢固程度的时候到了。


这个听起来挺复杂，也的确不好理解。但你可以写个程序，用单步执行跟一下，这些过程就清清楚楚摆在眼前了——写程序，然后单步跟踪，这是理解计算机程序执行过程最大的捷径。

缺乏直观的理解，就容易“学而不思则罔”；实际跟着看一看，把学过的知识回想回想、一点点和实物对应上，直观理解就来了。

当然，你也不能尽信单步跟踪。因为很多东西是编译器相关的、同时还有优化选项的干扰（会使得生成的机器码和你敲出的程序不再对应）；因此需要不停的和C/C++标准对照着看，否则就“思而不学则殆”了。


类似的，指针是一个特殊的变量。比如我们可以定义一个整形指针p：

       int *p=&A;

和普通的变量A一样，指针变量p同样有自己存储的值、自己的名字以及自己的地址。

在这个案例里，指针变量p存储着0x12397AB0，也就是A的地址。或者说，p的值就是0x12397AB0。


p的名字是p，这个是方便我们记忆的——和A一样，就不多说了。


p的地址是&p——没错，指针变量和普通的变量一样，也要在内存中占据若干个格子；它占据的格子同样有地址，我们同样需要借助地址访问它（想起“指针的指针”这种奇怪的东西了吗？其实它就这么简单）。


注意：指针p和内存地址0x12397AB0并不等价。因为0x12397AB0仅仅指向了内存空间某几个格子的起始处；但一个int可能有2个、4个甚至8个字节，也就是占据2~8个格子，仅仅一个0x12397AB0是不包含长度信息的。而int* p这个声明就明确指示了编译器：p指向的地址，也就是0x12397AB0，并不是简单的一个单元格（一个字节），而是足够放下一个int型数据的内存区域。


类似的，我们还可以搞出指针的指针、指针的指针的指针之类东西。你同样可以自己写个程序然后用单步执行跟着看看，从而彻底把这块搞清楚——只听别人讲、看书上说是不够用的；必须自己动手、动脑，彻底把相关概念搞明白。

理工科的东西极重概念。概念不清，后面什么都别想学进去。

再说内存分配。

对PC机来说，内存就是主板上插的内存条。你可以把它理解为一个面积超大的黑板，你的程序、音乐播放器、杀毒软件、操作系统等等，都要在上面“演算”一些东西，也就是都要在上面占据一些空间。

但内存比较贵，空间有限；加上程序太多，大家都要用。那么乱用显然是不行的，不然你演算一半别人把你的内容擦掉你就傻了；或者，你只管用不去擦，别人见上面有内容又不敢擦，那么大片内存空间就会浪费掉，闹得大家都没法干活。


因此，操作系统定下了一些规矩，要求所有程序都必须照规矩使用内存。其中：

  • 程序代码本身因为很少改变，操作系统会按一定规则直接载入内存（还可能加上只读保护，也就是检测并阻止对程序代码占用的内存区的改写动作，从而避免恶意破坏）。
  • 你声明的全局变量、静态变量、字符串常量等也会分别安置在一个固定的内存区域。
  • 程序运行时，不可避免的要调用一些函数；这些函数用到的局部变量会被一个叫做“栈”的数据结构管理；而栈本身可以被CPU指令直接支持，因此速度极快。


其中，栈的大小是动态变化的，由CPU自动维护；但其它区域都是固定不变的——程序一写出来，占用的内存空间大小就确定了。

但这样显然不够用。因为还会有很多无法事先确定空间大小的任务，比如载入一个word文档、一副图片、从硬盘加载一个庞大的游戏地图，等等。

这些功能并不能用栈支持。这是因为栈空间是连续的，栈内存的使用是伴随着函数调用自动分配/归还的，规整而死板（调用函数时，局部变量就得到可用的栈上空间；一旦函数返回，栈上空间就自动归还：因此C语言有很多“返回栈上空间指针”的题目，就是考察你知不知道“不能返回局部变量的指针”）。

然而很多场景里，内存空间的占用时间并不能事先确定——比如说，玩家控制的角色发射了一个“火球”，我们就要为火球分配内存、并且在屏幕上画上一个火球；但这个火球并不能在createFireball这个函数返回后马上删除，而是需要在屏幕上飞行一段时间、击中目标或者超出射程才可以删除它。

如果放到栈上，一旦函数返回，这个火球就会被提前删除；然后如果再调用了其它函数，火球占用的内存空间就会被挪作它用，整个执行逻辑就错乱了。

因此，我们需要一个更灵活的内存管理方式，这就是malloc/new（C系程序员习惯称其为堆分配）。


堆分配说白了也很简单：

  • 你调用malloc/new这个语言提供的库函数/关键字提出需求：老兄，我需要内存！
  • 库函数malloc/关键字new替你调用操作系统API：大哥，给点内存！
  • 操作系统一查，有内存可用；再一查，这次malloc是进程1239调用的；于是记下一笔账：题主启动的、进程id为1239的进程找我要了XX字节内存，将来它退出时我要全部收回！（这里实际上颇为复杂，比如还可能存在内存池之类东西，但现在不用管）
  • malloc拿着操作系统分给你的内存，返回给你：喏，你要的内存空间给你安排好了！
  • 于是，你得到了一个地址；从这个地址开始的、你要求大小的那块内存都是你的（new更复杂一些，它还要调用你的构造函数、帮你初始化这块内存空间，暂不深入讨论）。

这就是所谓的随机内存分配。


归还也一样，你调用free，传入malloc返回给你的那个地址，库函数free就替你把内存归还了——然后操作系统就把你的欠账从小本本上一笔划掉了。


典型的内存分配代码：

       //分配可用存储100个int的内存空间 int* p = malloc(sizeof(int)*100); //malloc返回一个地址，我们把这个地址存储在指针p中，方便将来使用  //使用p指向的内存空间完成工作 ...  //工作完成后，归还内存 //注意malloc会做一个暗记，比如把分配的内存大小存储到p指向的地址的前面几个单元里（不同编译器手法可能不同） //因此这里不需要给free传入待归还的内存大小 //当然，如果你故意搞破坏，比如把p-1位置的内容置零，那么乐子可就大了 free(p);


还记得前面关于指针变量的讨论吗？

没错：

  • 指针变量p被分配在栈上或者其它的固定存储区里（后者对应全局变量/静态变量等情况）
  • p存储的内容是malloc函数返回的一个内存地址


看出不同了吗？

没错：和指针变量p以及常规的变量A不同，我们通过malloc新分配的100个int，它是没有名字的！

它仅仅是一个地址；我们可以想办法用指针p来保存这个地址、也可以把它传递给另一个指针；但它并不像普通的变量那样有一个名字。


这是因为，它是动态分配的内存，是程序执行时才分配的东西，是脱离编译器控制的——前面讨论过，变量名称是方便我们记忆的东西；编译器需要把我们写在程序里的A、p、sumOfMoney等符号自动转换成内存地址。

而malloc分配的东西是运行时才能得到的一块内存，是不可能像其它变量那样直接通过名称使用的。我们必须借助指针p之类东西间接访问它。


那么，你可能就要问了：如果我们的程序很复杂很复杂，比如可能有一千个火球，那该怎么办啊？

总不能这样吧：

       //直接申请1000个火球的空间 //但是1000个火球可能还不够用，因为战斗就有那么激烈！ //但是绝大多数战斗只会同时存在两三个火球，空余1000个火球太浪费空间了！ //我们还得处理火球飞行之类动作。这样是不是每一帧画面就要遍历1000个火球对应的空间？ fireBall *pFireBall=malloc(sizeof(fireBall)*1000);  //怎么办呢？难道这样: //这得占用多少栈空间啊 //而且1000个变量，这程序写出来……成什么狗屎了！ fireBall *pFireBall1=malloc(sizeof(fireBall)); fireBall *pFireBall2=malloc(sizeof(fireBall)); fireBall *pFireBall3=malloc(sizeof(fireBall)); ……


怎么办呢？

没错，上链表。

我们知道，C语言允许我们把基本数据类型组合起来，搞一个自定义数据结构（struct）；甚至还可以在struct里面存放另一个struct，嵌套出复杂的数据结构。那么：

       struct fireBallNode{    fireBall fb; //火球对应的数据结构    fireBallNode* next; //这里指向下一个node节点 };  //现在,用p记录第一个火球对应的内存空间 fireBallNode *p = malloc(fireBallNode); fireBallNode *pHead = p; //记住链表首节点的位置，避免后面搞丢。 //初始化第一个火球 initFireball(p->fb);  //第二个火球继续往后挂 p->next = malloc(fireBallNode); //初始化第二个火球 //也可以是p=p->next; initFireball(p->fb);这种写法和初始化第一个火球完全相同，更方便循环执行 initFireball(p->next->fb);   p=p->next; //让p指向第二个节点，这样接下来的代码形式相同，可以写成循环  //再生成并初始化剩下的998个火球 //其实你可以改写一下，从第一个火球开始就放进循环里，不需要前面两段重复代码 //总之就这个意思，明白了爱怎么写怎么写；不明白就眼花缭乱 for(size_t i=2; i<1000; i++) {   p->next = malloc(fireBallNode);   p=p->next;   initFireball(p->fb); }

你看，就好像链条一样，我们只需一个变量p，就可以灵活管理一大溜的、数量不限的火球了——搞一百万个火球也不怕，我们的程序肯定能处理；只是机器性能/内存容量可能顶不住罢了。


进一步抽象：其实任何需要在运行时灵活决定数量的东西，都可以用类似方式组织数据。

那么我们其实可以做一个通用的实现，这样就不用在管理冰雹、人员或别的什么时，都从头写那么一大堆链表访问链表维护操作代码了：

       struct Node{    void* data; //这里保存用户自己申请的内存空间，随便用户存什么咱都不需要管    Node* next; //这里指向下一个节点，咱靠它帮用户把一拉溜内存空间串起来，别的不需要咱管 };  //为了方便使用，我们需要再定义一组可以方便的操纵链表的接口 //比如增加节点、删除节点，比如链表倒置，等等 //这样就不需要每个项目都重写一遍了 //这就是所谓的“库”  //对火球这个应用来说，你malloc块内存按火球的要求初始化、然后把Node里面的data指针指向这块内存就行了 //可参考前面的代码，把它迁移到这个“库”上面来  //你也可以参考libc的list以及c++的list（c++的list用了泛型，要难懂一些）， //想想这些list该如何用、它们的使用/控制接口是否和你想象的以及课本上的有所不同


你看，就这么土，一点都不神秘。

容易看出，链表这种东西适合存储数量随机、顺序不限的东西。比如游戏里的火球/子弹等对象，比如操作系统里面的内存分配表，比如账务软件里面的流水账，比如一条条的日志信息，等等。

但如果要在上面做搜索、或者需要实现“优先级队列”（比如操作系统的进程列表）、或者有别的稀奇古怪的需求，链表就力不从心了——这时候，就需要队列、栈、树、map等东西出场了。


但总的来说思路是差不多的：想要提高速度、节约空间，那就要用连续内存空间、上各种索引；想要灵活控制空间大小，那就通过类似链表的、借助指针一层层“钩挂”数据的思想来管理数据结构——不同的需求经常还需要把各种思路“杂交”起来（比如各种map就是“增强版”的、便于搜索的数组，但同时为了方便管理也会借助类似链表的手法管理空间、仅仅把key放进排序数组；再比如树就是“增强版链表”，只不过它有两个以上的next指针，分别指向大于/小于当前节点的索引值的其它数据，从而可以在像链表那灵活管理内存的基础能力之外、提供强悍的搜索能力）……于是，五花八门无限复杂的各种数据结构就出现了。


总之，不要把链表及其相关算法当咒语背。这种东西极其实用，自己在机器上实现出来、在项目中用一用，马上就全明白了。

这东西实在太基础了，稍微有一点上机练习、稍微给自己点任务压一压，独立从头发明出来都不难；也必须学到这个水平，将来遇到稍微复杂一点的任务时，才可能随机应变的根据实际需要“捏造”出最适合自己需要的数据结构——这，就是为何说“算法+数据结构=程序”的原因（现在颇有一些半瓶子咣当的家伙喜欢扯淡什么“算法+数据结构=程序已经落伍了、失效了，现在都面向对象了”；只要你稍有经验，就知道那纯属外行扯淡）。

当然，如果你自己不动手、不琢磨，希望别人给你讲懂、希望通过看书看懂……那是绝对不可能的。神仙都学不会。


没错，再强调一遍：链表、树、广义表、各种map……这些东西，自己写出来、发明出来，都不难；因为这本就是程序员们每天都在进行的普通工作，本就应该随手拈来、任意化用的——不然动态创建几个火球你是不是就晕菜了？稍微上点规模的程序里满满当当可都是资源管理！

而且，很多情况下，你还必须结合设计目的正确选择数据结构、甚至不得不因地制宜的综合若干种数据结构之长，这才能简洁高效的实现功能——比如操作系统里面广泛应用的“优先级队列”，你看数据结构这本书里讲过吗？可一但真学会了算法，这玩意你就应该听到名字、稍微一琢磨它的技术要求，自己就马上能发明一个出来。

当然，重复一遍：想走到这一步是不可能一蹴而就的；你必须从语言基础开始逐一夯实基础，尽量理解到“水到渠成”的水准，这才可能真正掌握相关知识。

类似的话题

本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有

服务条款
联系我们
关于我们
隐私政策
友情链接
知乎
百度问答
搜狐
新浪