1. ArrayList
ArrayList是最最罕用的汇合类了，真的没有之一。上面的剖析是基于1.8.0_261源码进行剖析的。
1.1 ArrayList特点介绍
动静数组，应用的时候，只须要操作即可，外部曾经实现扩容机制。
- 线程不平安
- 有程序，会依照增加进去的程序排好
- 基于数组实现，随机访问速度快，插入和删除较慢一点
- 能够插入null元素，且能够反复
1.2 实现的接口和继承的类
首先，咱们看看ArrayList实现的类和继承的类：
class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.SerializableArrayList 继承了AbstractList接口，实现了List，以及随机拜访，可克隆，序列化接口。不是线程平安的，如果须要线程平安，则须要抉择其余的类或者应用Collections.synchronizedList(arrayList)
容许存储null元素，也容许雷同的元素存在。
其底层实际上是数组实现的，那为什么咱们应用的时候只管往里面存货色，不必关怀其大小呢？因为ArrayList封装了这样的性能，容量能够动静按需变动，不须要使用者关怀。扩容之后不会主动放大容量。
2. 成员变量
elementData是真正存储数据元素的中央，transient示意这个属性不须要主动序列化。
对于下面的transient,找到一个靠谱的说法：
在ArrayList中的elementData这个数组的长度是变长的,java在扩容的时候,有一个扩容因子,也就是说这个数组的长度是大于等于ArrayList的长度的,咱们不心愿在序列化的时候将其中的空元素也序列化到磁盘中去,所以须要手动的序列化数组对象,所以应用了transient来禁止主动序列化这个数组。
// 真正存取数据的数组 transient Object[] elementData; // 理论元素个数(不是elementData的大小，是具体寄存的元素的数量) private int size;那在哪里去实现对西那个的序列化和反序列化的呢？
这个须要咱们看源码外面的readOject()和writeOject()两个办法。其实就除了默认的序列化其余字段，这个elementData字段，还须要手动序列化和反序列化。
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ // 序列之前须要保留本来的批改的次数，序列化的过程中不容许新批改 int expectedModCount = modCount; // 将以后类的非动态和非transient的字段写到流中，其实就是默认的序列化 s.defaultWriteObject(); // 将大小写到输入流中 s.writeInt(size); // 依照程序序列化外面的每一个元素，留神应用的是`writeOject()` for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } // 如果序列化期间有产生批改，就会抛出异样 if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } // 反序列化 private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA; // 读取默认的反序列化数据 s.defaultReadObject(); // 读取大小 s.readInt(); // ignored if (size > 0) { // 和clone()相似，依据size调配空间，而不是容量 int capacity = calculateCapacity(elementData, size); SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); ensureCapacityInternal(size); Object[] a = elementData; // 循环读取每一个元素 for (int i=0; i<size; i++) { a[i] = s.readObject(); } } }很多人可能会有疑难，为什么这个函数没有看到有调用呢？在哪里调用的呢？
其实就是在对象流中，通过反射的形式进行调用的，如果有本人的实现，就会调用到这里的实现，这里就不开展了，下次肯定！！！有趣味能够看看。
如果咱们创立的时候不指定大小，那么就会初始化一个默认大小为10,DEFAULT_CAPACITY就是默认大小。
private static final int DEFAULT_CAPACITY = 10;外面定义了两个空数组，EMPTY_ELEMENTDATA名为空数组,DEFAULTCAPACITY_EMPTY_ELEMENTDATA名为默认大小空数组,用来辨别是空构造函数还是带参数构造函数结构的ArrayList,第一次增加元素的时候应用不同的扩容形式。
之所以是一个空数组，不是null，是因为应用的时候咱们须要制订参数的类型，如果是null，那就基本不晓得元素类型是什么了。
private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};还有一个非凡的成员变量modCount，这是疾速失败机制所须要的，也就是记录批改操作的次数，次要是迭代遍历的时候，避免元素被批改。如果操作前后的批改次数对不上，那么有些操作就是非法的。transient示意这个属性不须要主动序列化。
protected transient int modCount = 0;序列化idserialVersionUID如下：
为什么须要这个字段呢？这是因为如果没有显示申明这个字段，那么序列化的时候回主动生成一个序列化的id，写到序列化文件中去，这样子的话，假如序列化实现之后，往原来的类外面增加了一个字段，那么这个时候反序列化会失败，因为默认的序列化id曾经扭转了。假如咱们给它指定了序列化id的话，就能够防止这种问题，只是减少的字段反序列化的时候是空的。
private static final long serialVersionUID = 8683452581122892189L;3. 构造方法
构造方法有三个，能够指定容量，能够指定初始的元素汇合，也能够什么都不指定。
// 指定初始化的大小 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); } } // 什么都不指定，默认是空的元素集 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } // 传入一个汇合，转成数组之后，复制一份作为显得数据集 public ArrayList(Collection<? extends E> c) { Object[] a = c.toArray(); if ((size = a.length) != 0) { if (c.getClass() == ArrayList.class) { elementData = a; } else { elementData = Arrays.copyOf(a, size, Object[].class); } } else { // replace with empty array. elementData = EMPTY_ELEMENTDATA; } }4. 罕用增删改查办法
增加元素
add()办法有两个：
add(E e)：增加一个元素，默认是在开端增加add(int index, E element)：在指定地位index增加(插入)一个元素
public boolean add(E e) { // 确定容量是不是足够，足够就不会减少 ensureCapacityInternal(size + 1); // size+1的中央，赋值为当初的e elementData[size++] = e; return true; } // 在指定的地位插入一个元素 public void add(int index, E element) { // 查看插入的地位，是否非法 rangeCheckForAdd(index); // 查看是不是须要扩容，容量是否足够 ensureCapacityInternal(size + 1); // Increments modCount!! // 复制index前面的元素，都往后面挪动一位（这是c++实现的底层原生办法） System.arraycopy(elementData, index, elementData, index + 1, size - index); // 在index处插入元素 elementData[index] = element; // 理论的存储元素个数减少 size++; } 查问元素
get()办法绝对比较简单，获取之前查看参数是否非法，就能够返回元素了。
public E get(int index) { // 查看下标 rangeCheck(index); return elementData(index); } // 查看下标 private void rangeCheck(int index) { if (index >= size) // 数组越界 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } 更新元素
set()和之前的get()有点像，然而必须制订批改的元素下标，查看下标之后，批改，而后返回旧的值。
public E set(int index, E element) { // 查看下标 rangeCheck(index); // 获取旧的值 E oldValue = elementData(index); // 批改元素 elementData[index] = element; // 返回旧的值 return oldValue; }删除元素
依照元素移除，或者依照下标移除元素
public E remove(int index) { // 查看下标 rangeCheck(index); // 批改次数扭转 modCount++; // 获取旧的元素 E oldValue = elementData(index); // 计算须要挪动的下标（往前面挪动一位） int numMoved = size - index - 1; if (numMoved > 0) // 调用native办法将前面的元素复制，挪动往前一步 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 将之前的元素置为空，让垃圾回收不便进行 elementData[--size] = null; // clear to let GC do its work return oldValue; } public boolean remove(Object o) { // 为空的元素 if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { // 遍历，如果equals,则调用删除 for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } // 疾速删除办法 private void fastRemove(int index) { // 批改次数减少1 modCount++; // 计算挪动的地位 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 }5.主动扩容和手动缩容机制
5.1 主动扩容
ArrayList是基于数组动静扩容的，那它什么时候扩容的呢？如同下面的源代码中咱们没有看到，其实是有的，所谓扩容嘛，就是容量不够了，那么容量不够的时候只会产生在初始化一个汇合的时候或者是减少元素的时候，所以是在add()办法外面去调用的。
在最小调用的时候容量不满足的时候，会调用grow()，grow()是真正扩容的函数，这里不开展了。
如果元素是默认初始haul的空数据，那么所须要的最小容量就是默认容量和最小容量比照，两者取最大，也就是忽然有退出有6个元素加到汇合中来，那么默认容量是10，会间接初始化为10，如果一下子有11个元素加进来，那么最小的容量应该取11。
// 计算所需最小容量 private static int calculateCapacity(Object[] elementData, int minCapacity) { // 如果元素是默认初始haul的空数据，那么所须要的最小容量就是默认容量和最小容量比照，两者取最大。 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } // 确保容量足够 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity(int minCapacity) { // 批改次数减少 modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) // 真正实现容量增长的函数 grow(minCapacity); }真正实现扩容的代码如下：
private void grow(int minCapacity) { // 获取旧的容量 int oldCapacity = elementData.length; // 新容量是翻了一倍 int newCapacity = oldCapacity + (oldCapacity >> 1); // 如果新的容量还是小于最小容量，则最新容量更新为最小容量 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果最新的容量大于最大的容量，则须要调用hugeCapacity函数将容量调小一点 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 底层是调用数组间接复制 elementData = Arrays.copyOf(elementData, newCapacity); }- 如果所需最小容量小于0，抛出异样
- 如果所需最小容量大于最大的容量，那么间接返回int类型的最大值作为容量
- 如果所需的最小容量小于等于最大容量，那么间接返回最大的容量。
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }如果须要手动扩容，其实也是有提供函数的,其参数是所须要的最小的容量，外部调用也是下面说的ensureExplicitCapacity函数。
public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } }5.2 手动扩容
手动缩容的函数绝对简略,批改次数减少，而后，将数组元素copy到新的数组中即可。
public void trimToSize() { // 批改次数减少 modCount++; // 只有实在应用的个数小于数组长度，都会缩容 if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }6. 其余函数
获取大小：
public int size() { return size; }判断是不是空集合：
public boolean isEmpty() { return size == 0; }是否蕴含某个对象：
public boolean contains(Object o) { return indexOf(o) >= 0; }返回对象的下标，从左到右遍历,分为object为null和非null来解决：
public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }放回对象最初呈现的下标，从右往左遍历：
public int lastIndexOf(Object o) { if (o == null) { // 为null的时候不能应用equals for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; }克隆ArrayList对象，先拷贝ArrayList，而后再把外部的数组也拷贝一份：
public Object clone() { try { // 调用默认的拷贝 ArrayList<?> v = (ArrayList<?>) super.clone(); // 将外部的数组也拷贝一份 v.elementData = Arrays.copyOf(elementData, size); // 批改次数只为0 v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }转化为数组，咱们看到外部其实是复制了一份援用，所以如果咱们批改数组外面的元素，也会批改到ArrayList元素的。
public Object[] toArray() { return Arrays.copyOf(elementData, size); }将元素拷贝到指定的数组中：
public <T> T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; }依据index索引地位获取迭代器地位：
public ListIterator<E> listIterator(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index); return new ListItr(index); } // 默认是在开始的地位 public ListIterator<E> listIterator() { return new ListItr(0); }截取一段，返回新的list,返回的是一个外部类SubList对象。
public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList(this, 0, fromIndex, toIndex); }遍历办法,其实就是lambda的形式进行调用，将行为参数化，将行为传进去，解决。
@Override public void forEach(Consumer<? super E> action) { Objects.requireNonNull(action); final int expectedModCount = modCount; @SuppressWarnings("unchecked") final E[] elementData = (E[]) this.elementData; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { action.accept(elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }依据条件移除元素，也是lambda表达式：
@Override public boolean removeIf(Predicate<? super E> filter) { Objects.requireNonNull(filter); // figure out which elements are to be removed // any exception thrown from the filter predicate at this stage // will leave the collection unmodified int removeCount = 0; final BitSet removeSet = new BitSet(size); final int expectedModCount = modCount; 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)) { removeSet.set(i); removeCount++; } } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } // shift surviving elements left over the spaces left by removed elements final boolean anyToRemove = removeCount > 0; if (anyToRemove) { final int newSize = size - removeCount; for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { i = removeSet.nextClearBit(i); elementData[j] = elementData[i]; } for (int k=newSize; k < size; k++) { elementData[k] = null; // Let gc do its work } this.size = newSize; if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; } return anyToRemove; } // 替换所有 public void replaceAll(UnaryOperator<E> operator) { Objects.requireNonNull(operator); final int expectedModCount = modCount; final int size = this.size; for (int i=0; modCount == expectedModCount && i < size; i++) { elementData[i] = operator.apply((E) elementData[i]); } if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; }排序，lambda表达式：
public void sort(Comparator<? super E> c) { final int expectedModCount = modCount; Arrays.sort((E[]) elementData, 0, size, c); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; }7. 迭代器
源码中一共定义了三个迭代器：
Itr:实现了Iterator接口，是AbstractList.Itr的优化版本。ListItr:继承了Itr,实现了ListIterator，是AbstractList.ListItr优化版本。ArrayListSpliterator:继承于Spliterator,Java 8 新增的迭代器，基于索引，二分的，懒加载器。
7.1 Itr
Itr这是一个比拟高级的迭代器，实现了Iterator接口，有判断是否有下一个元素，拜访下一个元素，删除元素的办法以及遍历对每一个元素解决的办法。
外面有两个比拟重要的属性：
- cursor：下一个行将拜访的元素下标
- lastRet：上一个返回的元素下标，初始化为-1
两个重要的办法：
- next():获取下一个元素
- remove():移除以后元素，须要在next()办法调用之后，能力调用，要不会报错。
private class Itr implements Iterator<E> { // 下一个返回元素的下标 int cursor; // 上一个返回元素的下标，初始化为-1 int lastRet = -1; int expectedModCount = modCount; // 无参结构 Itr() {} public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { // 查看是否被批改 checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; // 批改上一个返回元素的下标，返回该地位的值 return (E) elementData[lastRet = i]; } public void remove() { // 如果在调用next之前，调用了remove办法，此时的lastRet就是-1，就是非法的。 if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { // 调用数组的remove办法 ArrayList.this.remove(lastRet); // remove的是lastRet地位的元素，那么cursor（下一个行将返回的元素下标地位）就相当于往前面挪动了一位，因为之前的lastRet地位的元素被删除了，前面所有元素都往前面挪动了一位 cursor = lastRet; // 上一个返回的元素下标没有意义了，曾经被删除了，间接置为-1 lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } // 对外面的每一个元素进行解决 @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic cursor = i; lastRet = i - 1; checkForComodification(); } // 查看过程中是否被批改 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }7.2 ListItr
继承了Itr,实现了ListIterator，次要减少的性能有：
- 依据index获取该地位的迭代器
- 判断是否有后面的元素
- 获取下一个返回元素的下标
- 获取上一个返回元素的上面
- 获取上一个元素
- 更新元素
- 减少元素
总结来说，就是在Itr的根底上，减少了更多的性能。
private class ListItr extends Itr implements ListIterator<E> { // 依据index获取该地位的迭代器 ListItr(int index) { super(); cursor = index; } // 判断是否有后面的元素 public boolean hasPrevious() { return cursor != 0; } // 获取下一个返回元素的下标 public int nextIndex() { return cursor; } // 获取上一个返回元素的上面 public int previousIndex() { return cursor - 1; } // 获取上一个元素 @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[lastRet = i]; } // 更新元素 public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { // 更新元素 ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } // 减少元素 public void add(E e) { // 查看是否被更改 checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); // 插入元素后，下一个元素的下标递增1 cursor = i + 1; // 上一个元素为-1 lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }7.3 ArrayListSpliterator
间接看源码，这是一个用来适应多线程并行迭代的迭代器，能够将汇合分成多端，进行解决，每一个线程执行一段，那么就不会互相烦扰，它能够做到线程平安。
static final class ArrayListSpliterator<E> implements Spliterator<E> { // 寄存ArrayList对象， private final ArrayList<E> list; // 以后地位 private int index; // 完结地位,-1示意最初一个元素 private int fence; // 期待的批改次数，用于比拟是不是被批改了 private int expectedModCount; // initialized when fence set /** Create new spliterator covering the given range */ ArrayListSpliterator(ArrayList<E> list, int origin, int fence, int expectedModCount) { this.list = list; // OK if null unless traversed this.index = origin; this.fence = fence; this.expectedModCount = expectedModCount; } private int getFence() { // initialize fence to size on first use int hi; // (a specialized variant appears in method forEach) ArrayList<E> lst; if ((hi = fence) < 0) { if ((lst = list) == null) hi = fence = 0; else { expectedModCount = lst.modCount; hi = fence = lst.size; } } return hi; } // 宰割ArrayList，每调用一次，将原来的迭代器等分为两份，并返回索引靠前的那一个子迭代器。 public ArrayListSpliterator<E> trySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid) ? null : // divide range in half unless too small new ArrayListSpliterator<E>(list, lo, index = mid, expectedModCount); } // 返回true时，示意可能还有元素未解决 // 返回falsa时，没有残余元素解决了 public boolean tryAdvance(Consumer<? super E> action) { if (action == null) throw new NullPointerException(); int hi = getFence(), i = index; if (i < hi) { index = i + 1; @SuppressWarnings("unchecked") E e = (E)list.elementData[i]; action.accept(e); if (list.modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } return false; } // 遍历解决剩下的元素 public void forEachRemaining(Consumer<? super E> action) { int i, hi, mc; // hoist accesses and checks from loop ArrayList<E> lst; Object[] a; if (action == null) throw new NullPointerException(); if ((lst = list) != null && (a = lst.elementData) != null) { if ((hi = fence) < 0) { mc = lst.modCount; hi = lst.size; } else mc = expectedModCount; if ((i = index) >= 0 && (index = hi) <= a.length) { for (; i < hi; ++i) { @SuppressWarnings("unchecked") E e = (E) a[i]; action.accept(e); } if (lst.modCount == mc) return; } } throw new ConcurrentModificationException(); } // 估算大小 public long estimateSize() { return (long) (getFence() - index); } // 返回特征值 public int characteristics() { return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; } }以上三种迭代器，各有千秋，Itr性能比较简单，提供了罕用的性能，ListItr，提供了双向遍历和更新，插入等操作，而ArrayListSpliterator则是专一于切分迭代。应用的时候按需应用即可。
8. 小结一下
- ArrayList是基于动静数组实现的，减少元素的时候，可能会触发扩容操作。扩容之后会触发数组的拷贝复制。remove操作也会触发复制，前面的元素对立往前面挪一位，原先最初面的元素会置空，这样能够不便垃圾回收。
- 默认的初始化容量是10，容量不够的时候，扩容时候减少为原先容量的个别，也就是原来的1.5倍。
- 线程不平安，然而元素能够反复，而且能够放null值，这个须要留神一下，每次取出来的时候是须要判断是不是为空。
- 查问效率比拟高，因为底层是数组，然而插入和删除操作，老本绝对高一点。
【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使迟缓，驰而不息。这个世界心愿所有都很快，更快，然而我心愿本人能走好每一步，写好每一篇文章，期待和你们一起交换。
此文章仅代表本人（本菜鸟）学习积攒记录，或者学习笔记，如有侵权，请分割作者核实删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有谬误之处，还望指出，感激不尽~