在Java的ArrayList内部实现一文中，我们已经看到了List接口之一的实现– ArrayList的内部实现细节。在本文中，我们将看到Java中的LinkedList内部实现，这是List接口的另一种实现

有关LinkedList在Java内部如何工作的问题可能如下：

• LinkedList类如何存储其元素。
• Java中的LinkedList类是作为单链表还是双链表实现的。
• 将元素添加到LinkedList时会发生什么。由于它是一个LinkedList，因此在第一个位置或者最后一个位置添加元素的实现是什么。
• remove()方法如何在LinkedList中工作。
• get()方法如何在LinkedList中工作。

在这篇文章中，我们通过研究Java中LinkedList的内部实现来尝试回答这些问题。

LinkedList类如何存储其元素

Java中的内部LinkedList类使用Node类型的对象来存储添加的元素。在LinkedList类中，将节点实现为静态类。由于LinkedList类是作为双链表实现的，因此每个节点都存储对下一个以及上一个节点的引用以及所添加的元素。

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

它是双链表吗

如已经显示的，Java LinkedList类被实现为双链表，并且每个节点都存储对下一个以及上一个节点的引用。

add()方法如何在LinkedList中工作

由于它是一个链表，因此除了常规的add()方法以进行顺序添加之外，Java LinkedList类中还包含有addFirst()和addLast()方法。
还有单独的变量，用于保存链接列表的第一个和最后一个节点的引用。

/**
* Pointer to first node.
*/
transient Node<E> first;

/**
* Pointer to last node.
*/
transient Node<E> last;

如果调用常规的add()方法或者addLast()方法，则会在内部调用linkLast()方法。在此方法中，将创建一个新节点来存储添加的元素，并且变量last开始引用该节点(因为此新节点成为最后一个节点)。在这种情况下，还要检查一下是否是第一个插入节点，所以它也是第一个节点。

LinkedList类中的linkLast()方法实现

/**
 * Links e as last element.
 */
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++;
}

如果我们在内部调用addFirst()方法，则将调用linkFirst()方法。在此方法中，将创建一个新节点来存储添加的元素，并且变量首先开始引用该节点(因为此新节点成为第一个节点)。在这种情况下，还要检查是否是第一个插入节点，所以它也是最后一个节点。如果不是第一个节点，则先前的"第一个"节点现在位于第二个位置，因此其上一个引用必须引用新节点。

LinkedList类中的LinkFirst()方法实现

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
  final Node<E> f = first;
  final Node<E> newNode = new Node<>(null, e, f);
  first = newNode;
  if (f == null)
    last = newNode;
  else
    f.prev = newNode;
  size++;
  modCount++;
}

还有一个add()方法可在特定索引处添加元素。如果调用该方法，则必须将传递的索引处已经存在的元素右移。

remove()方法如何在Java LinkedList类中工作

就像add()方法用于从LinkedList中删除元素一样，除了常规的remove()方法(传递索引或者元素的方法)之外，还有removeFirst()和removeLast()方法。

调用remove()方法时，必须更改已删除节点左右两边的节点的引用，以便左下一个节点开始参考右上的节点，并参考右上一节点。开始引用要删除的节点左侧的节点。

下图将了解实际需要执行的操作。这里中间节点必须删除。

get()方法如何在Java LinkedList类中工作

如果再次使用get()方法，则还有getFirst()和getLast()方法。如果使用get()方法，则必须获取传递的索引的节点并返回node.item。

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

如果是getFirst()和getLast()，则引用也存储在first和last变量中，因此只需返回值first.item或者last.item。