数据结构的存储方式

数据结构的四大存储方式：特性、适用场景与性能对比

数据结构的存储方式直接影响其操作效率（如增删查改），不同存储方式适用于不同的数据结构和业务场景。常见的存储方式包括顺序存储、链式存储、索引存储和散列存储，它们各有优劣，本文详细解析其原理、特性及适用场景。

顺序存储将数据元素存放在连续的物理存储单元中，逻辑上的相邻元素在物理位置上也相邻，通过元素的物理位置关系体现逻辑关系。
典型示例：数组（如 Java 的int[]、C++ 的std::array）。

存储结构：依赖一块连续的内存空间，需预先分配固定大小。
访问效率：通过下标直接访问元素（arr[i]），时间复杂度 O(1)（随机访问能力）。
增删效率：
- 插入 / 删除中间元素时，需移动后续所有元素（如数组中间插入元素），时间复杂度 O(n)。
- 尾部插入 / 删除效率高（无需移动元素），时间复杂度 O(1)。
空间利用率：无额外存储开销（不存储指针 / 索引），但可能因预分配过大导致空间浪费。

链式存储不要求物理空间连续，每个元素（节点）包含数据域和引用域（指针 / 地址），通过引用域指向相邻元素，从而体现逻辑关系。
典型示例：链表（单链表、双向链表、循环链表）。

存储结构：节点分散在内存中，通过指针链接形成逻辑序列，无需预分配连续空间。
访问效率：无随机访问能力，需从表头（或表尾）遍历至目标元素，时间复杂度 O(n)。
增删效率：
- 已知前驱 / 后继节点时，插入 / 删除仅需修改指针，时间复杂度 O(1)。
- 未知位置时，需先遍历定位，总时间复杂度 O(n)。
空间利用率：每个节点需额外存储指针（如双向链表需两个指针），空间开销略大，但可动态分配内存（按需扩展）。

索引存储在数据之外额外建立索引表，索引表中的每个条目（索引项）包含关键字和数据地址，通过索引快速定位数据位置，再访问实际数据。
典型示例：数据库索引（如 B + 树索引）、图书目录。

散列存储（哈希存储）通过哈希函数将数据的关键字直接映射为存储地址，实现 “关键字→地址” 的直接映射，无需遍历或索引查找。
典型示例：哈希表（如 Java 的HashMap、Python 的dict）。

存储方式	核心原理	访问效率	增删效率（中间元素）	空间开销	典型数据结构	适用场景
顺序存储	连续空间，物理相邻	O(1)	O(n)	低	数组、栈（顺序实现）	固定规模、查询频繁
链式存储	非连续空间，指针链接	O(n)	O (1)（已知位置）	中	链表、队列（链式实现）	动态规模、增删频繁
索引存储	索引表映射地址	O(logn)	O(logn)	高	数据库表、B + 树	大规模数据、查询密集
散列存储	哈希函数直接映射地址	O(1)	O (1)（无冲突）	中	哈希表、布隆过滤器	关键字查询、无顺序要求