计算机基础数据结构概览

数组 (Array)

最常用的数据结构。

在内存中申请一块固定长度的连续空间，可通过下标直接访问。

array = malloc(n);

挑战: 内存需提前申请。对于长度可变的存储需求，频繁申请新内存会有较高开销。

链表 (LinkList)

以节点为存储单元，每个节点包含值与下一个节点的地址。

linkNode = malloc(2);
linkNode[1] = value;
linkNode[2] = &nextNode;

特点: 可根据需求动态开辟空间，但在访问单个节点时效率较低（需从头遍历）。

列表 (List)

现代编程语言综合了数组和链表的优点。一种可能的实现方案：

1. 设置子数组长度 $k$。
2. 使用链表存储子数组的头节点。
3. 访问公式：List[i] = nodes[i / k][i % k]（注：此处公式根据实际逻辑修正）。

队列 (Queue)

先进先出 (FIFO)。 应用：广度优先搜索 (BFS) 中记录待搜索节点。

栈 (Stack)

先进后出 (LIFO)。 应用：深度优先搜索 (DFS) 中辅助搜索记录。

哈希表 (Hash Table)

给定 Key，通过 Hash 函数计算地址：address = hash(key)。

• 冲突解决: 通过冲突解决函数获得偏移地址。
• 底层实现: 通常依赖数组和链表共同实现。

脚本语言中的 Dictionary

字典通常使用多个链表：一个存储哈希值，一个存储 Value 引用。

虽然空间代价略高，但换取了极快的访问速度。

---

[!NOTE] 高级数据结构通常都无法脱离数组和链表这两类基础结构，它们是更高层次逻辑实现的基础单元。