1. Important Variables

1
2
3
4
5

transient int size = 0;
// 头节点指针
transient Node<E> first;
// 尾节点指针
transient Node<E> last;

1
2
3
4
5
6
7
8
9
10

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;
    }
}

LinkedList 使用双向链表实现，内部类Node用来表示一个节点。LinkedList 同时实现了 List 接口和 Deque 接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。关于栈或队列，现在的首选是ArrayDeque，当作栈或队列使用时，它有着比 LinkedList 有着更好的性能。

2. Main Mthods

• add()
  有两种添加单个元素的方法，add(E e)和· add(int index, E element)：

  • add(E e)在（链表）末尾加入元素，通过以下方法实现。

    1 2 3 4 5 6 7 8 9 10 11

    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++; }

  • add(int index, E element) 添加到指定的位置，包括索引检查、添加在末尾就调用linkLast，否则调用linkBefore实现

    1 2 3 4 5 6 7 8 9 10 11 12 13

    // succ =node(index) void linkBefore(E e, Node<E> succ) { // e 插入到succ之前 final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }

• remove()
  也有两种remove方法，remove(int index)和remove(Object o)删除指定位置或者与指定元素（可以为null）相等的第一个元素。最终都通过unlink(Node<E> x)来实现。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  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; // 可GC size--; return element; }

• get()
  通过调用node(int index)实现，返回指定位置的元素。

  1 2 3 4 5 6 7 8 9 10 11 12 13

  Node<E> node(int 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; } }

• set()
  修改指定位置元素的值。

  1 2 3 4 5 6 7

  public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; }

3. 其他

1. transient关键字表示序列化时忽略，LinkedList的双指针都忽略了，序列化时如何保存数据呢？

   1 2 3 4 5 6 7 8 9 10

   private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out size s.writeInt(size); // Write out all elements in the proper order. for (LinkedList.Node<E> x = first; x != null; x = x.next) s.writeObject(x.item); }

   查看源码我们发现LinkedList是通过writeObject和readObject实现序列化和反序列化，序列化时存储size和每个数据。反序列化时读取size然后使用linkLast边读边重建。因为如果直接序列化链表反序列化时节点地址会改变，指向下一个节点的指针会失效。

   1 2 3 4 5 6 7 8 9 10

   private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject(); // Read in size int size = s.readInt(); // Read in all elements in the proper order. for (int i = 0; i < size; i++) linkLast((E)s.readObject()); }