链表的应用：从内存管理到缓存淘汰
引言：链表之美
在计算机科学中，链表以其灵活多变的特性闪耀着独特的光芒。它不像数组那样需要连续的存储空间，而是通过指针将离散的内存单元优雅地串联起来，这种特质使其在众多领域大放异彩。
本文将探索链表在操作系统内存管理和缓存淘汰算法中的精妙应用。
一、链表在操作系统内存管理中的应用
1.1 内存碎片问题
想象一下，当我们向操作系统申请一片连续内存空间时，系统满足了请求。随后通过 malloc 申请了另一块内存，原有的内存版图便发生了变化：
void* memory = malloc(4 * 1024 * 1024 * 1024); // 申请 4GB
void* chunk1 = malloc(1 * 1024 * 1024 * 1024); // 申请 1GB
此时，原本完整的内存被分割成了已分配块和剩余的空闲块。由于内存对齐等因素，空闲内存可能会形成多个不连续的碎片。
1.2 链表：内存碎片的'穿线者'
操作系统如何管理这些分散的内存碎片？答案就是链表！系统会将不同的内存碎片通过指针串联起来，形成一个空闲内存链表。
这种链表结构的美妙之处在于：
- 动态管理：可以随时插入或删除节点，适应内存的分配与释放。
- 空间高效：仅需少量指针空间即可维护整个内存区域。
- 灵活性：不同大小的内存块可以共存于同一链表中。
当程序再次申请内存时，系统会遍历这个链表，寻找合适大小的内存块（首次适应、最佳适应等策略）。
二、缓存：速度与容量的优雅平衡
2.1 缓存的概念
缓存是位于高速设备与低速设备之间的一种临时存储区域，用于减少访问低速设备的次数，提高系统整体性能。
2.2 缓存的工作原理
以硬盘和内存为例，构建一个缓存工作的场景：
- CPU
- L1 Cache
- L2 Cache
- 主内存
- 硬盘
从上到下速度递减，容量递增。假设硬盘中有大量数据，而内存中仅有少量缓存空间。当 CPU 需要数据时：
- 首先查询内存缓存（命中则直接使用）。
- 若未命中，则从硬盘读取数据，并按照一定策略存入缓存。
2.3 缓存内部的数据结构
缓存内部最简单的实现方式是使用链表：
typedef struct CacheNode {
void* data;
size_t size;
} CacheNode;
