LinkedList

之前一直以为 LinkedList 是单链表结构，面试的时候被纠错了，因此现在查看源码，了解一下；

后来想想也对，如果是尾部插入、删除等操作，肯定是双向链表更加快速，单链表还需要遍历到尾部才可以实现；

以下基于 JDK8 源码

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

一些字段：

 public class LinkedList<E>
     extends AbstractSequentialList<E>
     implements List<E>, Deque<E>, Cloneable, java.io.Serializable
 {
     // 链表大小
     transient int size = 0;
     // 首个节点
     transient Node<E> first;
     // 最后一个节点
     transient Node<E> last;   
 }

add 添加元素

尾部添加元素

在 LinkedList 后面直接加入一个元素：

  • 直接在双向链表后面创建节点并更新 last；

 public boolean add(E e) {
     linkLast(e);
     return true;
 }
 // 双向链表的 last 直接插入后更新 last
 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 查找到对应的节点，根据插入位置是在前半部分还是后半部分决定是正向查找（从 first 开始） 还是反向查找 （从 last 开始）

  • 调用 linkBefore 插入到查找到的节点前面

 public void add(int index, E element) {
     checkPositionIndex(index);
     if (index == size)
         linkLast(element);
     else
         linkBefore(element, node(index));
 }
 ​
 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;
     }
 }
 ​
 void linkBefore(E e, Node<E> succ) {
     // assert succ != null;
     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++;
 }

get访问

访问某一个位置的元素：

  • 检查下标是否越界；

  • 使用 node 来查找对应位置的节点，并返回内部的数据

 public E get(int index) {
     checkElementIndex(index);
     return node(index).item;
 }

remove 删除

删除某一个位置上的元素：

  • 检查下标是否越界；

  • 通过 node 找到对应位置的节点

  • unlink 将指定节点从双向链表中移除；

 public E remove(int index) {
     checkElementIndex(index);
     return unlink(node(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;
 }

indexOf查找元素对应位置

查找指定元素在 LinkedList 中的位置：

  • 这里对元素是否为空分别有不同的实现

  • 对于不为空的元素，会使用 equals 进行判断；

 public int indexOf(Object o) {
     int index = 0;
     if (o == null) {
         for (Node<E> x = first; x != null; x = x.next) {
             if (x.item == null)
                 return index;
             index++;
         }
     } else {
         for (Node<E> x = first; x != null; x = x.next) {
             if (o.equals(x.item))
                 return index;
             index++;
         }
     }
     return -1;
 }

总结

LinkedList 的实现还是非常简单的，因为只有一个双向链表，同时也不需要进行扩容的操作；

LinkedList的优劣势

LinkedList 的作者曾表示：尽管设计了这个，但决不会去用它；

对于读写操作：

  • 如果是头部或者尾部插入，时间复杂度为 O(1)，如果是中间插入，那么时间复杂度还是 O(n)；

  • 删除也是同理；

  • 对于访问元素，LinkedList 不支持随机访问 RandomAccess，需要进行遍历才能访问到对应位置上的元素，时间复杂度是 O(n)；

  • 对比支持随机访问的 ArrayList ，LinkedList 的优势也只有在头部或尾部插入（删除）时，复杂度只有 O(1)

  • 对于一些经常需要对头部、尾部进行插入或删除操作的场景，比如队列、栈这些数据结构，使用 LinkedList会比较方便；

对于内存使用

  • LinkedList 并不像 ArrayList 需要申请一块非常大的内存，只需要申请一小块内存来存放节点对象即可；

  • 但是相对来说，这些一个个小的内存被释放后会产生内存碎片，会导致可能没有比较大的连续内存分配给其他对象，增加 GC 的概率；

  • ArrayList 释放后是可以有一块连续的内存，并不会产生内存碎片；

首先了解下 时间局部性和空间局部性

  • 时间局部性是指被引用过一次的内存位置很可能在不远的将来再被多次引用。

  • 空间局部性是指如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用其附近的一个内存位置。

对于 CPU 缓存（空间局部性）：

  • 因空间局部性原理，CPU 缓存会读取一块连续的内存；

  • 对于 LinkedList 来说，其节点是不连续分配在内存中的，当访问下一个节点时会导致 CPU 缓存失效（命中失败），需要继续从内存中去访问对应节点；

  • 对于 ArrayList 来说，是一个连续的内存来存放数据，因此连续访问元素时，CPU缓存的命中率较高；

这里从 OKHttp 中的 AsyncCallQueue 中并不使用 LinkedList 而是 ArrayDeq