我使用了很多列表和数组,但我还没有遇到一个场景,数组列表不能像链表一样容易使用,如果不是更容易的话。我希望有人能给我一些例子,说明什么时候链表明显更好。
当前回答
使用链表对数组和多项式操作进行基数排序。
其他回答
数组具有O(1)随机访问,但是向数组中添加或删除内容的代价非常高。
链表在任何地方添加或删除项目和迭代都非常便宜,但随机访问是O(n)。
这些是最常用的Collection实现。
数组列表:
插入/删除在结尾一般O(1)最坏情况O(n) 中间插入/删除O(n) 检索任意位置O(1)
LinkedList:
在任何位置O(1)插入/删除(注意你是否引用了元素) 中间检索O(n) 检索第一个或最后一个元素O(1)
向量:不要用。它是一个类似于ArrayList的旧实现,但所有方法都是同步的。对于多线程环境中的共享列表,这不是正确的方法。
HashMap
在O(1)中按键插入/删除/检索
TreeSet 插入/删除/包含O(log N)
HashSet 在O(1)中插入/删除/包含/大小
在现实中,内存局部性对实际处理的性能有很大的影响。
与随机访问相比,磁盘流在“大数据”处理中的使用越来越多,这表明围绕它构建应用程序可以在更大范围内显著提高性能。
如果存在按顺序访问数组的方法,则这是迄今为止性能最好的方法。如果性能很重要,那么至少应该考虑将此作为设计目标。
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
数组列表适用于写一次读多次或追加程序,但不适用于从前面或中间进行添加/删除。
使用链表对数组和多项式操作进行基数排序。
推荐文章
- 在JavaScript中根据键值查找和删除数组中的对象
- Python中方括号括起来的列表和圆括号括起来的列表有什么区别?
- 如何确定一个数组是否包含另一个数组的所有元素
- 给定一个数字数组,返回所有其他数字的乘积的数组(不除法)
- 多维数组如何在内存中格式化?
- TypeScript枚举对象数组
- 获取数组值的键名
- 检查ArrayList中是否存在值
- 如何规范化一个NumPy数组到一定的范围内?
- 如何计数列表中唯一值的出现
- 如何修剪空白的数组值在php
- 检查字符串是否包含字符串列表中的元素
- 如何有效地比较两个无序列表(不是集合)?
- 如何有效地从数组列表或字符串数组中删除所有空元素?
- 比较JUnit断言中的数组,简洁的内置方式?