前言

存放数据的容器其重要性不再多说了， 项目中到处在使用， 所以从分析下相应的容器重要源码， 以便加深记忆。
通过名称我们应该可以意识到， 这个存储结果是链式的。

源码分析

仅仅分析其最重要用的最多的方法。 重要成员变量、 初始化、 add、 remove

重要成员变量

1
2
3
4
5
transient int size = 0;

transient Node<E> first;

transient Node<E> last;

以上就是 LinkedList 的所有成员变量了， 我们知道其内部是链式结构存储， 看名称我们先猜测下， size 是数据存储的多少， first 和 last 是第一个和最后一个的指针。
我们看看 Node 这个节点数据长什么样子吧

1
2
3
4
5
6
7
8
9
10
11
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;
    }
}

看着其结构 item 是当前节点的数据， next 和 prev 是两个指针， 一个是前驱和后驱的指针。 难道是双向链表结构？

构造方法

1
2
public LinkedList() {
}

添加

1
2
3
4
public boolean add(E e) {
    linkLast(e);
    return true;
}

先打住， add 添加数据看着方法调用了 linkLast， 通过名称可以看到， 添加数据直接链接在最后了。

1
2
3
4
5
6
7
8
9
10
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++;
}

是对链表的基础操作， 那么我们可以看出来什么， 通过 new Node 这个参数可以看到， 最后一个节点的 next 指针指向 null， 说明其存储结构非环形的。 往下面看可以看出当 l = null 时， first 和 last 都指向的当前新增的节点（且 prev 和 next 指针都为 null）, 如果不为空的话， 直接往后面追加了一个节点。 通过添加节点也可以看出其是一个非循环的双向链表结构。

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

可以看出从头节点向后找， 找到都都是 unlink 方法。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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--;
    return element;
}

从上掉下一个一个的看下。 其中先把要删除的信息都赋值变量拿到， prev = null 说明什么， 说明当前节点是头结点呀， 也就是 first 指针， 所以直接 first = next， 把第一个节点从链表中进行剔除。 如果 prev != null 的话， 就 prev.next = next, x.prev = null， 也是把当前删除的节点链表中剔除。 所以上面第一个 if else 已经把要删除的数据从链表中删除啦。 好像不太对呀， 这样只能说只剔除了一般， 其双向链表还没有完全链接正确。
通过上面第一个 if else 可以看出我们仅仅维护了 next， 那么当前这条链子还有 prev 指针是野指针呢，除了这个外还有特殊情况下的 last 指针需要处理呢， 所以要经过下面的 第二个 if else 处理。 如果 next = null 的话， 说明是最后一个节点， 所以直接把当前节点的前一个当成 last 即可， 如果不为 null 呢， 说明是中间的数据删除了， next.prev = prev, x.next = null ，才真正的把链表的结构给链接好。
所以通过上面两个 if else 把数据进行剔除， 然后把链接维护联通不出错。
最后就是赋值， 然后 size - 1。