内存中用链表模拟FAT，本质是动态管理块索引信息：每个节点含block_id、status和next_block，按需分配、避免空间浪费，并支持alloc串联、free合并及哈希加速查找。
内存中模拟文件分配表（fat），本质不是复制磁盘上的fat结构，而是用链表管理“块索引信息”——即把每个磁盘块的归属、状态和链接关系，用动态节点组织起来。它不追求与硬件fat完全一致，而是抓住其核心思想：用轻量、可增删的结构描述离散块之间的逻辑顺序。
为什么用链表模拟FAT，而不是数组
真实FAT是固定大小的数组，索引直接对应簇号；但在内存模拟中，若文件系统只管理少量活跃块，或块编号稀疏（如只用了簇3、17、92），用数组会造成大量空槽浪费。链表则按需创建节点，每个节点存三要素：
- 簇号（block_id）：标识这是第几号磁盘块
- 状态（status）：FREE / ALLOCATED / BAD / EOF
- 下一簇（next_block）：若当前块属于某文件，则存后续块号；否则为-1
这样既避开预分配空间，又保留了FAT“通过单次查表定位任意块”的能力——只需遍历链表找指定 block_id，拿到 next_block 就能跳转，无需从头顺链扫描整个文件。
alloc操作：如何为文件分配并串联新块
分配一个新块给某文件时，不是孤立记录，而是嵌入已有链路：
- 若文件为空（无起始块），新建节点，设 status = ALLOCATED，next_block = -1，并插入链表头部或按 block_id 排序位置
- 若文件已有末尾块 A，先定位 A 节点，将其 next_block 改为新块号；再新建节点描述该新块，next_block 设为 -1
- 所有节点保持 block_id 唯一；重复分配同一块号应拒绝，避免逻辑冲突
这相当于在内存里“手绘一条FAT链”，不依赖物理磁盘布局，却复现了FAT的链式寻址语义。
free与合并：释放后如何维持链表有效性
释放某块不等于删除节点，而是重置其状态并修复链接：
- 找到目标节点，设 status = FREE；若其 next_block ≠ -1，检查该下一簇是否也 FREE —— 若是，可将两节点合并：删除后者，把前者 next_block 更新为后者的 next_block
- 同时向前检查：是否存在前驱节点指向当前块？若有，且前驱状态也为 FREE，则可进一步向前合并
- 合并后链表变短，但每个 FREE 节点仍保有 block_id 和 next_block，便于后续 alloc 快速识别连续空闲段
这种“懒合并”策略避免频繁重构，又防止碎片化导致小块堆积无法利用。
随机访问支持：怎样实现O(1)到O(log n)的块定位
纯链表遍历是 O(n)，但模拟 FAT 的关键优势在于可加一层索引加速：
- 维护一个哈希表或平衡树，key 是 block_id，value 是指向链表节点的指针
- alloc / free / get_next 操作先查哈希，命中则直接操作对应节点，平均 O(1)
- 若资源受限不加哈希，至少按 block_id 排序链表，使查找退化为 O(log n) 二分（需双向链表或支持跳表扩展）
这正体现了“模拟”的灵活性：底层用链表保动态性，上层可叠加结构提升性能，不像真实FAT被数组长度和硬件扇区强绑定。
