上一篇文章我们介绍了Hashmap,今天来看一看List接口下最主要的两个类 : ArrayList和LinkedList
思维导图
ArrayList
链表与数组
从名字就可以看出来,ArrayList使用的是数组,LinkedList使用的是链表.
- 数组在内存中是地址连续的,而链表是离散的,每个节点都需要记录其后继节点(双向链表同时需要记录前节点)
- 数组只要知道了其中一个节点的地址,就能通过计算相对地址来访问其他节点,因此数组可以实现任意访问(ramdaomly access),适合读操作比较多的场景.
- 访问链表中的任意节点都需要从头节点开始遍历,逐一获取其后续节点,因此链表的写操作比较慢.但是也由于地址不连续,在增删节点时不需要考虑位置,直接修改相关的next节点就行了,因此链表适合频繁增删的场景.
链表与数组各有优点和缺点,这也是我们系统设计的一个特点 : 没有完美的方案,有的只是根据业务场景做出取舍,要么空间换时间,要么牺牲效率来提高安全性.
数据结构
就是一个名叫elementData的数组,默认的初始长度是10;
transient Object[] elementData; // non-private to simplify nested class access
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
初始化
ArrayList有三个构造方法:
无参时设置为空数组,直到第一次往list里面add数据才会初始化为长度为10的数组.这里的相关逻辑有几层调用链,后面扩容的时候再详细展开
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//设置成空数组
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
参数为集合时将其转化为数组:
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
当参数为一个整型,也就是指定数组长度时,新建一个指定长度的数组
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;//当传入的是0,处理方法和无参构造的一致
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
Add
由于list的get,set都太简单,这里就直接跳过来分析add了.和map一样,add也可能触发扩容.
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)//扩容条件,当数组满了的时候进行扩容
elementData = grow();
elementData[s] = e;
size = s + 1;
}
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)//也是满了就扩容
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);//如果在数组中间插入元素,那么就得复制一个新的数组了
elementData[index] = element;
size = s + 1;
}
- add之前会检查数组当前的容量,看看需不需要扩容.
- 由于list不像map那样复杂,一个位置只有一个元素,所以扩容条件只有一个: 数组已满
- 由于数组是连续的,如果是在指定位置插入,那么就需要复制一个新的数组来操作了.
也就是说,如果数组已满,且你又要再指定位置插入一个数据,那么数组将被复制两次.
一个小坑
来看一段代码
ArrayList<Integer> list=new ArrayList<>(10);
list.set(5,4);
这段代码可以正常运行吗?
可能有人会说list的大小是10,那我10以内比如往5的位置set个值应该没问题吧.
实际上会报一个数组越界的异常.
不过这并不算真正的越界,我们的数组长度还是10.
public E set(int index, E element) {
Objects.checkIndex(index, size);//边界选用的是size而不是length
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
@HotSpotIntrinsicCandidate
public static <X extends RuntimeException>
int checkIndex(int index, int length,
BiFunction<String, List<Integer>, X> oobef) {
if (index < 0 || index >= length)
throw outOfBoundsCheckIndex(oobef, index, length);
return index;
}
由于list里面判断边界用的是size(实际节点个数),而不是length(数组长度),所以这种情况会报一个"越界".
这种写法实际上是把list当成数组来用了.
官方认为虽然elementData是list的实现细节,但是它对外界是隐藏的,只能操作逻辑上的list而不是实际存在的elementData.
封装的一大意义,就是向用户屏蔽用户不需要的操作.否则,用户可能会有意无意地调用这些操作,这将成为软件工程中重要的bug来源.
如果list里面还没有元素,那么你只能add,不能get,set.
如果list的size是5,那么你就不能访问第五个元素之后的位置.
list的add还没走到后面的位置,你就不能提前去put或者set.
扩容
在list里面,扩容的函数是grow().
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private Object[] grow() {
return grow(size + 1);//扩容后数组长度最少+1
}
这里调用了Arrays.copyOf(),这个方法的作用就是将旧数组的内容复制到新的数组,新数组多出来的部分置为null.
里面是个native方法,源码就不贴了.
这里还调用了newCapacity(),这个方法用于判断新数组的长度.
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//新数组长度为原来的1.5倍,向下取整
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)//初始化,数组为空,则长度设为10
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
这里关键的两条表达式:
- newCapacity = oldCapacity + (oldCapacity » 1)
- if (newCapacity - minCapacity <= 0)
什么情况下第二条表达式为true呢?
- 当oldCapacity=0,minCapacity=0+1=1,newCapacity=0+0=0,那么newCapacity - minCapacity=-1 < 0.这对应的是数组为空的情况,也就是上面我们说的无参构造方法会走到这条逻辑,将数组初始化长度为10.
- 当0<oldCapacity<4时,newCapacity - minCapacity依然小于0,这种情况扩容后数组长度+1.
- 其余情况newCapacity - minCapacity>0,此时新数组长度=newCapacity,也就是原来的1.5倍(向下取整)
看到这里,也许你会默默总结 :
哦,原来扩容后,除了初始化外,数组的长度有两种情况,一种是+1,一种是+50%
其实当原长度=2或3时,扩容后它们虽然也是长度+1,但是1也是2和3的50%(向下取整).
所以看到没有,如果让我们来写这段逻辑,可能我们的思路是这样:
-
if 数组长度=0, then….
-
if 数组长度=1, then…
而JDK的大神们用一两条表达式就把各种情况清清楚楚地分隔开了.不禁膜拜……
缩容
ArrayList没有自动缩容的机制,不过它提供了一个方法把list的容量最小化(刚好装得下所有元素)
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);//同样是复制
}
}
Remove
和add一样,remove一样需要通过复制数组来进行.
但有一点不一样,add不指定位置时,默认插入到末尾,此时不需要复制.
而remove不指定位置时,默认从头开始找,然后删除找到的一个元素.那么删除的元素位置不确定,所以都当成删除中间的节点来处理,因此不论哪种情况都需要复制数组.
也许有人会建议作者找到对应元素后判断一下是否末尾元素,如果是直接置null不就节省了一次复制的操作了?
我以为,在实际情况中,要删除的节点恰好位于末尾是小概率事件,为了这小概率事件而每次都额外判断一次恐怕划不来.
删除指定位置:
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
根据**equals()**删除指定元素
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)//null也可以删,都是删除找到的第一个
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);//复制到新数组
es[size = newSize] = null;//最后一个位置设为null
}
简单概括下流程:
- 先遍历去查找元素,元素是null则找null,元素非null则调用equals()来比较.
- 删除找到的第一个元素,然后剩余元素复制到新的数组.
- 新数组的最后一个位置设为null
深克隆/浅克隆
这个在Hashmap那篇文章忘了讲,在这里补回来.
先看下定义:
浅克隆
被复制对象的所有变量都含有与原来的对象相同的值，而所有的对其他对象的引用仍然指向原来的对象。换言之，浅复制仅仅复制所拷贝的对象，而不复制它所引用的对象。
深克隆
被复制对象的所有变量都含有与原来的对象相同的值，除去那些引用其他对象的变量。那些引用其他对象的变量将指向被复制过的新对象，而不再是原有的那些被引用的对象。换言之，深复制把要复制的对象所引用的对象都复制了一遍。
其实它们的区别也就是值传递和引用传递的区别.
浅克隆=引用传递 深克隆=值传递
在我印象中,JDK好像没有几个类是实现深克隆的,所以如果不想复制后的新对象与旧对象相互干扰,在复制之前要重写clone()方法.
ArrayList的克隆方法
/**
* Returns a shallow copy of this {@code ArrayList} instance. (The
* elements themselves are not copied.)
*
* @return a clone of this {@code ArrayList} instance
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
注释写的很明白了,是浅复制(shallow copy).除了modCount置0之外,数组也是直接复制过去的.
如果改成深克隆的话,应该要遍历数组,依次调用每个元素的clone方法而不是直接复制.(要注意套娃的情况)
LinkedList
数据结构
LinkedList有一个内部类Node,这就是存取数据的结构了.
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内部也持有头尾双指针.
由于链表不存在扩容的概念,因此size是链表的长度也是实际元素的个数.
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
初始化
来看一下构造函数
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
空的.
没错是空的,它不需要像ArrayList先构造出一个数组那样现去构造出first节点.
first是null的就让它暂时null吧,等到add第一个元素再去构造.
Add
public boolean add(E e) {//插入一个节点,默认插入链尾
linkLast(e);
return true;
}
public void add(int index, E element) {//往特定位置插入
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
public void addFirst(E e) {//往头部插入
linkFirst(e);
}
public void addLast(E e) {往尾部插入
linkLast(e);
}
可以看到LinkedList支持往任意位置插入元素.
根据linkFirst,linkBefore,linkLast,插入可分为3种情况:
- 插入头部
- 插入到某元素前面
- 插入尾部
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);//小细节,这里是新建一个node而不是直接赋值
first = newNode;//new节点变为first节点
if (f == null)//链表是空的,那么first节点和last节点都同时为new节点
last = newNode;
else
f.prev = newNode;//原first节点的前驱变为new节点
size++;
modCount++;
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;//记录该节点的前驱
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;//该节点的前驱为new节点
if (pred == null)//该节点的前驱为null,也就是该节点为first节点
first = newNode;
else
pred.next = newNode;//前驱的next指向新节点
size++;
modCount++;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
常规的链表操作了,唯一需要注意的是 : 插入的不是节点本身,而是它的复制.
应该说,这里用到的只是这个节点的值,而不需要知道它前驱节点以及后继节点的信息.
所以对链表任意操作并不会影响插入时参考过的那些节点.
Remove
public E remove() {//默认删除头节点
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)//链表为空时抛出异常
throw new NoSuchElementException();
return unlinkFirst(f);
}
public E removeLast() {//删除尾节点
final Node<E> l = last;
if (l == null)//链表为空时抛出异常
throw new NoSuchElementException();
return unlinkLast(l);
}
public E remove(int index) {//删除指定位置的节点
checkElementIndex(index);
return unlink(node(index));//node(index)作用是返回index位置的节点
}
public boolean remove(Object o) {//删除找到的第一个指定的元素
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
删除也是支持指定任意位置,任意元素的.
删除同样分为三种情况:
- 删除头节点
- 删除尾节点
- 删除中间节点
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;//记录返回值
final Node<E> next = f.next;//记录后驱
f.item = null;//释放节点的资源, help GC就很骚了....
f.next = null; // help GC
first = next;//first节点后移
if (next == null)
last = null;//若链表只有一个first节点,那么删除后last也为null
else
next.prev = null;//否则next的前驱置为null,这里也可以写成first.prev=null
size--;
modCount++;
return element;
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
链表的操作也很简单,就不写那么多注释了(为偷懒找个接口).
“二分查找”?
链表的存取很简单,本来想直接跳过的,不过这次看源码又新发现了一个小的优化点,就顺便提一下.
在上面remove操作时有个node(idnex),这个函数在get和set中也用到.
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {//判断index位于链表的前半部分还是后半部分
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
前面提到过,LinkedList是支持操作任意节点的.
而我们又知道,链表的节点地址是离散的,那么访问中间的节点一定要从first节点开始遍历吗?
由于是双向链表,JDK在访问Linkedlist前,会先用 if (index < (size >> 1))判断一下要访问的节点位于前半部分还是后半部分.
如果是前半部分,就从first节点向后遍历;
如果是后半部分,就从last节点向前遍历.
最好的情况下,这样的优化可以把时间从O(n)降低到O(1).
这个问题并不难,只要意识到这个问题都能回答上来.
问题只在于意识.
写这一部分是为了提醒自己在一些小细节上不要忘了优化的意识.
队列 & 双向队列 & 栈
LinkedList作为双向链表,可以同时作为队列/双向队列/栈来使用.
作为队列时:
- peek : 返回头节点(并非删除)
- poll : 返回并删除头节点(出队)
- offer : 队尾新增节点(入队,等同于add)
作为双向队列时:
- push : 队首新增节点(入栈)
- pop : 返回并删除头节点(出栈)
还有很多api,像peekFirst,pollLast等等.不列举了.
api不用背的,用到的时候忘了,点进源码看下注释,一下就记起来了.
Clone
/**
* Returns a shallow copy of this {@code LinkedList}. (The elements
* themselves are not cloned.)
*
* @return a shallow copy of this {@code LinkedList} instance
*/
public Object clone() {
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
和ArrayList一样,也是浅复制