响应式网站建设福州,中国服装设计公司排名,东营长安网站建设,定制网站开发接私活作者#xff1a;Tarun Telang 来源#xff1a;https://dzone.com/articles/arraylist-or-linkedlist本文为Java开发人员选择适当的顺序数据结构提供指导。ArrayList 和 LinkedList 是 Java 集合框架中用来存储对象引用列表的两个类。ArrayList 和 LinkedList 都实现 List 接口…作者Tarun Telang 来源https://dzone.com/articles/arraylist-or-linkedlist本文为Java开发人员选择适当的顺序数据结构提供指导。ArrayList 和 LinkedList 是 Java 集合框架中用来存储对象引用列表的两个类。ArrayList 和 LinkedList 都实现 List 接口。首先让我们了解一下它们最重要的父接口——List。# 1、List 接口列表(list)是元素的有序集合也称为序列。它提供了基于元素位置的操作有助于快速访问、添加和删除列表中特定索引位置的元素。List 接口实现了 Collection 和 Iterable 作为父接口。它允许存储重复值和空值支持通过索引访问元素。# 2、具体用法下面是使用 List 接口声明 ArrayList 和 LinkedList 的代码片段。Vector 与 ArrayList 类似只是 Vector 支持自动同步这也使得 Vector 线程安全但同时会带来一些性能损耗。# 3、内部实现LinkedList 内部实现Linkedlist 数据结构包含一组有序的数据元素称为节点。每个元素都包含对其后续元素即下一个元素的链接或引用。 序列的最后一个元素(尾部)指向空元素。链表本身包含对链表第一个元素的引用该元素称为 head 元素。Java 中的 LinkedList 是 List 接口的双向链表。在双向链表中每个节点都指向它的上一个节点和下一个节点。此外它还实现了其他接口比如 Serializable、 Cloneable 和 Deque(实现 Queue 作为父接口)。ArrayList 内部实现ArrayList 是可调整大小的数组实现了 List 接口。 它的内部是一个对象数组可以根据需要扩容支持在集合中加入更多元素。可以通过构造函数 ArrayList(int initialCapacity)指定 ArrayList 的初始容量然后在必要时使用 void ensureCapacity(int minCapacity) 增加容量确保至少可以容纳初始化时最小容量参数指定数量的元素。它还提供一个方法 void trimToSize()可以减少现有元素的大小。// 调用构造函数 ArrayList(initialCapacity)List arr new ArrayList(10);默认情况下ArrayList 创建初始容量为10的列表而 LinkedList 只构造一个没有设置任何初始容量的空列表。 Linkedlist 不实现 RandomAccess 接口而 ArrayList 实现了 RandomAccess 接口(而非 Deque 接口)。# 4、各种操作的时空复杂性# 5、提示考虑下面遍历 LinkedList 的示例代码。在这段代码中遍历会非常慢因为 LinkedList 不支持随机访问因此每次遍历都会带来巨大的开销。LinkedList ll new LinkedList();……Object o null;for (int i 0; i list.size(); i){ o list.get(i); …}一个更好的方法可提高性能像下面这段代码。LinkedList ll new LinkedList();……Object o null;ListIterator li list.listIterator(0);while (li.hasNext()){ o ll.next(); …}# 6、总结相比较而言 ArrayList 更快而且更好因为它支持对其元素的随机访问。 遍历链表或在中间插入新元素开销很大因为必须遍历每个元素而且很可能遇到缓存失败。 如果需要在一次迭代中对列表中的多个项目执行处理那么 LinkedList 的开销比 ArrayList 使用时多次复制数组元素的开销要小。欢迎分享你对这个话题的经验与见解请在文章的评论区中提出你的想法。
