Java集合之一 —— List
本文对List的讲解是基于JDK1.8版本.
Java的List中的常用子类有ArrayList、LinkedList、Vector,其中Vector是线程安全的(基本被淘汰了),其他两个线程是不安全的,本文主要讲解ArrayList和LinkedList.
// 初始化ArrayList容器 : list
List<String> list = new ArrayList<String>();
// 添加元素到 list 中
list.add("邱");
list.add("锐");
list.add("斌");
// 拼接返回结果
StringBuffer result = new StringBuffer();
// 遍历容器中的元素
for (int i = 0; i < list.size() ; i++) {
// 打印 : 根据索引值获取相对应的元素
System.out.println("索引值为 "+i+" 存放的元素 : "+list.get(i));
// 拼接
result.append(list.get(i));
}
// 打印拼接的最终结果
System.out.println(result);
最终输出结果为 :
索引值为 0 存放的元素 : 邱
索引值为 1 存放的元素 : 锐
索引值为 2 存放的元素 : 斌
邱锐斌
上面执行过程 : 初始化ArrayList容器 --> 添加元素到 list 中 --> 遍历容器中的元素 --> 输出打印结果. 现在,我们开始学习ArrayList在这一过程的每一步操作都做了什么实现,学习一下ArrayList的底层原理.
传统的数组容器
// 初始化长度为2的数组 : arrs
// String[] arrs = {"邱","锐"};
String[] arrs = new String[2];
// 向数组 arrs 中添加元素
arrs[0] = "邱";
arrs[1] = "锐";
// 循环遍历数组 arrs 中的元素
for (int i = 0; i < arrs.length; i++) {
// 打印
System.out.println("索引值为 "+i+" 存放的元素 : "+arrs[i]);
}
// 添加第三个元素,报错,因为初始化的时候长度固定为2,已经满了,不能再装了
arrs[2] = "斌";
传统的数组容器初始化的时候,长度固定了,当数组容器的元素已经填满的情况下继续添加元素,则会报错,这个时候有人可能会说:刚开始初始化长度的时候我们可以给数组一个比较大的值不就行了吗,或者当数组容器满了的情况下调用Arrays.copyOf重新拷贝扩容一个新的数组等等方法,前者会浪费内存空间,比如你只存放10个元素,但是数组的长度是100,会浪费内存空间的;后者的话自己手动来处理扩容问题,比较麻烦,这个时候ArrayList就出现了,它可以动态的扩容数组的长度;ArrayList底层其实就是个数组,只是原来的静态数组变为动态数组.
ArrayList : 简单的自我介绍
ArrayList 的数据结构是基于 数组 实现,默认初始化长度为10,当添加第一个元素的时候才真正初始化,当ArrayList容器为满的状态下继续添加元素,则会扩容,所以是一个动态数组.
全局变量
// 默认初始化长度
private static final int DEFAULT_CAPACITY = 10;
// 有参构造器初始化数组实例:有参构造器初始化的时候用的实例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 无参构造器初始化数组实例:无参构造器初始化的时候用的实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 底层数组实例 : 存储元素的数组实例
transient Object[] elementData;
// 容器中元素的个数
private int size;
// 数组的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
构造器(3个)
1、有参构造器初始化
initialCapacity参数为初始化数组的长度,
传入的initialCapacity大于0的话直接创建一个Object数组对象
传入的initialCapacity为0的话使用EMPTY_ELEMENTDATA实例
传入的initialCapacity小于0的话则抛出异常报错
最终都是指向 elementData 对象
public 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);
}
}
2、无参构造器初始化
使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA实例
指向 elementData 对象
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
3、有参构造器初始化
c参数为容器对(使用 extends来限制容器中的元素只能用一种对象)
public ArrayList(Collection<? extends E> c) {
// 把c转化为数组后指向elementData,这里的c容器的元素已经装进elementData容器了
elementData = c.toArray();
// 该条件成立的话,说明c容器存在元素
if ((size = elementData.length) != 0) {
// 判断一下elementData如果不是Object类型,则需要重新拷贝为Object类型
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 该条件成立的话,说明c容器不存在元素
// 使用EMPTY_ELEMENTDATA实例
this.elementData = EMPTY_ELEMENTDATA;
}
}
添加元素 --- add(E e)
现在我们选择第2种无参构造器初始化容器的方式,且当我们向容器add元素的时候,ArrayList做了什么操作?
1、添加元素,调用add方法
public boolean add(E e) {
// 该方法是添加元素前进行的数组容器初始化、扩容操作
ensureCapacityInternal(size + 1);
// 把元素添加到数组容器中
elementData[size++] = e;
return true;
}
2、数组容器初始化、扩容操作
minCapacity 参数表示当前数组容器中添加元素后的总个数
private void ensureCapacityInternal(int minCapacity) {
// elementData 对象是否等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA实例
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// minCapacity 和 DEFAULT_CAPACITY(默认10) 取最大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 该方法来检验当前数组容器是否需要扩容
ensureExplicitCapacity(minCapacity);
}
3、检验当前数组容器是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果当前数组容器中添加元素后的总个数 大于 当前数组的长度 则扩容
if (minCapacity - elementData.length > 0)
// 该方法的作用是数组容器扩容
grow(minCapacity);
}
4、数组容器扩容
private void grow(int minCapacity) {
// 获取原数组的长度 : oldCapacity
int oldCapacity = elementData.length;
// oldCapacity有移1位,减少一半,再加上原来的长度;
// 也就是说数组的长度扩大到原来是1.5倍
// 然后赋值给 newCapacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 当newCapacity 小于 minCapacity 的时候 则重新赋值 newCapacity
为什么这里有这个判断条件 : 跟addAll方法有关,看看下面的场景;
有这么一个场景 :
假如现在已经初始化了ArrayList,且数组容器的长度是默认值10,
此时我调用addAll方法传入一个装有元素为20的容器
那么此时的minCapacity为30,数组容器的长度只有10,数组容器的长度不够存,需要grow
第一次计算 newCapacity = 15;
因为 newCapacity 小于 minCapacity ,
也就是说 新的容器长度为15 还是不够装 最大的数量30
所以直接把minCapacity赋值给newCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// newCapacity 大于 MAX_ARRAY_SIZE(数组最大的容量)
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 该方法为返回数组的最大容量
newCapacity = hugeCapacity(minCapacity);
// 经过上面的流程,已经确认了newCapacity值
// 调用 Arrays.copyOf方法进行拷贝扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
5、返回数组的最大容量
当 minCapacity 大于 MAX_ARRAY_SIZE 取 Integer.MAX_VALUE
反之 取 MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add方法的执行流程
添加元素,调用add方法 --> 数组容器是否需要初始化、扩容操作(ensureCapacityInternal方法) --> 判断数组容器是否需要扩容(ensureExplicitCapacity方法),如果需要则执行扩容机制 --> 扩容机制(grow方法) --> 扩容完成,把元素添加到数组容器中.
- 添加元素,调用add方法
- 执行ensureCapacityInternal方法,取数组的长度 和 添加完元素后的长度 的最大值
- 执行ensureExplicitCapacity方法,如果 添加完元素后的长度 大于 数组的长度,则需要扩容
- 如果需要扩容,执行grow方法,数组的长度是扩大到原来是1.5倍,数组的最大容量不能超过MAX_ARRAY_SIZE
- 经过上面的流程,已经确认了要扩容的数组长度,然后调用 Arrays.copyOf方法进行拷贝扩容
- 扩容完成,把元素添加到数组容器中(elementData[size++] = e)
获取元素 --- get(int index)
根据索引值获取元素
public E get(int index) {
// 检查index是否越界
rangeCheck(index);
// 获取元素
return elementData(index);
}
// 根据索引值获取元素
E elementData(int index) {
return (E) elementData[index];
}
ArrayList提供了很多操作方法,这里只简单的介绍了添加、获取方法和数据存储结构,只要理解了基本的数据结构思路,其他方法慢慢的就可以看懂了.
小结及疑问
1.ArrayList的扩容机制是怎么样的 : 如果需要扩容,则执行grow方法;扩容机制是数组的长度是扩大到原来是1.5倍,数组的最大容量不能超过MAX_ARRAY_SIZE.
2.ArrayList的扩容机制消耗性能吗 : 对于grow方法,会调用Arrays.copyOf方法进行拷贝到新的数组容器,所以会消耗性能的.
3.ArrayList适用于读多写少的场景 : ArrayList对元素的增加操作,会对数组容器进行扩容,对元素的删除操作,会对数组容器中的元素进行挪动,这两操作都会影响性能;在查询的时候,只需要根据索引值获取到元素,所以查询的效率是很高的.
ArrayList适用于读多写少的场景,因为增删操作都会影响性能,那么有没有哪个容器是适用于增删操作场景的呢,答案就是 LinkedList.
LinkedList : 简单的自我介绍
LinkedList 的数据结构是基于双向链表组成,Node节点是LinkedList的基本存储单位,Node节点维护着三个属性 : 值(item)、指向下一个节点(next)、指向上一个节点(prev)的数据结构.
LinkedList维护的三个核心属性 : 头节点(first)、尾节点(last)、size,其中头节点(first)指向双向链表的头节点,尾节点(last)指向双向链表的尾节点.
既然LindedList是用节点指针(next\prev)把数据相关联形成一条双向链表,那么在对元素的随机增加或随机删除的时候,只需要移动节点指针就行了,无需像数组那样去挪动位置,消耗性能.
// Node<E>节点
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
LinkedList存储结构图
全局变量
// 链表中存放的元素个数
transient int size = 0;
// 指向头节点
transient Node<E> first;
// 指向尾节点
transient Node<E> last;
构造器(2个)
// 无参构造器
public LinkedList() {
}
// 有参构造器
// c容器中的元素添加到当前LinkedList容器中
public LinkedList(Collection<? extends E> c) {
// 调用上面的无参构造器
this();
// 把c容器的所有元素添加到当前的LinkedList容器中
addAll(c);
}
添加元素
现在我们选择第1种无参构造器初始化容器的方式,每当我们向容器add,LinkedList做了什么操作？
// 调用add方法添加元素
public boolean add(E e) {
linkLast(e);
return true;
}
// 向链表的尾部插入添加的元素
public void linkLast(E e) {
1、获取尾节点
final Node<E> l = last;
2、创建一个新节点 并且新节点与链表中最后的节点连接上(prev)
final Node<E> newNode = new Node<>(l, e, null);
3、尾节点(last)指向新的节点
last = newNode;
4、双向链表中不存在元素
也就是说添加的是第一个元素的时候
头节点和尾节点都是指向同一个节点
if (l == null)
first = newNode;
else
5、双向链表中存在元素
新节点与链表中最后的节点连接上(next)
l.next = newNode;
size++;
modCount++;
}
很简单,直接向双向链表的尾节点插入添加的元素,即在原先的双向链表的尾节点连接上即可,看看下面流程图:
分析一下add方法添加元素的过程:
- 获取当前双向链表的最后一个节点.
- 创建新节点对象,并跟双向链表中的最后一个节点连接上(prev).
- LinkedList的尾节点(last)指向新节点
- 如果当前双向链表中不存在元素,也就是第一个元素添加进来,则头节点(first)也指向新节点
- 如果当前双向链表中存在元素,新节点与双链表中最后的节点连接上(next)
获取元素
// 根据index获取元素
public E get(int index) {
// 检查index是否越界
checkElementIndex(index);
// 获取元素
return node(index).item;
}
// 获取元素
Node<E> node(int index) {
// 中间对半查找 : size右移1位,也就是说减少一半
// 当index小于size长度的一半的时候
// 说明需要查找的元素在中间的左边,从开头查找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 当index小大于size长度的一半的时候
// 需要查找的元素在中间的右边,从尾部查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
删除元素
// 根据index删除元素
public E remove(int index) {
// 校检index是否越界
checkElementIndex(index);
// 执行删除元素
return unlink(node(index));
}
// node(index)方法获取到要删除元素的Node对象
// 删除元素
E unlink(Node<E> x) {
// 获取要删除的元素的值(item)
final E element = x.item;
// 获取删除Node对象的上一个Node对象和下一个Node对象
final Node<E> next = x.next;
final Node<E> prev = x.prev;
这里的 if else 是来帮助删除的Node的上一个Node和下一个Node的next连接
1、 上一个对象为null 说明删除的节点是第一个节点
if (prev == null) {
2、 first指向下一个节点
first = next;
} else {
3、 删除的节点的上一个节点存在节点
上一个节点与下一个节点的next连接上
prev.next = next;
4、 与上一个节点断开
x.prev = null;
}
这里的 if else 是来帮助删除的Node的上一个Node和下一个Node的prev连接
5、 下一个节点为null 说明删除的节点是最后一个节点
if (next == null) {
6、 尾节点指向上一个节点
last = prev;
} else {
7、 删除的节点的下一个节点存在节点
下一个节点与上一个节点的prev连接上
next.prev = prev;
8、 与下一个节点断开
x.next = null;
}
9、 设置值为null,清理元素
x.item = null;
size--;
modCount++;
// 返回删除Node对象的item
return element;
}
看看下面流程图:
分析一下图中删除操作的过程:
- 删除的节点存在上一个节点,把删除节点的上一个节点和下一个节点的next连接起来,连接完后其实已经断开了删除节点与上一个节点的next(虚线),如图的3步骤
- 彻底断开删除节点的上一个节点(红色虚线),如图的4步骤
- 把删除节点的下一个节点和上一个节点的prev连接起来,连接完后其实已经断开了删除节点与下一个节点的prev(虚线),如图的7步骤
- 彻底断开删除节点的下一个节点(红色虚线),如图的8步骤
小结及疑问
以下说明基于ArrayList 初始化容量足够,排除动态扩容数组容量的情况下进行的测试,如果有动态扩容的情况,ArrayList 的效率也会降低.
- ArrayList 和 LinkedList 新增元素操作测试
- 从集合头部位置新增元素
- 从集合中间位置新增元素
- 从集合尾部位置新增元素
- 测试对比的花费时间
- ArrayList>LinkedList
- ArrayList<LinkedList
- ArrayList<LinkedList
- 分析
- 由于 ArrayList 是数组实现的,而数组是一块连续的内存空间,在添加元素到数组头部的时候,需要对头部以后的数据进行复制重排,所以效率很低.而 LinkedList 是基于链表实现,在添加元素的时候,首先会通过循环查找到添加元素的位置,如果要添加的位置处于 List 的前半段,就从前往后找;若其位置处于后半段,就从后往前找.因此 LinkedList 添加元素到头部是非常高效的
- ArrayList 在添加元素到数组中间时,同样有部分数据需要复制重排,效率也不是很高;LinkedList 将元素添加到中间位置,是添加元素最低效率的,因为靠近中间位置,在添加元素之前的循环查找是遍历元素最多的操作
- 在添加元素到尾部的操作中,我们发现,在没有扩容的情况下,ArrayList 的效率要高于 LinkedList.这是因为 ArrayList 在添加元素到尾部的时候,不需要复制重排数据,效率非常高.而 LinkedList 虽然也不用循环查找元素,但 LinkedList 中多了 new 对象以及变换指针指向对象的过程，所以效率要低于 ArrayList.
- ArrayList 和 LinkedList 删除元素操作测试
- 从集合头部位置删除元素
- 从集合中间位置删除元素
- 从集合尾部位置删除元素
- 测试对比的花费时间
- ArrayList>LinkedList
- ArrayList<LinkedList
- ArrayList<LinkedList
- 分析 : 同新增元素是一样的原理
结束语
本文只是简单的介绍了ArrayList和LinkedList的添加方法、获取方法、删除方法和数据存储结构,其中还实现了其他很多方法,只要理解了基本的数据结构思路,其他方法慢慢的就可以看懂了.
希望看完这篇文章的你有所收获,文章中有错误的地方麻烦您指出来,谢谢!