1、ArrayList是基于数组，LinkedList是基于链表
2、基于数组的ArrayList对于根据索引值查找比较高效；基于链表的LinkedList对于增加、删除操作比较高效
3、剖析CRUD：
ArrayList：
add：
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!!：size默认为0 elementData[size++] = e; return true; }
private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
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、首先判断elementData是否是空元素，调用grow方法设置默认长度为10的空数组：10/15/22
2、然后判断size+1和elementData长度比较，若增加之后的size大于elementData长度，则进行动态增加数组elementData长度
3、数组长度增加策略：对原来elementData长度进行oldCapacity + (oldCapacity >> 1)相当于elementData长度的1.5倍，然后用这个1.5倍与增加之后元素的个数比较，哪个大用哪个
4、然后进行数组elementData 的复制，长度采用上一步比较的数字
获取元素get：
public E get(int index) { rangeCheck(index); return elementData(index); }
首先要调用size方法获取到集合的长度，不然当获取的元素下标大于集合的长度时会报错
private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
E elementData(int index) { return (E) elementData[index]; }
因为是基于数组，所以查询根据索引值可直接获取
设置元素set：
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }
E elementData(int index) { return (E) elementData[index]; }
首先定义数组变量，然后给该变量设置内容
remove移除方法：
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; }
思路：
1、根据索引值，进行数组拷贝，把index之后的元素向前挪动1
2、size-1索引的地方设为null，垃圾自动回收
3、返回值为第几个元素，例如index为1则返回2
LinkedList
add：
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++; }
Node节点就是个含有头指针、存储元素、尾指针的双向链表
单向链表和双向链表有什么区别？各自有什么优缺点？
单向链表：从头指向尾一条线
双向链表：比单向链表多了一个下一节点指向上一节点的头指针
单链表只能单向读取，双向链表可以通过prev()快速return找到前一结点
单向链表优缺点：
1、优点：单向链表增加删除节点简单。遍历时候不会死循环
2、缺点：只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进
双向链表优缺点：
1、优点：可以找到前驱和后继，可进可退
2、缺点：增加删除节点复杂，多需要分配一个指针存储空间
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; } }
节点相连类似于对象里面套对象
思路：
1、判断如果该节点为null，设置为头节点
2、如果该节点不为null，设置到上个节点的next节点
remove方法：
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }
private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
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; }
链表删除操作：
1、将需要删除的prev节点next指向需要删除的next节点
2、将需要删除的next节点prev指向需要删除的prev节点
get方法：
public E get(int index) { checkElementIndex(index); return node(index).item; }
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; } }
思路：若索引值小于链表长度的1/2，则在前半部查询，反之，则在后半部查询
set方法：
public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; }
先查再改，耗时主要在查
