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有两种初始化

//面向接口//默认容量10List list = new ArrayList();//自定义集合容量20Lsit 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循环完成遍历