集合类实现
List 接口
是 ArrayList 等列表集合的父接口。主要特性有 ：
- 是一个有序的集合，插入元素默认是插入到尾部，按顺序从前往后存放，每个元素都有一个自己的下标位置
- 列表中允许存在重复元素
//List是一个有序的集合类，每个元素都有一个自己的下标位置
//List中可插入重复元素
//针对于这些特性，扩展了Collection接口中一些额外的操作
public interface List<E> extends Collection<E> {
...
//将给定集合中所有元素插入到当前结合的给定位置上（后面的元素就被挤到后面去了，跟我们之前顺序表的插入是一样的）
boolean addAll(int index, Collection<? extends E> c);
...
//Java 8新增方法，可以对列表中每个元素都进行处理，并将元素替换为处理之后的结果
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator(); //这里同样用到了迭代器
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
//对当前集合按照给定的规则进行排序操作，这里同样只需要一个Comparator就行了
@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
...
//-------- 这些是List中独特的位置直接访问操作 --------
//获取对应下标位置上的元素
E get(int index);
//直接将对应位置上的元素替换为给定元素
E set(int index, E element);
//在指定位置上插入元素，就跟我们之前的顺序表插入是一样的
void add(int index, E element);
//移除指定位置上的元素
E remove(int index);
//------- 这些是List中独特的搜索操作 -------
//查询某个元素在当前列表中的第一次出现的下标位置
int indexOf(Object o);
//查询某个元素在当前列表中的最后一次出现的下标位置
int lastIndexOf(Object o);
//------- 这些是List的专用迭代器 -------
//迭代器我们会在下一个部分讲解
ListIterator<E> listIterator();
//迭代器我们会在下一个部分讲解
ListIterator<E> listIterator(int index);
//------- 这些是List的特殊转换 -------
//返回当前集合在指定范围内的子集
List<E> subList(int fromIndex, int toIndex);
...
}
可以看到，在List接口中，扩展了大量列表支持的操作，其中最突出的就是直接根据下标位置进行的增删改查操作。
ArrayList 类
用数组实现的，内部维护的是一个可动态进行扩容的数组
继承自 List 类。在ArrayList中，底层就是采用数组实现的，跟我们之前的顺序表思路差不多：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//默认的数组容量
private static final int DEFAULT_CAPACITY = 10;
...
//存放数据的底层数组，这里的transient关键字我们会在后面I/O中介绍用途
transient Object[] elementData;
//记录当前数组元素数的
private int size;
//这是ArrayList的其中一个构造方法
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 boolean add(E e) {
ensureCapacityInternal(size + 1); // 这里会判断容量是否充足，不充足需要扩容
elementData[size++] = e;
return true;
}
...
//默认的列表最大长度为Integer.MAX_VALUE - 8
//JVM都C++实现中，在数组的对象头中有一个_length字段，用于记录数组的长
//度，所以这个8就是存了数组_length字段（这个只做了解就行）
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //扩容规则跟我们之前的是一样的，也是1.5倍
if (newCapacity - minCapacity < 0) //要是扩容之后的大小还没最小的大小大，那么直接扩容到最小的大小
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //要是扩容之后比最大的大小还大，需要进行大小限制
newCapacity = hugeCapacity(minCapacity); //调整为限制的大小
elementData = Arrays.copyOf(elementData, newCapacity); //使用copyOf快速将内容拷贝到扩容后的新数组中并设定为新的elementData底层数组
}
}
使用
一般我们要使用一个集合类，我们会用接口的引用 :
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("test");
System.out.println(list);
}删除元素：
.remove(Object o) 若传入是 int 类型则会根据多态性质删除对应下标的值。内核是调用 .equals 判断相等并删除，所以如果传入的对象跟要删除的对象地址不同，也可以删除。
生成只读列表：
Arrays.asList("a", "b", "c") 静态方法，用于一些不需要修改， 只需要通过下标访问的时候。若想访问，则可以把该列表传入构造方法中 new Array<>(aslist)。
LinkedList 双链表
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
//引用首结点
transient Node<E> first;
//引用尾结点
transient Node<E> last;
//构造方法，很简单，直接创建就行了
public LinkedList() {
}
...
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;
}
}
...
}LinkedList的使用和ArrayList的使用几乎相同，各项操作的结果也是一样的，在什么使用使用ArrayList和LinkedList，我们需要结合具体的场景来决定，尽可能的扬长避短。
只不过LinkedList不仅可以当做List来使用，也可以当做双端队列使用，我们会在后面进行详细介绍。