当前位置: 首页 > 后端技术 > Java

使用ArrayList还是LinkedList?看完你就明白了!

时间:2023-04-01 19:16:48 Java

本文旨在为Java开发选择合适的顺序数据结构提供指导。ArrayList和LinkedList是Java集合框架中的两个类,用于存储对象引用列表。ArrayList和LinkedList都实现了List接口。首先我们来看一下它们最重要的父接口——List。1.List接口列表(list)是元素的有序集合,也称为序列。它提供了基于元素位置的操作,有助于快速访问、添加和删除列表中特定索引位置的元素。List接口将Collection和Iterable实现为父接口。它允许存储重复值和空值,并支持通过索引访问元素。2.用法下面是使用List接口声明ArrayList和LinkedList的代码片段。importjava.util.*;publicclassMyClass{//非同步或非线程安全的ListarrayList=newArrayList<>();//声明一个数组列表ListlinkedList=newLinkedList();//声明链表//保证线程安全ListtsArrayList=Collections.synchronizedList(newLinkedList<>());ListtsLinkedList=Collections.synchronizedList(newLinkedList<>());}Vector类似于ArrayList,但是它们支持自动同步,这也使得Vector线程安全,但同时会带来一些性能损耗.3.内部实现3.1LinkedList内部实现Linkedlist数据结构包含一组称为节点的有序数据元素。每个元素都包含对其后续元素(即下一个元素)的链接或引用。序列的最后一个元素(尾部)指向空元素。链表本身包含对链表第一个元素的引用,称为头元素。Java中的LinkedList是List接口的双向链表。在双向链表中,每个节点都指向其上一个和下一个节点。此外,它还实现了其他接口,例如Serializable、Cloneable和Deque(将Queue实现为父接口)。3.2ArrayList的内部实现ArrayList是一个可以调整大小的数组,实现了List接口。它里面是一个对象数组,可以扩展它以支持根据需要向集合中添加更多元素。可以通过构造函数ArrayList(intinitialCapacity)来指定ArrayList的初始容量,然后在需要的时候使用voidensureCapacity(intminCapacity)增加容量,以保证初始化时至少有最小容量参数指定的元素个数可以入住。它还提供了一个方法voidtrimToSize()来减小现有元素的大小。//调用构造函数ArrayList(initialCapacity)Listarr=newArrayList(10);默认情况下,ArrayList创建一个初始容量为10的列表,而LinkedList只构造一个没有任何初始容量设置的空列表。Linkedlist没有实现RandomAccess接口,而ArrayList实现了RandomAccess接口(不是Deque接口)。4.各种操作的时间和空间复杂度5.Tips考虑下面遍历LinkedList的示例代码。在这段代码中遍历会很慢,因为LinkedList不支持随机访问,所以每次遍历都会产生巨大的开销。LinkedListll=newLinkedList();...Objecto=null;for(inti=0;i