ArrayList
ArrayList是一种变长集合，基于定长数组实现，允许空值和重复元素，是线程不安全的集合。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
构造函数
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
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;
}
}
查找 get()
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
ArrayList的查找比较简单，因为是数组，所以时间复杂度是O（1）的。
插入 add()
插入提供了两个API分别是插入元素序列的队尾，另一个是插入指定位置
/** 在元素序列尾部插入 */
public boolean add(E e) {
// 1. 检测是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 将新元素插入序列尾部
elementData[size++] = e;
return true;
}
/** 在元素序列 index 位置处插入 */
public void add(int index, E element) {
rangeCheckForAdd(index);
// 1. 检测是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 将 index 及其之后的所有元素都向后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 3. 将新元素插入至 index 处
elementData[index] = element;
size++;
}
在插入队尾的时候：
- 是否需要扩容
- 插入队尾
如果是插入指定位置，则
- 判断容量是否足够
- 把需要插入位置后面的元素向后移动一位
- 将新元素插入
判断扩容以及扩容逻辑
/** 计算最小容量 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/** 扩容的入口方法 */
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/** 扩容的核心方法 */
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// newCapacity = oldCapacity + oldCapacity / 2 = oldCapacity * 1.5
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 如果最小容量超过 MAX_ARRAY_SIZE，则将数组容量扩容至 Integer.MAX_VALUE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
可以看出，当需要扩容的时候则按照原先数组的1.5倍进行扩容（ oldCapacity + (oldCapacity >> 1)）
删除元素
/** 删除指定位置的元素 */
public E remove(int index) {
rangeCheck(index);
modCount++;
// 返回被删除的元素值
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 将 index + 1 及之后的元素向前移动一位，覆盖被删除值
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将最后一个元素置空，并将 size 值减1
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];
}
/** 删除指定元素，若元素重复，则只删除下标最小的元素 */
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 遍历数组，查找要删除元素的位置
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/** 快速删除，不做边界检查，也不返回删除的元素值 */
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
- 获取指定位置 index 处的元素值
- 将 index + 1 及之后的元素向前移动一位
- 将最后一个元素置空，并将 size 值减 1
- 返回被删除值，完成删除操作
当添加大量元素后，紧接着删除了大量元素后，Arraylist并没有对于多余的数组长度进行缩减，但是对外暴露了api进行释放多余空间，提高空间的利用率
/** 将数组容量缩小至元素数量 */
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
最后，在遍历过程中删除添加元素，有可能导致意料之外的结果，所以应该使用迭代器方法进行删除添加，这点有很多方法和介绍可以在网络上找到答案
LinkedList
LinkedList相对于ArrayList继承关系就复杂的多
LinkedList
LinkedList继承自AbstractSequentialList,AbstractSequentialList提供了一套用于顺序访问的接口，通过继承此类，仅需要实现部分代码就可以拥有完整的一套访问某种序列表（链表）的接口
public E get(int index) {
try {
return listIterator(index).next();
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public void add(int index, E element) {
try {
listIterator(index).add(element);
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
// 留给子类实现
public abstract ListIterator<E> listIterator(int index);
所以只要继承类实现了 listIterator 方法，它不需要再额外实现什么即可使用。对于随机访问集合类一般建议继承 AbstractList 而不是 AbstractSequentialList。LinkedList 和其父类一样，也是基于顺序访问。所以 LinkedList 继承了 AbstractSequentialList，但 LinkedList 并没有直接使用父类的方法，而是重新实现了一套的方法。
另外，LinkedList 还实现了 Deque (double ended queue)，Deque 又继承自 Queue 接口。这样 LinkedList 就具备了队列的功能。比如，我们可以这样使用：
Queue<T> queue = new LinkedList<>();
除此之外我们还可以实现一些其他的数据结构，比如栈
查找 get()
LinkedList基于链表，所以查找的时间复杂度为O(N).
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
/*
* 则从头节点开始查找，否则从尾节点查找
* 查找位置 index 如果小于节点数量的一半，
*/
if (index < (size >> 1)) {
Node<E> x = first;
// 循环向后查找，直至 i == index
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;
}
}
可以看到，链表的查找显示判断index处于的位置，如果处于前半部分则查找前半部分，如果是处于后半部分，则从后半部分开始查找。由于随机访问的效率很低，应该避免使用LinkedLsit来进行大数据量下的随机访问。
插入
/** 在链表尾部插入元素 */
public boolean add(E e) {
linkLast(e);
return true;
}
/** 在链表指定位置插入元素 */
public void add(int index, E element) {
checkPositionIndex(index);
// 判断 index 是不是链表尾部位置，如果是，直接将元素节点插入链表尾部即可
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/** 将元素节点插入到链表尾部 */
void linkLast(E e) {
final Node<E> l = last;
// 创建节点，并指定节点前驱为链表尾节点 last，后继引用为空
final Node<E> newNode = new Node<>(l, e, null);
// 将 last 引用指向新节点
last = newNode;
// 判断尾节点是否为空，为空表示当前链表还没有节点
if (l == null)
first = newNode;
else
l.next = newNode; // 让原尾节点后继引用 next 指向新的尾节点
size++;
modCount++;
}
/** 将元素节点插入到 succ 之前的位置 */
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
// 1. 初始化节点，并指明前驱和后继节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 2. 将 succ 节点前驱引用 prev 指向新节点
succ.prev = newNode;
// 判断尾节点是否为空，为空表示当前链表还没有节点
if (pred == null)
first = newNode;
else
pred.next = newNode; // 3. succ 节点前驱的后继引用指向新节点
size++;
modCount++;
}
LinkedList的插入操作实际就是链表的插入操作，我们知道往链表中插入一个数据的话，需要断开链然后使前一个节点连接到新节点，然后用新节点连接后一个节点，这样就成功插入，删除的原理类似。同样将节点处的连接断开再连接前后节点就实现了删除操作
网友评论