ArrayList，LinkedList和Vector

ArrayList与LinkedList的区别

1. ArrayList底层是由数组实现的，它查找效率高，支持随机访问，通过下标返回元素。增删速度较慢，需要移动其他元素的下标；
2. LinkedList底层是由双向链表（实现了Deque,一个表示双端队列的接口）实现的，查询效率比ArrayLIst低一点，因为它需要遍历链表节点来访问，增删效率较高，只需要更改节点的前后引用指针即可，另外LinkedList内存占用更多，因为它不仅存储元素本身，还要存储前后引用指针。

综合来说，在需要频繁读取集合中的元素时，更推荐使用ArrayList，而在插入和删除操作较多时，更推荐使用LinkedList。

---

ArrayList的初始化原理

默认的初始化容量为10，当元素数量超过数组容量时会触发扩容，每次扩容，容量会变成原数组的1.5倍，然后将原数组的内容拷贝到新数组中，完成扩容操作。

private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth 一般是1*/
                    oldCapacity >> 1           /* preferred growth */);//old右移一位即除以2
            return elementData = Arrays.copyOf(elementData, newCapacity);//newCapacity是old的1.5倍
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
            //如果是DEFAULTCAPACITY_EMPTY_ELEMENTDATA（初始化未指定容量），第一次扩容为DEFAULT_CAPACITY（10）
        }
}

private Object[] grow() {
    return grow(size + 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

如果创建空的 ArrayList 和 Vector即不指定 initialCapacity 大小,它的底层数组其实是空的，没有申请空间，当第一次向 ArrayList 集合中添加元素时，底层数组扩容到10.
当使用带参的构造方法，会直接申请参数大小的容量。

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

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

ArrayList 和 Vector 类封装了一个动态的, 允许再分配的 Object[] 数组. 如果一开始就知道 ArrayList 和 Vector 需要保存多少个元素, 则可以在创建它们时就指定 initialCapacity 大小，可以减少需要频繁扩容消耗的时间.

---

ArrayList和Vector有异同点

ArrayList和Vector在很多时候都很类似。

1. 两者都是基于索引的，内部由一个数组支持。
2. ArrayList和Vector两者允许null值，也可以使用索引值对元素进行随机访问。
3. 都继承自AbstractList，都实现List, RandomAccess, Cloneable, java.io.Serializable

以下是ArrayList和Vector的不同点。

1. Vector 是同步的，而ArrayList不是。 然而，如果你寻求在迭代的时候对列表进行改变，你应该使用CopyOnWriteArrayList。
2. ArrayList更加通用是因为我们可以使用Collections工具类轻易地获取同步List。

List<Integer> objects = Collections.synchronizedList(new ArrayList<Integer>());
------------------------------------------------------------------------------------
public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new SynchronizedRandomAccessList<>(list) :
            new SynchronizedList<>(list));
}
------------------------------------------------------------------------------------
static class SynchronizedList<E>
        extends SynchronizedCollection<E>
        implements List<E> {//扩展了功能，让不支持同步的List类有了有了同步方法，装饰者模式
        @java.io.Serial
        private static final long serialVersionUID = -7754090372962971524L;

        @SuppressWarnings("serial") // Conditionally serializable
        final List<E> list;

        SynchronizedList(List<E> list) {
            super(list);
            this.list = list;
        }
        SynchronizedList(List<E> list, Object mutex) {
            super(list, mutex);
            this.list = list;
        }
        //举例方法
        public E set(int index, E element) {
            synchronized (mutex) {return list.set(index, element);}
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3. 初始化，vector不指定容量初始化会直接分配10个空间，而ArrayList会在第一次增加元素的时候分配

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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5. 扩容：ArrayList扩容原有初始容量的50%，而Vector扩容原有初始容量的100%，当然是前提是创建Vector对象时没有设定他的扩容大小。即没有使用他的需要设定初始大小，和扩容大小的构造函数。

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = ArraysSupport.newLength(oldCapacity,
            minCapacity - oldCapacity, /* minimum growth 一般是1*/
            capacityIncrement > 0 ? capacityIncrement : oldCapacity
                                       /* preferred growth */);
    return elementData = Arrays.copyOf(elementData, newCapacity);
    //capacityIncrement 在构造方法中指定
}
private Object[] grow() {
	return grow(elementCount + 1);
}
1
2
3
4
5
6
7
8
9
10
11
12