LinkedList深入分析

原文出自：https://mp.weixin.qq.com/s/UJG9pFq22oTzQpGc11d9nw

• 导语

LinkedList集成AbstractSequentialList，实现了List，Deque，Cloneable，Serializable接口。AbstractSequentialList提供了骨干实现。Deque一个线性 collection，支持在两端插入和移除元素，定义了双端队列的操作。

分析要点

• 是否线程安全？
• 数据结构是怎样的？
• 怎么实现扩容？
• 怎么实现插入和获取元素？
• 应用与哪些场景？

深入剖析

构造函数

...
// 元素个数
transient int size = 0;
// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;
...
// 无参构造方法
public LinkedList() {
}

• LinkedList的数据结构为链表结构，有头节点和尾节点。Node中包含了当前元素和指向当前元素前、后的'指针'
• LinkedList本身存储容量无上限

元素的插入

• 元素插入分两种，一种是从链表头插入，一种从链表尾插入，实现效果相差无几，以下列举从表尾插入元素

public boolean add(E e) {
  // 从链表尾插入元素
  linkLast(e);
  return true;
}

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

元素的删除

// 该方法总的来说就是获取删除元素位置index
public E remove(int index) {
  // 验证index是否超过元素个数
  checkElementIndex(index);
  // node(index)遍历定位到要删除的节点元素
  return unlink(node(index));
}

• 删除节点

E unlink(Node<E> x) {
  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;
  }
}

是否线程安全

LinkedList为线程不安全的，主要在并发插入元素节点的时候，共享了成员变量first(头节点)、last(尾节点)。

应用场景

• 如果应用程序有更多的插入或者删除操作，较少的数据读取。

本节只列举出了LinkedList最基本的插入和删除方法，但是我们可以从中了解到它的实现原理，对我们分析LinkedList有很大帮助。想了解更多，请阅读LinkedList源码。

扫码关注了解更多