List
ArrayList
ArrayList的subList方法会返回一个list视图，对这个SubList的修改都会映射到原来的list
而Arrays.asList返回的arrays包下的ArrayList，这个类并没有重写add,remove等方法，所以修改时会抛出异常
结构
- DEFAULT_CAPACITY 表示数组的初始大小，默认是 10
- size 表示当前数组的大小
- modCount 统计当前数组被修改的版本次数，数组结构有变动，就会 +1
解析
- 初始化
一共有三种方式可以初始化ArrayList
public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // 直接将传入的集合转成数组复制给内部数组 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { this.elementData = {}; }}public ArrayList() { this.elementData = {};}public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = {}; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}- 新增与扩容
添加元素时：
- 判断是否需要扩展，如果需要则只需扩容
- 添加
// 这个版本是基于JDK13的private void add(E e, Object[] elementData, int s) { // 当发现现在list的size跟数组容量一样大时，则进行扩容 if (s == elementData.length) // 这里扩容完，会产生一个新数组，我们要将新数组保存 elementData = grow(size+1); //添加index:size elementData[s] = e; size = s + 1;}// 扩容核心代码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 */ oldCapacity >> 1 /* preferred growth */); // 复制老数组到新数组 return elementData = Arrays.copyOf(elementData, newCapacity); } else { return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; }}// 计算容量的方法public static int newLength(int oldLength, int minGrowth, int prefGrowth) { // 判断list的size与elementData的差值如果大于elementData长度的一半 // 新数组长度就等于老数组长度加上list的size与elementData的差值 // 否则新数组的长度就等于老数组的1.5倍 int newLength = Math.max(minGrowth, prefGrowth) + oldLength; if (newLength - MAX_ARRAY_LENGTH <= 0) { // 数组长度不能大于整数最大值 return newLength; } return hugeLength(oldLength, minGrowth);}所以扩容的本质就是申请一个更大的数组，将旧数组的内容移过去
源码扩容过程值得借鉴的地方
通过自动扩容的方式，让使用者不用关心底层数据结构的变化，封装得很好
1.5 倍的扩容速度，可以让扩容速度在前期缓慢上升，在后期增速较快
扩容过程中，注意数组大小溢出的情况
删除
无论是根据Object删除还是index删除，都必须给出被删除元素的index
private void fastRemove(Object[] es, int i) { modCount++; final int newSize; if ((newSize = size - 1) > i) // 将elementData 下标为i后面的全部元素往前移动一个位 System.arraycopy(es, i + 1, es, i, newSize - i); // 如果删除的是最后一个元素，置为null就行 es[size = newSize] = null; // 同时记得size-1}迭代器
- hasNext
public boolean hasNext() { return cursor != size;}- next
public E next() { // 有点乐观锁的意思，通过版本号来确定持有的数据是否被修改了 if (modCount != expectedModCount) throw new ConcurrentModificationException(); // 否则每次根据游标获取元素，获取完游标+1 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];}- remove
public void remove() { if (lastRet < 0) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); // 将当前游标作为下标，删除这个位置的元素 try { ArrayList.this.remove(lastRet); // 删除完之后要更新版本号 cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }}线程安全
ArrayList 有线程安全问题的本质，是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时，都没有加锁
问：对 ArrayList 的理解？
答：底层数据结构、对数组的封装、add、remove
问：为什么说扩容会消耗性能
答：扩容底层使用的是 System.arraycopy 方法，会把原数组的数据全部拷贝到新数组上，所以性能消耗比较严重
LinkedList
架构
LinkedList 底层数据结构是一个双向链表
解析
- node的结构
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; }}- 尾部追加节点
void linkLast(E e) { final Node<E> l = this.last; final Node<E> newNode = new Node<>(l, e, null); this.last = newNode; // 如果尾节点为空，则代表当前链表是空的，直接把插入节点作为头节点 if (l == null) first = newNode; else l.next = newNode; // 否则就将插入节点设置为尾节点，并且把旧尾节点的next指向插入节点 size++; modCount++;}- 头部追加节点
private void linkFirst(E e) { final Node<E> f = this.first; final Node<E> newNode = new Node<>(null, e, f); this.first = newNode; // 如果头节点为空，则代表当前链表是空的，直接把插入节点作为尾节点 if (f == null) last = newNode; else f.prev = newNode; // 否则就将插入节点设置为头节点，并且把旧头节点的prev指向插入节点 size++; modCount++;}- 删除节点
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; // 当前删除的是头节点，所以将删除节点的next变为头节点 if (prev == null) { first = next; } else { // 否则设置删除节点的上一个节点的next指向删除节点的next prev.next = next; x.prev = null; } // 当前删除的是尾节点，所以将删除节点的prev变为尾节点 if (next == null) { last = prev; } else { // 否则设置删除节点的下一个节点的prev指向删除节点的prev next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element;}- 根据下标查询节点
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; }}迭代器
// 双向迭代器private class ListItr implements ListIterator<E> { private Node<E> lastReturned;//上一次执行 next() 或者 previos() 方法时的节点位置 private Node<E> next;//下一个节点 private int nextIndex;//下一个节点的位置 …………}- 从头到尾迭代
public boolean hasNext() { return nextIndex < size;} public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; // next指向当前遍历元素的next nextIndex++; return lastReturned.item;}- 从尾到头迭代
public boolean hasPrevious() { return nextIndex > 0;}public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); // 主要是判断next为空的情况下要选择last作为遍历节点，否则选择遍历元素的prev lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item;}- 删除
public void remove() { checkForComodification(); // lastReturned 是本次迭代需要删除的值，分以下空和非空两种情况： // lastReturned 为空，说明调用者没有主动执行过 next() 或者 previos()，直接报错 // lastReturned 不为空，是在上次执行 next() 或者 previos()方法时赋的值 if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; //删除当前节点 unlink(lastReturned); // next == lastReturned 的场景分析：从尾到头递归顺序，并且是第一次迭代，并且要删除最后一个元素的情况下 // 这种情况下，previous() 方法里面设置了 lastReturned = next = last,所以 next 和 lastReturned会相等 if (next == lastReturned) // 这时候 lastReturned 是尾节点，lastNext 是 null，所以 next 也是 null，这样在 previous() 执行时，发现 next 是 null，就会把尾节点赋值给 next next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++;}问：ArrayList 和 LinkedList 有何不同
答：底层数据结构，数组结构导致的读写差异
问： ArrayList 和 LinkedList 应用场景
答：ArrayList 更适合于快速的查找匹配，不适合频繁新增删除，像工作中经常会对元素进行匹配查询的场景比较合适，LinkedList 更适合于经常新增和删除，对查询反而很少的场景
问：ArrayList 和 LinkedList 两者有没有最大容量
答：两个都有最大容量，是int的最大值，原因是ArrayList使用的数组容量不能超过int最大值，LinkedList则是因为size使用int表示的，所以也不能超过int的最大值
问：ArrayList 和 LinkedList 是如何对 null 值进行处理的
答：ArrayList 允许 null 值新增，也允许 null 值删除。删除 null 值时，是从头开始，找到第一值是 null 的元素删除；LinkedList 新增删除时对 null 值没有特殊校验，是允许新增和删除的
问：ArrayList 和 LinedList 是线程安全的么，为什么
答：都非线程安全，主要的问题点在于多线程环境下，所有线程任何时刻都可对数组和链表进行操作，这会导致值被覆盖，甚至混乱的情况