Java面试中关于容器类List，Set是必问题目。但在我的面试经历中很难遇到满意的答复。大部分只能了解其大概使用方法，对其内部结构缺乏了解，错误的使用方式会导致性能大幅下降。
首先介绍ArrayList，顾名思义内部数据结构是数组
private transient Object[] elementData;
private int size;
public ArrayList(int initialCapacity){
}
在增加元素时，若容量不足进行扩充
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
新数组大小为之前数组大小*1.5+1 ，加上1保证oldCapacity为1的情况也能扩充为2
（类似分页时总页数=(总记录数+ （每页记录数-1）)/每页记录数算法)
删除元素时通过 System.arraycopy把删除位置后的所有元素前移一个位置实现
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
LinkedList大家都知道是通过链表实现，内部是一个双向链表
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
}
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
}
插入和删除都只要改动前后节点的next和previous实现
总结特点如下：
| 类型 | 内部结构 | 顺序遍历速度 | 随机遍历速度 | 追加代价 | 插入代价 | 删除代价 | 占用内存 |
| ArrayList | 数组 | 高 | 高 | 中 | 高 | 高 | 低 |
| LinkedList | 双向链表 | 高 | 低 | 低 | 低 | 低 | 中 |
所以：
- 一般顺序遍历情况下使用ArrayList，但注意构造函数中设置初始大小
- 尽量不对ArrayList进行插入或删除操作(删除尾部除外),若有多次删除/插入操作又有随机遍历的需求，可以再构建一个ArrayList，把复合条件的对象放入新ArrayList，而不要频繁操作原ArrayList
- 经常有删除/插入操作而顺序遍历列表的情况下最适合使用LinkedList
已有 0 人发表留言，猛击->>这里<<-参与讨论
ITeye推荐