数据结构

数据结构是一种组织信息的方式，通常用于计算机内存中，使信息能够被系统地访问和操作。它规定了元素的表示方式、元素之间的关系，以及这种组织方式必须保持的性质。在计算机科学中，数据结构与算法相互配合：数据的表示方式决定了哪些操作能够高效完成，而算法则执行查找、插入、删除及其他变换。数据结构也可以将相关信息组织在一起，使概念更清晰，例如用一条记录保存某人的姓名和地址。(xlinux.nist.gov)

抽象与表示

抽象数据类型描述一组可能的值及其定义明确的操作，而不指定具体实现。具体的数据结构则提供实现这一规范所需的表示方式和操作过程。这一区分将一个集合“能做什么”与“如何实现”分离开来。例如，栈支持后进先出的访问方式，但其元素既可以存储在数组中，也可以存储在链表中。这两种实现都能满足相同的抽象约定，却具有不同的性能特点。(xlinux.nist.gov)

队列通常提供先进先出的访问方式，而优先队列则根据元素的优先级移除元素。列表提供按位置访问的功能；集合表示互不重复的元素；字典将键与值关联起来。编程语言的库通常通过接口表达这些抽象，并提供多种可相互替换的实现。例如，Java 的集合框架将集合接口与基于数组、链式结构、散列和树的实现区分开来。(opendatastructures.org)

顺序结构

数组将带有索引的元素存储在连续的位置中。在通常假设内存访问耗时为常数的模型下，可以通过索引在 $O(1)$ 时间内读取或替换一个元素。在基于数组、元素紧密排列的序列内部插入或删除元素，可能需要移动后续元素，因此，对于包含 $n$ 个元素的序列，最坏情况下的开销为 $O(n)$。(opendatastructures.org)

动态数组使用一个容量可变的底层数组。当容量耗尽时，实现会分配一个更大的数组，并复制已有元素。按几何比例扩容可使追加操作的均摊时间达到 $O(1)$，但一次触发复制的追加操作仍可能耗费 $O(n)$ 时间。因此，逻辑长度与已分配的容量是两个不同的量。(opendatastructures.org)

链表由多个节点组成，每个节点包含值以及指向相邻节点的引用。单向链表提供指向后继节点的引用；双向链表还提供指向前驱节点的引用。如果已经持有所需的节点引用，就可以通过更新链接在常数时间内完成插入或删除。按位置查找节点通常需要遍历，可能耗费 $O(n)$ 时间。链接也会占用额外的内存，而且各节点不必位于相邻的存储位置。(opendatastructures.org)

关联结构与层次结构

散列表通过散列函数将键映射到数组位置，从而实现按键存储。不同的键可能映射到同一位置，产生冲突。链地址法将发生冲突的条目存放在辅助集合中；开放寻址法则在表内寻找另一个位置。采用合适的散列方法并控制占用率时，查找的期望开销可以达到 $O(1)$，但性能取决于散列方案和冲突处理方式，并非无条件保证。(xlinux.nist.gov)

二叉搜索树按照排序规则组织键：一侧子树中的键排在当前节点的键之前，另一侧子树中的键则排在其后。查找、插入和删除的开销取决于树的高度。不平衡的树可能退化为一条链，使操作需要 $O(n)$ 时间；而红黑树等结构采用的平衡机制能够将树高维持在对数级别，支持 $O(\log n)$ 时间的操作。与普通散列表不同，有序搜索树可以直接支持按键的顺序遍历。(opendatastructures.org)

二叉堆是一种满足堆序性质的完全二叉树。在最小堆中，每个父节点的键都不大于其子节点的键，因此根节点保存着一个最小值。二叉堆通常用数组表示，父节点和子节点的位置可由索引计算得出。二叉堆支持在常数时间内查看最小值，并在对数时间内完成插入或删除，因此是优先队列的常见实现方式。堆序并不意味着所有元素都已完全排序。(xlinux.nist.gov)

图的表示

在图论中，图表示顶点和边，可以是有向的，也可以是无向的。邻接表存储每个顶点的邻居，对于包含 $V$ 个顶点和 $E$ 条边的图，需要 $O(V+E)$ 空间。邻接矩阵使用一个以顶点对为条目的矩阵，需要 $O(V^2)$ 空间。邻接矩阵可以在常数时间内判断一条边是否存在，而在基本的邻接表中，枚举邻居的耗时与所存储的邻居数量成正比。表示方式会影响图遍历及其他操作的开销。(opendatastructures.org)

复杂度与实际权衡

比较数据结构时会考察时间复杂度和空间复杂度，通常使用大O记号来表示。分析时必须明确某个界限针对的是最坏情况开销、期望开销还是均摊开销，并说明所依据的计算模型假设。均摊分析为一系列操作的总开销给出界限，不要求输入服从某种概率分布。动态数组的扩容说明，偶尔出现的高开销操作可以与常数级的均摊开销并存。(opendatastructures.org)

物理组织方式同样重要。数组提供紧凑的顺序存储，而链式结构会引入引用，并可能使分配的存储位置分散。因此，仅凭渐近界限无法确定实际运行时间或内存占用。(opendatastructures.org)

外部存储与版本保留

B树是一种平衡的多路搜索树。其较大的分支因子能够降低树高，并在信息存放于较慢的外部存储中时，减少所需的访问次数。因此，外存分析不仅考察内存中的计算，也考察数据块的传输。(xlinux.nist.gov)

可持久化数据结构在更新后仍保留先前的版本，使旧状态依然可以被查询。在这一技术含义下，“持久化”指的是保留版本，而不只是将信息保存到磁盘。(xlinux.nist.gov)