List与Set

List集合是Collection集合的子接口，其中的元素有序，并且可重复，元素可以通过下标访问。

接囗特有且常用的方法

1.add(int index, E element)

void add(int index, E element);

将指定的数据element存储到集合的指定索引index位置上。如果这个索引上存有元素就把原有的元素和随后的元素向右移动1位（在它们索引上加一），再将存储element

该方法会进行范围检查，如果不在这个范围的会报：java.lang.IndexOutOfBoundsException异常

2.get(int index)

E get(int index);

获取集合中指定索引上的元素

该方法会进行范围检查，如果不在这个范围的会报：java.lang.IndexOutOfBoundsException异常

3.indexOf(Object o)

int indexOf(Object o);

返回指定元素在这个列表中第一次出现的索引，如果这个列表不包含该元素，则返回-1

4.lastIndexOf(Object o)

int lastIndexOf(Object o);

返回指定元素在这个列表中最后出现的索引，如果这个列表不包含该元素，则返回-1。

5.remove(int index)

E remove(int index);

删除集合中指定索引处的元素，并将后面的元素向左移动（从它们的索引中减一）

返回被删除的元素

6.set(int index, E element)

E set(int index, E element);

用指定的元素替换这个列表中指定位置的元素

ArrayList

---

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access

其底层采用了数组数据结构，其默认容量是10

构造方法

ArrayList有两种初始化

//面向接口
//默认容量10
List list = new ArrayList();
//自定义集合容量20
Lsit list1 = new ArrayList(20);

使用无参构造，底层会先给赋一个长度为0的数组，在添加第一个元素时，再把容量设为10

扩容

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);
}

一般情况下，如果新增加的元素下标超出原有的容量，则扩容到原容量的1.5倍。elementData会指向这个新数组，旧数组会被回收。

如果新容量减去最小容量小于0，则最终扩容的容量为最小容量

Q：建议尽可能减少扩容，因为数组的扩容效率较低

增删元素

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    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

    return oldValue;
}

由源码可知，ArrayList在向某个索引增加或删除元素时底层会调用System.arraycopy，而这一操作极为消耗资源

在涉及到频繁插入和删除元素的情况下，LinkedList是首选，因为它只需要添加或删除节点，并重新链接现有的节点。

优缺点

优点：ArrayList底层是数组，元素间的内存地址是相连的，其检索效率高，向末尾添加元素效率也高。

而日常工作最常用到的是向末尾添加元素。

缺点：随机增删元素效率低，且消费高；数组不适合存储大数据，因为内存空间没有很大的一块地方分配给它

[Data Analytics]

链表

---

链表的基本单元是节点：Node

单向链表

对于单向链表，任意的Node都有两个属性，一个是存储数据，另一个则存储的是下一节点的内存地址

其中最后一个节后存储内存地址的部分指向空值（null）

链表中各节点内存地址并不连续，要寻找某个元素时，要从头节点开始查，靠上一节点内部的属性记录下一节点的内存地址。

随机增删元素不会涉及大量节点位移。删除或增加某个节点时，上一节点要重新记录下一节点的内存地址

双向链表

与单向链表相似，不过Node还多了一个存储上一节点内存地址的属性

在删除或增加某个节点时，上一节点要重新记录下一节点的内存地址，下一节点也要记录上一节点的内存地址

LinkedList

transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

底层采用双向链表存储数据，first、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;
    }
}

内部类Node，用于存储节点信息

初始化

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

无论使用哪种构造，都会调用无参构造

在LinkedList类中，并未对链表的容量作说明，而从构造方法可以看出LinkedList是一个无界限的链表，可以不限容量存储

方法

1.添加元素

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++;
}

add方法向尾部添加元素。

首先方法内部对象 l 会保存链表尾部节点，然后创建新节点，将新节点的 prev 节点信息关联到链表当前的尾节点，并把新节点的 next 节点赋值null。再将新创的节点newNode更新为链表的尾部节点 last 。再对内部变量 l 做非空引用判断，如果对象 l 引用为空，则表示当前链表中没有节点，把首节点 first 也更新为newNode；如果对象 l 引用不为空，则把newNode节点与对象 l 指向节点的next属性关联。最后再把节点个数加1，集合修改次数加1

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

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;
    }
}

向指定索引添加节点。

与上面的add方法基本一致，不同的是要让索引index的上一节点与下一节点重新关联新的节点

2.删除节点

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

删除元素为 o 的节点

要先对链表遍历，因为LinkedList可以存储null值，所以需要进行null判断。判断这个节点是不是首尾节点，让上一节点的next属性与 x 节点的next关联，或让下一节点的pre属性与 x 节点的pre关联，将x的next 、 prev 、 item设为null。因为 x 节点没有被使用，后面会被垃圾回收器回收

3.更新节点数据

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

更新指定节点存储的元素

4.是否包含元素

public boolean contains(Object o) {
    return indexOf(o) != -1;
}

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

判断元素是否存在于链表中

特有方法

1.获取首或尾节点元素

public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

返回首节点或尾节点存储的元素

优缺点

因为节点的内存地址不连续，随机增删元素不会导致大量的元素产生空间位移，随机增删元素效率高。但不能通过数学表达式查找元素的内存地址，每次查找元素都要去遍历链表，检索效率低

Vector

---

/**
 * The array buffer into which the components of the vector are
 * stored. The capacity of the vector is the length of this array buffer,
 * and is at least large enough to contain all the vector's elements.
 *
 * <p>Any array elements following the last element in the Vector are null.
 *
 * @serial
 */
protected Object[] elementData;

/**
 * The number of valid components in this {@code Vector} object.
 * Components {@code elementData[0]} through
 * {@code elementData[elementCount-1]} are the actual items.
 *
 * @serial
 */
protected int elementCount;

/**
 * The amount by which the capacity of the vector is automatically
 * incremented when its size becomes greater than its capacity.  If
 * the capacity increment is less than or equal to zero, the capacity
 * of the vector is doubled each time it needs to grow.
 *
 * @serial
 */
protected int capacityIncrement;

和ArrayList一样，其底层也是数组；elementCount是记录这个数组的有效元素个数；capacityIncrement是每次扩容的大小，如果容量增量小于或等于零，每次需要增长时，向量的容量就会增加一倍。

构造方造

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 Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector() {
    this(10);
}

从其底层的构造方法可以看出，默认的数组长度为10。

扩容

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;  //10
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

如果在初始化时没有对 capacityIncrement 赋值，那其默认的扩容容量是原容量的两倍

线程安全

Vector中所有的方法都有synchronized线程同步，是线程安全的

在java.util下还有个Collections集合工具类，其中有synchronizedList()方法，可以把List接口下的非线程安全集合转换成线程安全的

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new SynchronizedRandomAccessList<>(list) :
            new SynchronizedList<>(list));
}

返回一个由指定列表支持的同步（线程安全）的列表

当用户在返回的列表上进行迭代时，必须对其进行手动同步，否则可能会导致非确定性的行为，例：

List list = Collections.synchronizedList(new ArrayList))。
            ...
synchronized (list) {
	Iterator i = list.iterator(); // 必须在同步块中进行
	while (i.hasNext())
		foo(i.next())
}

Set

---

其元素无序、不可重复

Set接口的方法基本与Collection一致。由于元素无序，Set中元素没有下标，所以没有set和get、index等从索引上访问元素的方法

与List集合一样可以通过迭代器或forEach、for循环完成遍历