一、LinkedList 的剖白

大家好，我是 LinkedList，和 ArrayList 是同门师兄弟，但我俩练的内功却完全不同。师兄练的是动态数组，我练的是链表。

问大家一个问题，知道我为什么要练链表这门内功吗？

举个例子来讲吧，假如你们手头要管理一推票据，可能有一张，也可能有一亿张。

该怎么办呢？

申请一个 10G 的大数组等着？那万一票据只有 100 张呢？

申请一个默认大小的数组，随着数据量的增大扩容？要知道扩容是需要重新复制数组的，很耗时间。

关键是，数组还有一个弊端就是，假如现在有 500 万张票据，现在要从中间删除一个票据，就需要把 250 万张票据往前移动一格。

遇到这种情况的时候，我师兄几乎情绪崩溃，难受的要命。师父不忍心看到师兄这样痛苦，于是打我进入师门那一天，就强迫我练链表这门内功，一开始我很不理解，害怕师父偏心，不把师门最厉害的内功教我。

直到有一天，我亲眼目睹师兄差点因为移动数据而走火入魔，我才明白师父的良苦用心。从此以后，我苦练“链表”这门内功，取得了显著的进步，师父和师兄都夸我有天赋。

链表这门内功大致分为三个层次：

第一层叫做“单向链表”，我只有一个后指针，指向下一个数据；

第二层叫做“双向链表”，我有两个指针，后指针指向下一个数据，前指针指向上一个数据。

第三层叫做“二叉树”，把后指针去掉，换成左右指针。

但我现在的功力还达不到第三层，不过师父说我有这个潜力，练成神功是早晚的事。

先赞后看：《Java 程序员进阶之路》专栏在 GitHub 上已经开源了，有 GitHub 账号的小伙伴，来安排一波 star 呀！看能不能冲一波 trending 榜单，求求各位了。

GitHub 地址：https://github.com/itwanger/toBeBetterJavaer

二、LinkedList 的内功心法

好了，经过我这么样的一个剖白后，大家对我应该已经不陌生了。那么接下来，我给大家展示一下我的内功心法。

我的内功心法主要是一个私有的静态内部类，叫 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;
    }
}

它由三部分组成：

节点上的元素

下一个节点

上一个节点

我画幅图给你们展示下吧。

对于第一个节点来说，prev 为 null；

对于最后一个节点来说，next 为 null；

其余的节点呢，prev 指向前一个，next 指向后一个。

我的内功心法就这么简单，其实我早已经牢记在心了。但师父叮嘱我，每天早上醒来的时候，每天晚上睡觉的时候，一定要默默地背诵一遍。虽然我有些厌烦，但我对师父的教诲从来都是言听计从。

03、LinkedList 的招式

和师兄 ArrayList 一样，我的招式也无外乎“增删改查”这 4 种。在此之前，我们都必须得初始化。

LinkedList<String> list = new LinkedList();

师兄在初始化的时候，默认大小为 10，也可以指定大小，依据要存储的元素数量来。我就不需要。

1）招式一：增

可以调用 add 方法添加元素：

list.add("沉默王二");
list.add("沉默王三");
list.add("沉默王四");
add 方法内部其实调用的是 linkLast 方法：
public boolean add(E e) {
    linkLast(e);
    return true;
}
linkLast，顾名思义，就是在链表的尾部链接：
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++;
}

添加第一个元素的时候，first 和 last 都为 null。

然后新建一个节点 newNode，它的 prev 和 next 也为 null。

然后把 last 和 first 都赋值为 newNode。

此时还不能称之为链表，因为前后节点都是断裂的。

添加第二个元素的时候，first 和 last 都指向的是第一个节点。

然后新建一个节点 newNode，它的 prev 指向的是第一个节点，next 为 null。

然后把第一个节点的 next 赋值为 newNode。

此时的链表还不完整。

添加第三个元素的时候，first 指向的是第一个节点，last 指向的是最后一个节点。

然后新建一个节点 newNode，它的 prev 指向的是第二个节点，next 为 null。

然后把第二个节点的 next 赋值为 newNode。

此时的链表已经完整了。

我这个增的招式，还可以演化成另外两个：

addFirst() 方法将元素添加到第一位；

addLast() 方法将元素添加到末尾。