Blog of CIU

线性结构

6 min read

数组（Arrays）

数组把元素放在连续内存里，用下标可在 时间内随机访问任意位置；在末尾增删通常也很快，但在中间插入或删除需要挪动后面的元素，一般是 。固定长度的数组容量写死；动态数组在元素变多时自动扩容（常见做法是容量翻倍），是多数语言里 vector、列表等容器的底层思路。

链表（Linked Lists）

链表由一个个节点串成，每个节点存数据和指向下一个节点的指针；元素在内存里不必连续。已知位置时，在头尾或中间插入、删除往往只需改指针，是 ；但按序号访问要从头往后走，是 。单向链表只指向前驱；双向链表多一个指向前节点的指针，便于从尾部往前删改，代价是每个节点多占一点空间。

堆栈（Stack）

堆栈是一种 后进先出（LIFO） 的线性结构：只在同一端压入（push）和弹出（pop），查看栈顶也是 。用数组或链表都能实现，数组版更简单。常见于函数调用栈、括号匹配、DFS、撤销操作等「先处理最近压入的」场景。

可以不实现，因为使用数组来实现是微不足道的事。

队列（Queue）

队列是一种 先进先出（FIFO） 的线性结构：从一端入队（enqueue）、另一端出队（dequeue），两端操作都是 。与堆栈相对，适合 BFS、任务调度、消息缓冲等「先来的先处理」场景。用数组实现时常配合循环队列，避免频繁搬移元素；用链表实现则头尾各维护指针即可。

哈希表（Hash table）

哈希表用哈希函数把键映射到桶下标，在理想情况下插入、查找、删除的平均时间都是 。不同键可能落到同一位置（冲突），常见处理方式是链式法（每个桶挂链表）或开放寻址（在表里探测下一个空位）。语言里的 dict / map、缓存、计数表等都依赖这一结构；负载因子过高时要扩容并 rehash。

分布式哈希表

Graph View

Backlinks