前言
数据结构在计算机中的存储方式(线性表的物理结构)主要分为以下两种:
- 顺序存储结构:数据存储在连续的存储单元中,如数组
- 优点
- 存储密度大(=1),存储空间利用率高,不需要为元素之间的逻辑关系而增加额外存储空间
- 随机存取表中元素
- 缺点
- 插入和删除操作需要移动元素,效率低
- 当线性表变化较大的时候,难以确定存储空间的容量
- 优点
- 链式存储结构:数据存放在任意的存储单元中,如链表
- 优点:
- 逻辑相邻的节点物理上不必相邻,插入、删除灵活,只需改变节点中的指针指向
- 缺点:
- 存储密度小(<1),存储空间利用率低,需为元素之间的逻辑关而增加额外存储空间
- 查找节点时需遍历元素节点,效率比顺序存储慢
- 优点:
ArrayList
是基于数组结构(顺序存储)的列表,LinkedList
是基于双向链表(链表存储)的列表,在介绍了以上两种存储结构后,相信即使不了解LinkedList
和ArrayList
的源码也知道这两个列表的核心区别了,但作为开发者,一定的源码了解还是需要的。
ArrayList源码分析
核心结构(类图分析)
List
:声明是一个有序的集合,可以控制元素位置并索引访问。RandomAccess
:声明支持快速随机访问的标记接口,常用于列表类实现。该接口的主要目的是允许通用算法更改其行为,即必要时选择更好的算法进行性能上的提高,实现了该接口的列表使用for遍历比迭代器Iterator
遍历效率高。Serializable
:启用类的可序列化特性。Cloneable
:声明类是可克隆的,且调用clone()
方法时不会抛出CloneNotSupportedException
AbstractList
:提供了List
接口的基本实现,并尽可能的减少List
接口”随机访问”数据存储支持的工作
属性解析
DEFAULT_CAPACITY
:默认容量10,用于构造函数初始化与容量运算。EMPTY_ELEMENTDATA
:共享的空数组,调用ArrayList
有参构造函数参数容量值为0(即一般考虑不再进行容量扩展)时赋给elementData
。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
:共享的空数组,与EMPTY_ELEMENTDATA
区别在于该数组是用来容量运算的,调用ArrayList
无参构造函数时会把该对象赋给elementData
,添加元素时再重新计算扩容,所以一般建议使用有参构造函数赋予原始容量。
1
2
3public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
elementData
:存储ArrayList的元素的数组缓冲区。size
:ArrayList
包含的元素数量,elementData
数组的元素数量。MAX_ARRAY_SIZE
:分配的最大数组大小,值为Integer.MAX-8
方法解析
add(E)添加元素
1 | /** |
以下重新整理一下新增的的步骤:
- add()数组末尾添加元素
- ensureCapacityInternal()确保内部的容量能满足所需最小容量minCapacity
- calculateCapacity()根据数组所需的最小容量minCapacity进行容量计算
- ensureExplicitCapacity()根据数组所需的最小容量minCapacity确保精确的容量
- ensureExplicitCapacity()根据数组所需的最小容量minCapacity判断是否扩容,若需要则进行步骤6
- grow()重新建一个至少可以容纳最小容量minCapacity的数组并进行数组元素拷贝,消耗大,所以建议一般使用有参构建函数创建列表时设置好容量
由上述流程可以看出,ArrayList
的add(E e)
方法在容量足以确保的情况下效率是很高的,直接将新元素赋予数组元素的末尾下标+1即可,复杂度仅为O(1)。
add(int, E)增元素
1 | public void add(int index, E element) { |
该方法的主要核心在System.arraycopy()
方法,该方法把elementData数组中的index位置起的size-index个元素(即index下标后的元素)复制到下标index+1,然后再把新的元素element赋到index下标位置。由于需要进行元素的位置逐个后移,所以性能耗费大,时间复杂度为O(n),n为指定位置后的元素数目。
如在非末尾位置插入元素的操作较多,选择LinkedList
效果会比ArrayList
更好。
addAll(Collection<? extends E>)添加元素
1 | public boolean addAll(Collection<? extends E> c) { |
由上源码可以看到当添加集合元素时,也是需要进行数组拷贝的,不过是直接拷贝到列表数组末尾,时间复杂度由集合元素数目而定,即为O(n)。
remove(Object)删元素
1 | public boolean remove(Object o) { |
虽然删除元素的主要方面命名为fastRemove()
,但从其代码依然可以看出这方法并不fast,指定位置删除元素后还要进行元素前移,性能耗费与指定位置添加差别不大,时间复杂度为O(n),n为指定位置后的元素数目。
如删除元素的操作较多,选择LinkedList
效果会比ArrayList
更好。
set(int, E)改元素
1 | public E get(int index) { |
替换指定下标数组元素,复杂度为O(1),效率高。
get(int)查元素
1 | public E get(int index) { |
根据下标获取数组元素,复杂度为O(1),效率高。
总结
ArrayList有以下特点:
- 添加元素性能因参数有所区别,但都需注意数组容量不足时ArrayList会进行扩容产生性能消耗
- add(E)在数组末尾添加元素,复杂度O(1)
- add(int, E)在数组指定位置添加元素,复杂度O(n),n为下标后的元素数目
- addAll(Collection)在数组末尾添加集合元素,复杂度O(n),n为集合中的元素数目
- 删除元素慢,remove()删除元素,后面元素需逐个移动,复杂度O(n),n为下标后的元素数目
- 更改效率高,set(index, E)直接根据下标替换数组元素,复杂度O(1)
- 查询效率高,get(index)直接根据下标获取数组元素,复杂度O(1)
LinkedList
源码解析
核心结构(类图分析)
LinkedList
是基于双向链表数据结构的列表,链表中的每个节点对应内部类Node
。
LinkedList
实现了List
和Deque
(双向队列)接口,即该类包含了列表与双向队列的操作方法,其类图如下:
AbstractSequentialList
:提供List
接口的基本实现,以最小化实现List
接口类顺序访问数据存储所需要提供的支持(实现)。
从类的继承与接口实现角度看,LinkedList
与ArrayList
的区别在于LinkedList
继承了AbstractSequentialList
列表类与实现了Deque
双向队列接口,少实现了一个快速访问接口RandomAccess
,因而相比于ArrayList
访问效率会有所不及,但多了双向队列的特性(从这个角度看挺有意思的)。
LinkedList
常用源码解析
由于LinkedList
是链表结构列表,所以访问该列表中的元素只能通过第一个节点或最后一个节点遍历获取,因此查询的效率比使用数组根据下标获取元素的ArrayList
慢。
属性解析
size
:列表元素数目first
:第一个节点last
:最后一个节点
方法解析
add(E)添加元素
1 | public boolean add(E e) { |
由源码看出,LinkedList
添加元素的流程如下:
- 将当前列表的最后一个节点引用赋予临时变量l
- 创建一个新的节点存放新元素e,并把最后一个节点的引用l赋予新节点e
- 将最后一个节点的last指向新节点newNode
- 判断列表之前的最后一个节点是否为空(即列表是否为空),空则将第一个节点first指向新节点newNode,非空则将之前最后一个节点的下一节点指向新节点
LinkedList
的add(E)与addLast(E)的调用与效果是一样的,都是新建一个Node
节点并更改最后一个节点的指向,消耗也不大,时间复杂度为O(1)。
add(int,E)添加元素
1 | public void add(int index, E element) { |
重新梳理一下LinkedList
指定位置添加元素流程:
- 校验位置索引是否超出列表范围
- 若index < size / 2. 则从第一个节点开始遍历,否则从最后一个节点开始遍历
- 获取链表中指定索引index的节点,为新元素创建节点并插入到指定节点之前
3-1. 若index < size / 2. 则从第一个节点开始遍历,否则从最后一个节点开始遍历,并返回指定索引节点
3-2. 为新元素创建节点并插入到指定节点之前
LinkedList
虽然要遍历才能获取到指定位置节点,但插入元素时只需新建一个节点并更改相应的引用而已,并没有更多的更改操作,相比ArrayList
的列表元素后移性能自然要好上不少,所以当对列表位置添加元素操作较多时选择LinkedList
比ArrayList
更好。
remove(Object)删除元素
1 | public boolean remove(Object o) { |
删除节点流程:
- 遍历获取目标元素节点
- 更改目标节点的上一节点与下一节点引用,更改元素数目
删除节点与添加节点的操作区别不大,都是遍历更改节点的链接,效率比ArrayList
的删除操作效率高。
get(int)获取节点
1 | public E get(int index) { |
由于LinkedList
是基于双向链表的数据结构,所以查询时也是按照双向链表的查询方式,需要从头部或尾部开始遍历查找,故查询的性能比基于数组结构的ArrayList
要差。
总结
LinkedList有以下特点:
- 增删元素快,遍历到指定节点后只需更改”指针”指向
- 查询效率慢,每次查询都需遍历链表
- 相比
ArrayList
需更多的存储空间来存储指向