- List 按照规则加入list
- Set 加入list中的元素不能重复
- Queue 队列中的元素按照FIFO规则操作
List
- Positional access — manipulates elements based on their numerical position in -the list. This includes methods such as get, set, add, addAll, and remove.
- Search — searches for a specified object in the list and returns its numerical position. Search methods include indexOf and lastIndexOf.
- Iteration — extends Iterator semantics to take advantage of the list's sequential nature. The listIterator methods provide this behavior.
- Range-view — The sublist method performs arbitrary range operations on the list.
ArrayList
ArrayList存储结构是数组，数组A在申请空间时都是固定大小的，如果A空间不足，就需要重新申请更大的数组B存储数据，然后把A中数据复制到B上。
重新申请arrayB的策略： 按照arrayA的size的一半增加，sizeB = sizeA + sizeA/2。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}
Arrays.copyOf 由 System.arraycopy实现，arraycopy效率涉及到JVM，参考https://www.zhihu.com/question/53749473
LinkedList
根据index查找元素的策略是： 如果index < size/2，从first->last向后遍历，否则从last->first向前遍历。
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
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;
}
}
