第十四章 集合（List）

一、集合框架体系

集合：
（1）可以动态保存任意多个对象。
（2）提供了一系列方便的操作对象的方法：add、remove、set、get等。

二、Collection

1. Collection 接口常用方法

（1）add：添加单个元素
（2）remove：删除指定元素
（3）contains：查找元素是否存在
（4）size：获取元素个数
（5）isEmpty：判断是否为空
（6）clear：清空
（7）addAll：添加多个元素
（8）containsAIl：查找多个元素是否都存在
（9）removeAll：删除多个元素

2. Collection 接口遍历元素方式1，使用 Iterator（迭代器）

（1）Iterator 对象称为迭代器，主要用于遍历 Collection集合 中的元素。
（2）所有实现了 Collection接口 的集合类都有一个 iterator() 方法，用以返口一个实现了Iterator接口 的对象，即可以返回一个迭代器。
（3）Iterator 仅用于遍历集合，lterator 本身并不存放对象。

public class Test {
 
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
 
        // list.iterator() 重置迭代器，可重复
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            System.out.println(next);
        }
    }
}

3. Collection 接口遍历元素方式2，for循环增强

增强 for 循环，可以代替 iterator 迭代器，特点：增强 for 本质就是迭代器。只能用于遍历集合或数组。

public class Test {
 
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
 
        for (Integer e : list) {
            System.out.println(e);
        }
    }
}

三、List

1. List 接口基本介绍

（1）List 接口是 Collection 接口的子接口。
（2）List 集合类中元素 有序（即添加顺序和取出顺序一致）、且 可重复。
（3）List 集合中的每个元素都有其对应的顺序索引，即 支持索引。
（4）List 容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。

2. List 集合里添加了一些根据 索引 来操作集合元素的方法

（1）void add (int index, Object ele）：在 index 位置插入 ele 元素。
（2）boolean addAll (int index, Collection eles)：从 index 位置开始将 eles 中的所有元素添加进来。
（3）Object get (int index)：获取指定 index 位置的元素。
（4）int indexOf (Object obj)：返回 obj 在集合中首次出现的位置。
（5）int lastlndexOf (Object obj)：返回 obj 在当前集合中末次出现的位置。
（6）Object remove (int index)：移除指定 index 位置的元素，并返回此元素。
（7）Object set (int index, Object ele)：设置指定 index 位置的元素为 ele，相当于是替换。
（8）List subList (int fromlndex，int tolndex)：返回从 fromlndex 到（tolndex -1）位置的子集合。

public class Test {
 
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("乔峰");
        list.add("段誉");
        list.add(1, "虚竹");
        list.add("Tom");
        System.out.println(list); // [乔峰, 虚竹, 段誉, Tom]
 
        List<String> list2 = new ArrayList<>();
        list2.add("Jack");
        list2.add("Tom");
        list.addAll(1, list2);
        System.out.println(list); // [乔峰, Jack, Tom, 虚竹, 段誉, Tom]
 
        System.out.println(list.get(1)); // Jack
        System.out.println(list.indexOf("Tom")); // 2
        System.out.println(list.lastIndexOf("Tom")); // 5
 
        list.remove(5);
        System.out.println(list); // [乔峰, Jack, Tom, 虚竹, 段誉]
        list.set(2, "Mike");
        System.out.println(list); // [乔峰, Jack, Mike, 虚竹, 段誉]
        System.out.println(list.subList(0, 2)); // [乔峰, Jack]
    }
}

四、ArrayList（P509）

1. ArrayList的注意事项

（1）ArrayList 可以加入 null，并且多个。
（2）ArrayList 是由数组来实现数据存储的。
（3）ArrayList 基本等同于 Vector。ArrayList 是线程不安全（执行效率高），在多线程情况下，不建议使用 ArrayList。

2. ArrayList的底层操作机制 源码 分析（P510）

（1）ArrayList 中维护了一个 Object 类型的数组，transient Object[] elementData（transient 表示该属性不会被序列化）。
（2）当创建 ArrayList 对象时，如果使用的是无参构造器，则初始 elementData 容量为 0。第一次添加，则扩容 elementData 为 10。如果需要再次扩容的话，则扩容 elementData 为1.5 倍。
（3）如果使用的是指定大小的构造器，则初始 elementData 容量为指定大小，如果需要扩容，则直接扩容 elementData 为1.5倍。

public class ArrayList_<E> {
 
    transient Object[] elementData;
 
    private int size;
 
    protected transient int modCount = 0;
 
    private static final int DEFAULT_CAPACITY = 10;
 
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
    // 无参构造
    public ArrayList_() {
        // 创建一个空的数组
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
 
    public ArrayList_(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } 
    }
 
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 在 elementData[size] 赋值，并且size++
        elementData[size++] = e;
        return true;
    }
 
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
 
    private void ensureExplicitCapacity(int minCapacity) {
        // 操作次数
        modCount++;
 
        // overflow-conscious code
        // 判断是否扩容，如果elementData数组大小不够就扩容
        if (minCapacity - elementData.length > 0){
            grow(minCapacity);
        }
 
    }
 
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
 
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
    // 扩容方法
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 扩容为1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0){
            newCapacity = minCapacity;
        }
        // 防止超过最大值2147483639
        if (newCapacity - MAX_ARRAY_SIZE > 0){
            newCapacity = hugeCapacity(minCapacity);
        }
        // minCapacity is usually close to size, so this is a win:
        // Arrays.copyOf 可以保留原先的数据，并扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
 
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0){
            // overflow
            throw new OutOfMemoryError();
        }
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }
}

五、Vector（P513）

1. Vector 的基本介绍

（1）Vector 类的定义说明

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

（2）Vector 底层也是一个对象数组 protected Object[] elementData;
（3）Vector 是线程同步的，即线程安全，Vector 类的操作方法带有 synchronized。
（4）在开发中，需要线程同步安全时，考虑使用 Vector。

2. Vector 的底层操作机制源码分析

Vector 扩容源码类似于 ArrayList

public class Vector_<E> {
 
    protected Object[] elementData;
 
    protected int capacityIncrement;
 
    protected transient int modCount = 0;
 
    protected int elementCount;
 
    public Vector_() {
        this(10);
    }
 
    public Vector_(int initialCapacity) {
        this(initialCapacity, 0);
    }
 
    public Vector_(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0){
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
        // 初始化数组
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
 
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
 
    private void ensureCapacityHelper(int minCapacity) {
        // 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
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0){
            newCapacity = minCapacity;
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

六、LinkedList（P515）

1. LinkedList 说明

（1）LinkedList 底层实现了双向链表和双端队列特点。
（2）可以添加任意元素（元素可以重复），包括 null。
（3）线程不安全，没有实现同步。

2. LinkedList 的底层操作机制

（1）LinkedList 底层维护了一个双向链表。
（2）LinkedList 中维护了两个属性 first 和 last 分别指向首节点和尾节点。
（3）每个节点（Node对象），里面又维护了 prev 、next 、item 三个属性，其中通过 prev 指向前一个，通过 next 指向后一个节点。最终实现双向链表。
（4）所以 LinkedList 的元素的添加和删除，不是通过数组完成的，相对来说 效率较高。

3. LinkedList 源码 解读（P516）

public class LinkedList_<E> {
 
    transient int size = 0;
    protected transient int modCount = 0;
 
    transient Node<E> first;
 
    transient Node<E> last;
 
    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;
        }
    }
 
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
 
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
        modCount++;
    }
 
    public E remove() {
        return removeFirst();
    }
 
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null) {
            throw new NoSuchElementException();
        }
        return unlinkFirst(f);
    }
 
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null) {
            last = null;
        } else {
            next.prev = null;
        }
        size--;
        modCount++;
        return element;
    }
}

七、ArrayList和LinkedList比较（P517）

（1）如果我们改查的操作多，选择 ArrayList。
（2）如果我们增删的操作多，选择 LinkedList。
（3）一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择 ArrayList。