ewo*_*wok 4 java performance list data-structures
我正在研究一种算法,该算法将一小组对象存储为一组较大对象的子列表.对象本质上是有序的,因此需要有序列表.
执行的最常见操作将按频率顺序执行:
从中间移除和插入将永远不会完成,因此无需考虑其效率.
我的问题是List的实现对Java中的这个用例最有效(即LinkedList,ArrayList,Vector等)？请通过解释不同数据结构的实现来捍卫您的答案,以便我做出明智的决定.
谢谢.
注意
不,这不是一个功课问题.不,我没有可以为我工作的军队研究助理.
根据您的第一个标准(任意访问),您应该使用ArrayList.ArrayLists(和一般的数组)在恒定时间内提供查找/检索.相比之下,在LinkedList中查找项目需要线性时间.
对于ArrayLists,最后插入或删除是免费的.它也可能与LinkedLists有关,但这将是一个特定于实现的优化(否则它是线性的).
对于ArrayLists,前面的插入或删除需要线性时间(一致地重用空间,这些可能会变得不变,具体取决于实现).列表前面的LinkedList操作是不变的.
最后两个用例在某种程度上相互平衡,但是最常见的情况肯定是基于阵列的存储.
至于基本的实现细节:ArrayLists基本上只是内存的连续部分.如果你知道开头的位置,你可以只做一个添加来找到任何元素的位置.前面的操作是昂贵的,因为可能必须移动元件以腾出空间.
LinkedLists在内存中是不相交的,由彼此链接的节点组成(引用第一个节点).要查找第n个节点,您必须从第一个节点开始并按照链接进行操作,直到到达所需节点.前面的操作只需要创建一个节点并更新你的开始指针.