说一下 ArrayList 和 LinkedList 的区别？

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    // 疑问 1：为什么字段都不声明 private 关键字？
    // 疑问 2：为什么字段都声明 transient 关键字？
    // 元素个数
    transient int size = 0;

    // 头指针
    transient Node<E> first;

    // 尾指针
    transient Node<E> last;

    // 链表节点
    private static class Node<E> {
        // 节点数据
        // （类型擦除后：Object item;）
        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;
        }
    }
}

// 无参构造方法
public LinkedList() {
}

// 带集合的构造方法
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

// 在链表尾部添加集合
public boolean addAll(Collection<? extends E> c) {
    // 索引为 size，等于在链表尾部添加
    return addAll(size, c);
}

public void addFirst(E e) {
    linkFirst(e);
}

public void addLast(E e) {
    linkLast(e);
}

public boolean add(E e) {
    linkLast(e);
    return true;
}

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        // 在尾部添加
        linkLast(element);
    else
        // 在指定位置添加
        linkBefore(element, node(index));
}

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

// 在链表头部添加
private void linkFirst(E e) {
    // 1. 找到插入位置的后继节点（first）
    final Node<E> f = first;
    // 2. 构造新节点
    // 3. 将新节点的 prev 指针指向前驱节点（null）
    // 4. 将新节点的 next 指针指向后继节点（f）
    // 5. 将前驱节点的 next 指针指向新节点（前驱节点是 null，所以没有这个步骤）
    final Node<E> newNode = new Node<>(null, e, f);
    // 修改 first 指针
    first = newNode;
    if (f == null)
        // f 为 null 说明首个添加的元素，需要修改 last 指针
        last = newNode;
    else
        // 6. 将后继节点的 prev 指针指向新节点
        f.prev = newNode;
    size++;
    modCount++;
}

// 在链表尾部添加
void linkLast(E e) {
    final Node<E> l = last;
    // 1. 找到插入位置的后继节点（null）
    // 2. 构造新节点
    // 3. 将新节点的 prev 指针指向前驱节点（l）
    // 4. 将新节点的 next 指针指向后继节点（null）
    final Node<E> newNode = new Node<>(l, e, null);
    // 修改 last 指针
    last = newNode;
    if (l == null)
        // l 为 null 说明首个添加的元素，需要修改 first 指针
        first = newNode;
    else
        // 5. 将前驱节点的 next 指针指向新节点
        l.next = newNode;
    // 6. 将后继节点的 prev 指针指向新节点（后继节点是 null，所以没有这个步骤）
    size++;
    modCount++;
}

// 在指定节点前添加
// 1. 找到插入位置的后继节点
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    // 2. 构造新节点
    // 3. 将新节点的 prev 指针指向前驱节点（pred）
    // 4. 将新节点的 next 指针指向后继节点（succ）
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        // 5. 将前驱节点的 next 指针指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}

// 在指定位置添加整个集合元素
// index 为 0：在链表头部添加
// index 为 size：在链表尾部添加
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    // 事实上，c.toArray() 的实际类型不一定是 Object[]，有可能是 String[] 等
    // 不过，我们是通过 Node中的item 承接的，所以不用担心 ArrayList 中的 ArrayStoreException 问题
    Object[] a = c.toArray();
    // 添加的数组为空，跳过
    int numNew = a.length;
    if (numNew == 0)
        return false;

    // 1. 找到插入位置的后继节点
    // pred：插入位置的前驱节点
    // succ：插入位置的后继节点
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // 找到 index 位置原本的节点，插入后变成后继节点
        succ = node(index);
        pred = succ.prev;
    }
    // 插入集合元素
    for (Object o : a) {
        E e = (E) o;
        // 2. 构造新节点
        // 3. 将新节点的 prev 指针指向前驱节点
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            // pred 为 null 说明是在头部插入，需要修改 first 指针
            first = newNode;
        else
            // 5. 将前驱节点的 next 指针指向新节点
            pred.next = newNode;
        // 修改前驱指针
        pred = newNode;
    }

    if (succ == null) {
        // succ 为 null 说明是在尾部插入，需要修改 last 指针
        last = pred;
    } else {
        // 4. 将新节点的 next 指针指向后继节点
        pred.next = succ;
        // 6. 将后继节点的 prev 指针指向新节点
        succ.prev = pred;
    }
    // 数量增加 numNew
    size += numNew;
    modCount++;
    return true;
}

// 将 LinkedList 转化为 Object 数组
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

// 寻找指定位置的节点，时间复杂度：O(n)
Node<E> node(int index) {
    if (index < (size >> 1)) {
        // 如果索引位置小于 size/2，则从头节点开始找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 如果索引位置大于 size/2，则从尾节点开始找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

// 删除头部元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

// 删除尾部元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

// 删除指定元素
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

// 非静态内部类
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    // 创建迭代器时会记录外部类的 modCount
    private int expectedModCount = modCount;

    ListItr(int index) {
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public E next() {
        // 更新 expectedModCount
        checkForComodification();
        ...
    }
    ...
}

// 序列化和反序列化只考虑有效数据

// 序列化过程
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();

    // 写入链表长度
    s.writeInt(size);

    // 写入节点上的有效数据
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

// 反序列化过程
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();

    // 读取链表长度
    int size = s.readInt();
  
    // 读取有效元素并用 linkLast 添加到链表尾部
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}

private LinkedList<E> superClone() {
    try {
        return (LinkedList<E>) super.clone();
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

public Object clone() {
    LinkedList<E> clone = superClone();

    // Put clone into "virgin" state
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;

    // 将原链表中的数据依次添加到新立案表中
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);

    return clone;
}