共计 2446 个字符,预计需要花费 7 分钟才能阅读完成。
ArrayList 与 linkedList 源码分析
ArrayList
底层实现为数组,支持随机访问,可根据索引查找元素,插入删除中间元素时间复杂度为 O(n);
默认初始容量为 10,使用默认初始容量时懒分配,扩容机制 1.5 倍;
线程不安全;
类图结构
重要属性
// 默认容量 10
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;
构造方法
// 设置初始容量的构造方法
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);
}
}
// 无参构造
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
public ArrayList(Collection<? extends E> c) {elementData = c.toArray();
if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
扩容方法
1.5 倍扩容;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 扩容 1.5 倍大小
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 新扩容容量溢出
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 新扩容容量大于 MAX_ARRAY_SIZE (Integer.MAX_VALUE - 8) 就分配 Integer.MAX_VALUE 的空间
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 拷贝元素
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
添加元素分析
public boolean add(E e) {
// 先确认添加元素时容量是否足够
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 未初始化容量则初始化,并返回
private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果新元素添加进来,新元素大于容量则扩容
//minCapacity - elementData.length == 新元素个数 - 原数组容量
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
LinkedList
底层实现为双链表,插入删除中间元素时间复杂度为 O(1),查找为 O(n);
线程不安全;
类图结构
内部结构
// 内部类节点,双链表
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;
}
}
正文完