Java源码阅读（三） LinkedList类

LinkedList 适用于集合元素先入先出和先入后出的场景，在队列源码中被频繁使用，面试也经常问到，本小节让我们通过源码来加深对 LinkedList 的了解。

1 整体架构

LinkedList 底层数据结构是一个双向链表，整体结构如下图所示：

上图代表了一个双向链表结构，链表中的每个节点都可以向前或者向后追溯，我们有几个概念如下：

链表每个节点我们叫做 Node，Node 有 prev 属性，代表前一个节点的位置，next 属性，代表后一个节点的位置；
first 是双向链表的头节点，它的前一个节点是 null。
last 是双向链表的尾节点，它的后一个节点是 null；
当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null；
因为是个双向链表，只要机器内存足够强大，是没有大小限制的。

链表中的元素叫做 Node，我们看下 Node 的组成部分：

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