LinkedList

LinkList 相比于 ArrayList 有两个特征：顺序访问和写快读慢
不支持 RandomAccess 所以 for 循环 get() 效率低于 迭代器遍历

父类和接口

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

1、java.util.AbstractSequentialList：

• 该抽象类继承自java.util.AbstractList，是List 接口的简化版实现(只支持顺序访问，不支持随机访问)
• Sequential 相继的，按次序的
• 提供 get、set、add、addAll、remove等方法的迭代器方式实现。

2、java.util.Deque：

• 双向队列接口，继承自 java.util.Queue。实现后可以操作任意队列节点。

  成员变量

  1、transient int size = 0;

• 用于标记序列大小，因为链表除了统计节点个数外并没有办法获取 size，所以提供了一个标记量来记录，提高效率。

2、transient Node first;

• 链表的头部节点。

3、transient Node last;

• 链表的尾部节点。

  Deque 双向链表的实现

  关键方法：

• addFirst(E): 在队头添加元素。

• addLast(E): 在队尾添加元素。
• E removeFirst(): 删除队头元素。
• E removeLast(): 删除队尾元素。

这些方法都是通过操作成员变量 first 和 last 实现的。 first 和 last 的类型时私有类 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;
    }
}

addLast 的实现

• 新建一个 Node，数据域为方法形参，前驱节点为 last，后继为 null
• 更新 last 为 新建节点
• 如果 之前的 last 为空，那么 first 更新为新建节点
• 更新 size 和 modCount ```java public void addLast(E e) { linkLast(e); }

void linkLast(E e) { final Node l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } ``` getFirst、getLast
取出头部、尾部的数据，直接返回 first.item 和 last.item

public E get(int index)

• LinkedList 是顺序存储结构，要取到第 i 个数据，必须顺序遍历到 i 结点，所以这个方法时间复杂度为 O(n)。
• 具体实现时做了优化，如果 index 小于 size 的一半，那么正序遍历，反之倒序遍历，遍历规模小了一半，这也是双向队列的应用。

  set、add、addAll

  set 与 add:
  与 ArrayList 不同，LinkedList 的 add 方法比 set 更加迅速。
  add 的本质是在尾部增加一个结点，通过 LinkedList 的成员变量 last 很快就能实现，而 set 需要遍历查找到指定结点再替换。
  addAll:
  等价于调用多次 add

  removeFirst、removeLast、remove

  removeFirst 与 removeLast方法用于移动头尾结点并返回数据，remove 则是遍历到指定结点然后移除。
  remove 方法只需要修改待删除结点的后继结点的 pre 与前驱结点的 next，不需要像 ArrayList 移动数据，更高效。