深度解析LinkedList-六虎

LinkedList是Java调集结构中List接口的完成之一，它以双向链表的形式存储元素。与传统的数组比较，链表具有更高的灵敏性，特别适用于频频的刺进和删去操作。让咱们从底层完成开端深化了解这个强壮的数据结构。

linkedList.jpg

底层数据结构

LinkedList的底层数据结构是双向链表。每个节点都包括一个数据元素以及两个引证，一个指向前一个节点（prev），一个指向下一个节点（next）。这种结构使得在链表中进行刺进和删去操作变得十分高效。

linkedList.png

LinkedList的特点及Node源码如下：

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;
    public 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包括两个重要的实例变量：first和last，别离指向链表的头节点和尾节点。这两个节点使得在链表的两端进行操作更为高效。

size字段表明链表中元素的数量，经过它咱们能够随时获取链表的巨细。

Node类是LinkedList数据结构的根底。每个节点都包括一个数据元素、一个指向下一个节点的引证（next），以及一个指向前一个节点的引证（prev）。

item：当时节点的数据元素。
next：下一个节点的引证。
prev：前一个节点的引证。

操作办法

篇幅有限，咱们在这具体解释下常用的几个办法，别的办法家人们可自行阅览源码

add(E e): 在链表尾部添加元素

add(E e): 在链表尾部添加元素。

// LinkedList类中的add办法
public boolean add(E e) {
    linkLast(e);
    return true;
}

linkLast(e)

// 在链表尾部链接新节点的办法
void linkLast(E e) {
    // 获取尾节点的引证
    final Node<E> l = last;
    // 创立新节点，其前一个节点是尾节点，后一个节点为null
    final Node<E> newNode = new Node<>(l, e, null);
     // 将新节点更新为尾节点
    last = newNode;
    if (l == null)
        // 假如链表为空，一起将新节点设置为头节点
        first = newNode;
    else
        // 否则，将原尾节点的next指向新的尾节点
        l.next = newNode;
    // 添加链表的巨细
    size++;
    //修正计数器
    modCount++;
}

源码详解：

final Node l = last;

经过last字段获取链表的尾节点引证。这一步是为了后续创立新节点时能够将其连接到链表的尾部。
final Node newNode = new Node<>(l, e, null);

运用Node类的结构办法创立一个新节点，其前一个节点是链表的尾节点l，后一个节点为null，由于这是新的尾节点。
last = newNode;

将链表的last字段更新为新创立的节点，使其成为新的尾节点。

if (l == null) first = newNode;

假如链表为空（即尾节点为null），则将头节点first指向新节点。由于在空链表中添加元素时，头节点和尾节点都是新节点。
else l.next = newNode;

假如链表非空，将原尾节点的next引证指向新节点，以完成新节点的刺进。

size++;

每次成功添加一个元素后，添加链表的巨细。
modCount++;

modCount是用于迭代器的修正计数器，用于在迭代时检测是否有其他线程修正了调集。每次对链表结构进行修正时，都会添加modCount的值。modCount是用于迭代器的修正计数器，用于在迭代时检测是否有其他线程修正了调集。每次对链表结构进行修正时，都会添加modCount的值。

add(int index, E element): 在指定方位刺进元素

  //在指定方位刺进元素的办法
  public void add(int index, E element) {
    //参数查看
    checkPositionIndex(index);
    //链表尾部刺进元素
    if (index == size)
        linkLast(element);
    // 非尾部刺进的状况
    else
        linkBefore(element, node(index));
}

checkPositionIndex()：参数查看

//参数查看
private void checkPositionIndex(int index) {
  if (!isPositionIndex(index))
      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

isPositionIndex():判别指定下标是否合法

//判别指定下标是否合法
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

node(int index)：获取指定方位的节点

Node<E> node(int index) {
    // assert isElementIndex(index);
     //判别索引方位(判别索引位于链表的前半部分仍是后半部分，进步元素获取的性能)
    if (index < (size >> 1)) {
        //前半部分的话从头节点开端遍历，经过节点的next一向查找到当时索引地点的元素
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
       //后半部分的话从尾始遍历，经过节点的prev一向查找到当时索引地点的元素                         
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

源码详解：

if (index < (size >> 1)) {

>>带符号右移运算符，一个数的二进制表明向右移动指定的位数，左侧空出的方位运用原始数值的最高位进行填充。这个操作相当于将数值除以2的指定次方并向下取整。右移一位相当于除以2。

这行代码是判别索引方位,即判别索引位于链表的前半部分仍是后半部分来决定是早年往后仍是从后往前遍历链表，以进步元素获取的性能。

Node x = first; for (int i = 0; i < index; i++) x = x.next;

假如方针节点在链表的前半部分，就从头节点 first 开端，经过next往后遍历，找到对应索引的节点并回来。

Node x = last; for (int i = size – 1; i > index; i–) x = x.prev;

假如方针节点在链表的后半部分，就从尾节点 last 开端,经过prev往前遍历，找到对应索引的节点并回来。

linkBefore():非尾部刺进元素

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

源码详解：

final Node pred = succ.prev;

经过 succ 节点的 prev 引证，获取刺进方位的前一个节点 pred。
final Node newNode = new Node<>(pred, e, succ);

运用 Node 类的结构办法创立一个新的节点，其前一个节点是 pred，后一个节点是 succ。
succ.prev = newNode;

将后继节点 succ 的前驱引证指向新节点 newNode，保证新节点的刺进。
if (pred == null) first = newNode;

假如前驱节点为空，阐明新节点刺进的方位是链表的头部，将链表的头节点 first 指向新节点 newNode。
else pred.next = newNode;

假如前驱节点非空，将前驱节点的 next 引证指向新节点 newNode，完成新节点的刺进。
size++;

每次成功添加一个元素后，添加链表的巨细。

modCount++;

modCount是用于迭代器的修正计数器，用于在迭代时检测是否有其他线程修正了调集。每次对链表结构进行修正时，都会添加modCount的值。modCount是用于迭代器的修正计数器，用于在迭代时检测是否有其他线程修正了调集。每次对链表结构进行修正时，都会添加modCount的值。

remove(Object o): 从链表中移除指定元素

public boolean remove(Object o) {
  //处理删去元素为null的状况
  if (o == null) {
      //遍历链表
      for (Node<E> x = first; x != null; x = x.next) {
          //获取到第一个为null的元素
          if (x.item == null) {
              //删去元素
              unlink(x);
              return true;
          }
      }
   //处理删去元素非null的状况
  } else {
      //遍历链表
      for (Node<E> x = first; x != null; x = x.next) {
          //获取到要删去的元素
          if (o.equals(x.item)) {
              //删去元素
              unlink(x);
              return true;
          }
      }
  }
  return false;
}

源码解析：

if (o == null) {

这里首要查看传入的参数 o 是否为 null，别离处理 null 和非 null 两种状况。

if (o == null) { for (Node x = first; x != null; x = x.next) {…

假如要删去的元素是 null，则经过遍历链表找到第一个值为 null 的节点，然后调用 unlink(x) 办法删去该节点。删去成功后回来 true。假如要删去的元素是 null，则经过遍历链表找到第一个值为 null 的节点，然后调用 unlink(x) 办法删去该节点。删去成功后回来 true。

else { for (Node x = first; x != null; x = x.next) { …

假如要删去的元素不为 null，则经过遍历链表找到第一个值与参数 o 相等的节点，然后调用 unlink(x) 办法删去该节点。删去成功后回来 true。

return false;

假如遍历完整个链表都没有找到要删去的元素，则回来 false 表明删去失利。

unlink(Node x)：实际执行节点删去的办法

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

源码详解：

final E element = x.item;

经过 x 节点的 item 字段获取节点的数据元素，即要删去的元素。
final Node next = x.next; final Node prev = x.prev;

经过 x 节点的 next 和 prev 字段获取方针节点的后继节点和前驱节点。

if (prev == null) { if (prev == null) { first = next; } else { prev.next = next; x.prev = null; }

假如前驱节点为空，阐明要删去的节点是链表的头节点，将方针节点的后继节点 next设置为链表的头节点 first 。假如前驱节点非空，将前驱节点的 next 引证指向方针节点的后继节点，一起将方针节点的 prev 引证置为 null。
if (next == null) { last = prev; else { next.prev = prev; x.next = null; }

假如后继节点为空，阐明要删去的节点是链表的尾节点，将链表的尾节点 last 指向方针节点的前驱节点 prev。假如后继节点非空，将后继节点的 prev 引证指向方针节点的前驱节点，一起将方针节点的 next 引证置为 null。

x.item = null;

将方针节点的 item 字段置为 null，协助垃圾收回系统收回节点的数据元素。

size–; modCount++;

每次成功删去一个节点后，减小链表的巨细，并更新修正计数器。
return element;

最后，回来被删去节点的数据元素。

LinkedList的优势和下风

优势

动态巨细：链表能够动态地分配内存，不需要预先指定巨细。
刺进和删去：在链表中刺进和删去元素更为高效，由于只需要调整节点的引证。

下风

随机拜访困难：在链表中要拜访特定方位的元素，必须从头结点开端遍历，功率相对较低。
额外空间：链表每个节点需要额外的空间存储引证，比较数组会占用更多的内存。

运用场景

LinkedList适用于以下场景：

频频的刺进和删去操作：由于链表的节点能够方便地刺进和删去，适用于这类操作频频的场景。
不需要频频随机拜访：假如主要操作是在链表两端进行，而不是在中间进行随机拜访，那么链表是一个不错的选择。

总结

LinkedList作为Java调集结构中的一个重要成员，为开发者提供了一种灵敏而高效的数据结构。经过深化了解其底层完成和基本特性，咱们能够更好地在实际运用中选择和运用这一数据结构，从而优化程序的性能和功率。希望这篇文章能够协助你更好地了解和运用LinkedList。

深度解析LinkedList

底层数据结构

操作办法

add(E e): 在链表尾部添加元素

add(int index, E element): 在指定方位刺进元素

remove(Object o): 从链表中移除指定元素

LinkedList的优势和下风

优势

下风

运用场景

总结

相关文章

Android 组件化架构思路

我用Echarts图表分析了巴西队历年战绩

前端：需要掌握哪些技能才能找到满意的工作？

StackView & frame

作者信息