ArrayList和LinkedList学习
摘要
arraylist和linkedlist是对list接口的不同数据结构的实现。它们都是线程不安全的，线程不安全往往出现在数组的扩容、数据添加的时候。
一、arraylist和linkedlist是什么？
arraylist：arraylist是list接口的可变数组的实现。
linkedlist：linkedlist是list接口的（双向）链表实现。
二、两个list的数据结构
1、arraylist的数据结构
arraylist的类继承图如下：
存储
arraylist使用数组（elememntdata）存储数据，默认构造方法创建arraylist时，会初始化一个空数组。
扩容
arraylist使用数组存储数据，因此在添加数据的时候需要做容量检查，如果容量不足则需要进行扩容。
其新容量大小公式为：新容量=旧容量+旧容量/2
扩容过程请看下面源码：
public boolean add(e e) {
// 容量检查
ensurecapacityinternal(size + 1); // increments modcount!!
elementdata[size++] = e;
return true;
}
// 计算数组需要的最小容量
private void ensurecapacityinternal(int mincapacity) {
if (elementdata == defaultcapacity_empty_elementdata) {
mincapacity = math.max(default_capacity, mincapacity);
}
ensureexplicitcapacity(mincapacity);
}
// 判断是否需要扩容，如果需要则扩容
private void ensureexplicitcapacity(int mincapacity) {
// modcount表示list结构修改的次数，快速失败机制会用到，快速失败机制在后面会详细说明。
modcount++;
// overflow-conscious code
if (mincapacity - elementdata.length > 0)
grow(mincapacity);
}
private void grow(int mincapacity) {
// overflow-conscious code
int oldcapacity = elementdata.length;
// 新容量=旧容量+旧容量/2
int newcapacity = oldcapacity + (oldcapacity >> 1);
if (newcapacity - mincapacity < 0)
newcapacity = mincapacity;
if (newcapacity - max_array_size > 0)
newcapacity = hugecapacity(mincapacity);
// mincapacity is usually close to size, so this is a win:
elementdata = arrays.copyof(elementdata, newcapacity);
}
2、linkedlist的数据结构
linkedlist的类继承图如下：
存储
linkedlist使用双向链表来存储数据。其中链表结点定义如下：
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添加删除元素，实际上就是对链表进行结点添加/删除，下面给出实现细节，以供后面的线程安全讨论使用（注意modcount发生了变化）。
// 添加元素
public boolean add(e e) {
// 往链表末尾添加元素
linklast(e);
return true;
}
// 添加结点
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++;
}
// 删除元素（删除第一个匹配的元素）
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;
}
// 删除结点
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;
}
三、线程安全讨论
首先确认一点的是，arraylist和linkedlist均是线程不安全的，下面将分析多线程情况下会出现的一些问题。
1、快速失败（fail-fast）
快速失败，指的是使用遍历器对list进行遍历时，如果在遍历过程中，对list进行了修改，则会触发快速失败机制，抛出java.util.concurrentmodificationexception异常。
快速失败触发机制
前文谈到modcount的作用用于记录list的修改次数，在遍历器进行遍历时，代码正是通过这个值触发快速失败的。
相关核心代码如下：
int expectedmodcount = modcount;
public e next() {
checkforcomodification();
try {
int i = cursor;
e next = get(i);
lastret = i;
cursor = i + 1;
return next;
} catch (indexoutofboundsexception e) {
checkforcomodification();
throw new nosuchelementexception();
}
}
// 检查修改次数，该方法在类中多次会被调用
final void checkforcomodification() {
if (modcount != expectedmodcount)
throw new concurrentmodificationexception();
}
2、arraylist添加元素时的数组越界问题
添加元素时的数组越界问题发生在扩容判断上，当当前数组容量还差一个元素达到数组扩容的临界值时。并发插入元素时对数组大小的判断均是无需扩容，但是当前数组实际上仅有一个空闲位置，因此数组越界异常就发生了。
3、添加元素被覆盖
这种异常出现情况如下面代码注释所示：
多个线程对数组同一个位置进行赋值，导致元素被覆盖。
elementdata[size++] = e; // elementdata[size] = e; --- thread1 // elementdata[size] = e; --- thread2 // size++; --- thread1 // size++; --- thread2
类似的分析，linkedlist添加元素时也会出现这种情况。
4、线程安全的list
同步方法
全部使用同步方法，如：vector、collections.synchronizedlist(list)
其它加锁
其它加锁实现线程安全，如：concurrentlinkeddeque（自旋+cas）、copyonwritearraylist（读写锁）
参考资料
上一篇： jQuery 事件介绍
下一篇： P2613 【模板】有理数取余 (数论)