java集合-LinkedList

类图结构

LinkedList是List接口和Deque接口的双向链表实现类。它的类层级结构如图所示：

LinkedList继承自AbstractSequentialList，说明LinkedList具有顺序遍历的特性（ArrayList实现了RandomAccess接口具有随机遍历的特性），另外它还实现了Deque接口，说明LinkedList具有双端队列操作的特性。

类文件说明

LinkedList元素类型是泛型，可以存放【所有】类型的元素，包括null。LinkedList的元素以双链表的形式存储，因此在指定位置插入或删除元素需要从头顺序遍历或从尾反向顺序遍历到指定index所在的位置。所以ArrayList随机访问肯定比LinkedList快。那添加和删除操作LinkedList比ArrayList快吗？NO！添加和删除元素综合性能两者差不多！

ArrayList在指定index处添加或删除元素时，主要耗时在要System.arraycopy，它要移动指定index后面所有的元素。

LinkedList在指定index添加或删除元素时，主要耗时在需要从头顺序遍历或从尾反向顺序遍历到指定index所在的位置。

所以：

当指定插入或删除元素的位置越靠前时，ArrayList的性能越差。

当指定插入或删除元素的位置越靠中间时，LinkedList的性能越差。

数据量小时基本没什么区别，不用考虑；数据量大时，如果在中间位置插入或删除的操作增多，此时LinkedList性能并不比ArrayList好。

综上：一般选用ArrayList即可。LinkedList主要用于特殊数据结构栈、队列、双端队列操作时使用。

LinkedList内部元素双链表结构如下：

每个节点都有一个前驱指针和后驱指针，节点数据结构如下：

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数据结构如下：只有三个属性：size、first、last。注释上有说：

first为null时last也必为null表示是空链表
第二点：first.prev == null && first.item != null验证了不对，item是可以为null的
第三点同上：last.item也是可以为null的

transient int size = 0;

/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
*            (first.prev == null && first.item != null)
*/
transient Node<E> first;

/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
*            (last.next == null && last.item != null)
*/
transient Node<E> last;

linkFirst

linkFirst在头部添加元素，需要进行指针移动操作如下：

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
  final Node<E> f = first;
  // 新建头节点,prev = null, next = f
  final Node<E> newNode = new Node<>(null, e, f);
  // first指向新建的头节点
  first = newNode;
  // 如果之前的first为null，表示是空链表，则last也为null，
  // 此时插入新节点链表中只有这一个节点，first和last都指向它
  // 如果之前的first不为null，则表示之前链表已经有节点了，
  // 此时需要修改之前的first的前驱prev为新的first节点
  if (f == null)
    last = newNode;
  else
    f.prev = newNode;
  size++;
  modCount++;
}

操作前后图示：

linkLast

linkLast在尾部添加元素，需要进行指针移动操作如下：

/**
 * Links e as last element.
 */
void linkLast(E e) {
  final Node<E> l = last;
  // 新建尾节点，prev = l， next = null
  final Node<E> newNode = new Node<>(l, e, null);
  // last指向新建的尾节点
  last = newNode;
  // 如果之前的last为null，表示是空链表，则first也为null，
  // 此时插入新节点链表中只有这一个节点，first和last都指向它
  // 如果之前的last不为null，则表示之前链表已经有节点了，
  // 此时需要修改之前的last的后驱next为新的last节点
  if (l == null)
    first = newNode;
  else
    l.next = newNode;
  size++;
  modCount++;
}

操作前后图示：

linkeBefore

linkBefore在指定node前添加元素，需要进行指针移动操作如下：

/**
 * Inserts element e before non-null Node succ.
 */
void linkBefore(E e, Node<E> succ) {
  // assert succ != null;
  // 提取出新插入节点的prev
  final Node<E> pred = succ.prev;
  // succ则是新插入节点的next
  // 新建待插入节点
  final Node<E> newNode = new Node<>(pred, e, succ);
  // succ.prev指向新建的节点
  succ.prev = newNode;
  // 如果待插入节点的prev为null，表示新插入的节点将是头节点
  // 否则，正常设置prev.next为新插入节点
  if (pred == null)
    first = newNode;
  else
    pred.next = newNode;
  size++;
  modCount++;
}

操作前后图示：

get

LinkedList实现了List接口，所以支持按index获取元素的操作

public E get(int index) {
    // 判断index 是否超过LinkedList的index区间[0, size）
    checkElementIndex(index);
    // 根据index 获取对应位置的节点node
    return node(index).item;
}

// 根据index 获取对应位置的节点node
Node<E> node(int index) {
  // 二分法判断是从first开始向后遍历还是从last开始向前遍历
  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;
  }
}