Java集合框架之List

1.List集合概要

2.Iterable接口

1.概要

2.重要方法

1. forEach方法：对Collection集合中的每个对象进行消费

List<Student> list = Stream.generate(() -> new Student("张三", 23)).limit(100).collect(Collectors.toList());
list.forEach(System.out::println);

2. spliterator方法：获取Spliterator迭代器

3.Collection接口

1.重要方法

1. spliterator()：创建Spliterator
2. stream()：创建串行流Stream
3. parallelStream()：创建并行流Stream

4.RandomAccess接口

1.概要

这是一种标识型接口，用于标识某个类具有某种功能特性的接口。

5.Vector

1.Vector集合概要

Vector是一个线程安全的集合，其中的大部分方法都加了synchronized关键字。

2.重要变量

1. Vector中重要的变量信息

// 集合Vector存放对象的数组
protected Object[] elementData;
// 集合Vector存储的对象数量
protected int elementCount;
// elementData数组每次扩容的大小
protected int capacityIncrement;

3.Vector的扩容操作

1. 初始化Vector的扩容操作

// 1. 指定了初始化容量和每次扩容时的增量
// 则下次扩容为initialCapacity + capacity，依次类推
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}
// 2. 指定初始化容量和每次扩容时的增量为0
// 则下次扩容为2 * initialCapacity
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}
// 3.指定初始化容量为10，则下次扩容为20， 40...
public Vector() {
    this(10);
}

2. 向集合Vector添加对象，elementData数组容量不足时：2倍扩容

// minCapacity为期望的elementData数组容量
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 客户指定的每次数组扩容大小超过0，则扩容为newCapacity = oldCapacity + capacityIncrement
    // 否则进行2倍扩容
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    // 确保数组扩容为期望的elementData数组容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

3. 客户端重新设置Vector的容量时，可能会进行扩容操作

public synchronized void setSize(int newSize) {
    modCount++;
    // 新容量大于当前Vector集合中的对象数量则进行扩容
    if (newSize > elementCount) {
        ensureCapacityHelper(newSize);
    } else {
        for (int i = newSize ; i < elementCount ; i++) {
            elementData[i] = null;
        }
    }
    elementCount = newSize;
}

6.ArrayList

1.ArrayList概要

ArrayList是一个多线程环境下有些操作不安全的集合

2.ArrayList集合中重要的常量和变量

// 默认的初始化数组容量
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存放集合ArrayList中的对象的数组
transient Object[] elementData;
// 集合ArrayList中包含的对象数量
private int size;

3.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);
    }
}
// 构造一个长度为0的ArrayList集合，
// 后面使用add方法添加元素会将elementData扩容成长度为10的数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 根据另一个集合构造ArrayList
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;
    }
}

4.ArrayList的扩容操作

1. 扩容：按照1.5倍扩容

// minCapacity为期望的数组最低容量（即原数组容量 + 1）
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 1.5倍进行扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 确保容器达到最低容量10，最低下限
    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);
}

5.ArrayList内部数组的移动操作

1. 移动数组元素的操作都是通过System.arraycopy这个本地方法完成。

6.ArrayList的删除操作removeIf

1. 删除操作removeIf方法中使用BitSet根据相应的位标记需要删除的元素。

// size为容器中的元素个数
final BitSet removeSet = new BitSet(size);
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
    @SuppressWarnings("unchecked")
    final E element = (E) elementData[i];
    if (filter.test(element)) {
        // 需要删除的元素标记为1
        removeSet.set(i);
        // 统计需要删除的元素个数
        removeCount++;
    }
}

7.Vector和ArrayList的对比

1. 两者的内部结构都是数组。
2. Vector集合默认采用当前容量的1倍大小进行扩容，且可以指定一个固定的扩容增量；ArrayList再进行扩容操作时会将当前容量增大50%。
3. Vector集合大大部分操作都是线程安全的，但是使用的是synchronized锁，锁的粒度太过粗放，保证线程安全性不推荐使用Vector；ArrayList集合不是线程安全的，在多线程环境下不能使用它。
4. Vector集合在序列化的过程中，当前elementData数组中多余的索引位被序列化，产生不必要的性能消耗；在对ArrayList集合进行序列化时，只会对elementData数组中已使用的索引位进行序列化，未使用的索引位不会被序列化；相对地，在原ArrayList集合中已被序列化的各个数据对象被反序列化成新的ArrayList集合中的数据对象时，新的elementData数组不会产生多余的容量，只有在下一次被要求向该集合中添加数据对象时，才会开始新一轮的扩容操作。

7.Stack

1.Stack概要

2.Stack和Vector的对比

1. Stack继承自Vector，内部结构都是数组，都存在数组扩容的问题，每次将数组容量增大一倍的方式不灵活。
2. 两者都是线程安全的，但是不推荐使用。已经被LinkedBlockingQueue和CopyOnWriteArrayList等替代。
3. 两者没有针对序列化过程和反序列化过程进行任何优化，而工作效果相似的ArrayDeque集合、ArrayList集合都对序列化过程的反序列化过程进行了优化。

8.LinkedList

1.LinkedList集合的继承体系

2.LinkedList中重要的变量

1. LinkedList底层由双向链表实现

// 集合LinkedList的对象个数
transient int size = 0;
// 指向头节点（双向链表的第一个节点）
transient Node<E> first;
// 指向尾节点（双向链表的最后一个节点）
transient Node<E> first;
// 双链表节点结构
private static class Node<E> {
        // 节点存储的元素
        E item;
        // 指向下一个节点
        Node<E> next;
        // 指向前一个节点
        Node<E> prev;
}

3.LinkedList集合的添加操作

1. linkFirst(E e)：在双链表头部插入一个新节点
2. linkLast(E e)：在双链表尾部插入一个新节点
3. linkBefore(E e, Node succ)：在指定节点前插入一个新节点

4.LinkedList集合的移除操作

1. unlinkFirst(Node f)：移除双链表的第一个节点
2. unlinkLast(Node l)：移除双链表的最后一个节点
3. unlink(Node x)：移除双链表的指定节点

5.LinkedList的查找操作

1. 查询指定索引位置的节点

// 根据索引和集合长度的一半对比，来决定在头部还是尾部开始搜索。
Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

6.LinkedList和ArrayList的对比

1. 基于数组结构的ArrayList的删除和插入操作效率不高，需要考虑数组扩容元素复制、移动数组元素的问题；基于双向链表的LinkedList的插入和修改操作需要考虑查询索引位的节点的时间消耗，如果在靠近双向链表的中间位置插入新的节点，则找到正确的索引位置节点的时间复杂度为o(n)。
2. ArrayList集合支持随机访问，所以查询的效率很高，时间复杂度为O(1)；LinkedList集合的查询操作时间复杂度为o(n);