本文为Java开发人员选择适当的顺序数据结构提供了指导。
ArrayList和LinkedList 两个类的Java集合框架用于存储对象引用的名单。ArrayList并且 LinkedList 都实现了List接口。让我们首先尝试了解它们最重要的父接口List(哪个)。
ArrayList
LinkedList
列表界面 列表只是元素的有序集合(也称为序列)。它添加了面向位置的操作,这些操作对于快速访问,添加和删除列表中特定索引位置的元素很有用。列表接口具有Collection和Iterable作为超级接口。它可以允许存储重复项和空值。它提供对其元素的索引访问。
Collection
Iterable
Usage 下面是声明ArrayList 和LinkedList使用List接口的代码段。
import java.util.*; public class MyClass { // Unsynchronized or Not thread safe List<Object> arrayList = new ArrayList<>(); // declares an array list List<Object> linkedList = new LinkedList(); // declares a linked list // ensures thread safety List<Object> tsArrayList = Collections.synchronizedList(new LinkedList<>()); List<Object> tsLinkedList = Collections.synchronizedList(new LinkedList<>()); }
Vector与ArrayList 它们相似,不同之处在于它们具有自动同步功能,这使它们具有线程安全性,但会导致性能开销。
Vector
链表 该LinkedList数据结构包含一组有序的数据元素(如知道节点),使得每个元素包含到其后继(链接或参考下一个元素)。序列的最后一个元素(或tail)指向空元素。链接列表本身包含对列表的第一个元素(称为head元素)的引用。Java中的LinkedList是List接口的双链列表实现。在双向链接列表中,每个节点都指向其上一个和下一个节点。它实现的其他接口是Serializable,Cloneable和Deque(将超级接口作为Queue))。
数组列表
ArrayList是List接口的可调整大小的数组实现。它在内部实现为对象数组,可以根据需要增加大小以支持集合中更多的元素。可以ArrayList 通过构造函数指定a的初始容量,ArrayList(int initialCapacity) 然后void ensureCapacity(int minCapacity)在需要时使用来增加容量 ,以确保它可以容纳至少由minimum Capacity参数指定的元素数量。
ArrayList(int initialCapacity)
void ensureCapacity(int minCapacity)
它还包括一种基于现有元素减小大小的方法。 void trimToSize()
void trimToSize()
// calling constructure ArrayList<type>(initialCapacity) List arr = new ArrayList<Integer>(10);
默认情况下,an创建一个初始容量为10的列表,而LinkedList仅构建一个没有任何初始容量的空列表。 LinkedList 不实现RandomAccess接口,而实现接口(而不是Deque接口)。
RandomAccess
各种行动的时空复杂性
Tips 考虑下面的代码示例遍历A。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(); … }
结论 AnArrayList 更快更好,因为它支持对其元素的随机访问。遍历链表或在中间插入项目非常昂贵,因为您必须遍历每个项目,并且很可能会发生缓存未命中的情况。如果您需要在单次迭代中对列表的多个项目执行处理,则迭代的开销LinkedList要比ArrayList涉及多次复制数组元素的开销要少。
要分享您对这个主题的经验和更多见解,请在下面的评论部分中留下您的想法。
原文链接:http://codingdict.com