集合类(二)

ArrayList/LinkedList/Vector

ArrayList

允许包括 null 在内的所有元素、有序、可重复、线程不安全

定义

继承AbstractList，实现List、RandomAccess

1
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

底层存储

1
transient Object[] elementData;

属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//初始容量
private static final int DEFAULT_CAPACITY = 10;
//共享空数组实例，用于空实例，调用构造函数容量为0时，会赋予数据的数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//共享空数组实例用于默认大小的空实例。使用默认构造函数时，会赋予数据的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//容量大小
private int size;
//最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造方法

1
2
3
4
5
6
7
8
9
//默认构造，初始容量为10
public ArrayList()
//通过initialCapacity指定初始容量
public ArrayList(int initialCapacity)
//使用集合进行初始化，元素的顺序是传入集合的迭代器返回的顺序
public ArrayList(Collection<? extends E> c)

add

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//添加元素
public boolean add(E e) {
	ensureCapacityInternal(size + 1);// 确保能够存放添加元素，容量不足则扩容
	elementData[size++] = e;
	return true;
}
//往指定位置插入元素
public void add(int index, E element) {
	rangeCheckForAdd(index);
	ensureCapacityInternal(size + 1);
	System.arraycopy(elementData, index, elementData, index + 1,
					 size - index);
	elementData[index] = element;
	size++;
}

在add一个元素时，才对容量进行了操作，以防止new出一个数组，但是不用，导致空间资源的浪费

扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private void ensureCapacityInternal(int minCapacity) {
	//这里可以看出定义两个不同的空数组属性的原因就是为了保证
	//当我们使用默认构造方法对ArrayList进行构造时，初始容量为10
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
		minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
	modCount++;
	//当最小所需容量大于当前数组容量时进行grow扩容操作
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}
private void grow(int minCapacity) {
	int oldCapacity = elementData.length;
	//扩充为1.5倍，如果还不够，那么就使用minCapacity作为当前扩充的容量大小
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity);
	//拷贝数组，生成新的数组  
	elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList

底层基于链表、允许包括null的所有元素、有序、线程不安全

定义

继承AbstractSequentialList，实现List、Deque（即能将LinkedList当作双端队列使用）

1
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

属性

1
2
3
4
5
6
7
8
//大小
transient int size = 0;
//头结点
transient Node<E> first;
//尾结点
transient Node<E> last;

结点定义

1
2
3
4
5
6
7
8
9
10
11
12
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;
	}
}

构造方法

1
2
3
4
//默认构造
public LinkedList()
//构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列
public LinkedList(Collection<? extends E> c)

常用方法

底层的具体操作都是基于链表的操作，具体查看源码。。

与ArrayList的区别

  1. ArrayList是实现了基于动态数组的数据结构，而LinkedList是基于链表的数据结构
  2. 随机访问get和set，ArrayList优于LinkedList / 对于add和remove，LinedList比较占优势
  3. 当容量不足时，ArrayList需要进行扩容操作，实际上就是创建出一个更大的数组，然后将旧数组中的值拷贝到新数组中。

Vector

与ArrayList一样底层基于动态数组，但线程安全

定义

继承AbstractList，实现List、RandomAccess

1
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

底层存储

1
protected Object[] elementData;

属性

1
2
3
4
5
6
//元素数量
protected int elementCount;
//容量增量
protected int capacityIncrement;
//最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//构造一个空向量，使其内部数据数组的大小为 10，其标准容量增量为零
//创建的时候就分配了10个元素的内存，而ArrayList是在第一次add的时候才真正分配的内存
public Vector()
  
//构造一个包含指定 collection 中的元素的向量，这些元素按其 collection 的迭代器返回元素的顺序排列
public Vector(Collection<? extends E> c)
  
//使用指定的初始容量和等于零的容量增量构造一个空向量
public Vector(int initialCapacity)
//使用指定的初始容量和容量增量构造一个空的向量
//通过此构造方法来创建一个Vector时，当容量不足时扩充的容量大小是capacityIncrement
public Vector(int initialCapacity, int capacityIncrement)

扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
private void grow(int minCapacity) {
	//当capacityIncrement>0时，扩充后的容量为oldCapacity + capacityIncrement
	//否则为2*oldCapacity
	int oldCapacity = elementData.length;
	int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
									 capacityIncrement : oldCapacity);
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity);
	elementData = Arrays.copyOf(elementData, newCapacity);
}