java - 静态和动态数据结构之间的差异

Question

静态和动态数据结构之间的主要区别、优点和缺点是什么？

最常见的数据结构属于哪些类别？

我怎么知道在什么情况下使用它们？

Answer 1

从过度简化开始:

数据结构只有几种基本类型:数组、列表和树。其他一切都可以通过使用这两种结构的不同类型来组合(例如，哈希表可以用哈希值的数组和每个哈希值的一个列表来实现，以处理冲突)。

在这些结构中，数组是静态的(即，它们的内存占用不会随着对其执行操作而随时间变化)，其他一切都是动态的(即，在一般情况下，内存占用会发生变化)。

这两种结构的区别可以从上面推导出来:

• 静态需要预先知道最大尺寸，而动态可以动态调整
• 静态无论如何都不会重新分配内存，因此您可以保证内存需求

还有其他差异，但只有在您的数据可能已排序时才会发挥作用。我无法给出一个详尽的列表，因为有许多动态数据结构对不同的操作(“添加”、“删除”、“查找”)表现出不同的性能特征，因此不能将它们全部放在同一屋檐下。

一个非常明显的区别是，排序数组需要在内存中移动(可能很多)内容以进行除“查找”之外的任何操作，而动态结构通常执行较少的工作。

所以，回顾一下:

1. 如果您需要保证最大内存使用量，您别无选择，只能使用数组。
2. 如果您对数据大小有硬性上限，请考虑使用数组。数组可以很好地解决主要需要添加/删除操作(保持数组未排序)和主要需要查找操作(保持数组排序)的问题，但不能同时解决这两个问题。
3. 如果您没有硬性上限，或者如果您需要所有添加/删除/查找操作都很快，请使用一种适当的动态结构。

编辑: 我没有提到图形，这是另一种动态数据结构，可以说它不能由更简单的部分组成(根据定义，一棵树只有一个链接“进入”任何节点，除了根，而图可能有多个)。然而，在“用什么更好”的场景下，图并不能真正与其他结构进行比较，因为你要么需要使用图，要么不需要(其他结构可能表现出不同的性能，但最终它们都支持同一组操作)。