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

只有几种基本类型的数据结构：数组,列表和树.可以通过使用不同类型的这两个结构来组合其它的(例如,哈希表可以用哈希值的数组和每个散列值的一个列表来实现冲突).

在这些结构中,阵列是静态的(即,随着对它们执行操作,它们的存储器占用不会随时间而变化),并且其它一切都是动态的(即,在一般情况下,存储器足迹改变).

两种结构之间的差异可以从上述得出：

>静态需要提前知道的最大尺寸,而动态可以适应
> Static不会重新分配内存,无论什么,所以你可以保证内存的要求

还有其他的差异,但是如果您的数据可能被排序,则只会发挥作用.我不能给出广泛的列表,因为有许多动态数据结构对不同的操作(“添加”,“删除”,“查找”)表现出不同的性能特征,因此它们不能被置于同一个屋檐下.

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

所以,总结一下：

>如果您需要最大内存使用率的保证,除了数组之外,您不能选择任何选项.
>如果您的数据大小有上限,请考虑使用数组.数组可以很好地适用于主要需要添加/删除操作(保持数组未排序)和主要需要查找操作(保持数组排序)但不是同时存在的那些问题的问题.
>如果您没有硬上限,或者如果您要求所有添加/删除/查找都是快速的,请使用适当的动态结构.

编辑：我没有提到图形,另一种类型的动态数据结构可以说是不能由更简单的部分组成(根据定义,一棵树只有一个链接进入“除了根”之外的任何节点,而图形可能有多个) .但是,由于您需要使用图形或者不使用图形(其他结构可能会表现出不同的性能,所以图形与其他结构实际上并不能与其他结构进行比较,因为它们都支持同一套操作).