Java集合之LinkedList

上一篇写的是ArrayList，这一篇写一下LinkedList.

开宗明义，因为Vector已经被废弃了，所以list家族只剩下ArrayList和LinkedList两兄弟了，这里直接对比一下二位：

ArrayList基于动态数组的实现，它长于随机访问元素，但是在中间插入和移除元素时较慢

LinkedList基于链表实现，在List中间进行插入和删除的代价较低，提供了优化的顺序访问。LinkedList在随机访问方面相对比较慢，但是它的特性集较ArrayList更大。

那么，到底特性集大在哪里呢？

这就是这篇博客的重点，在JAVA中，LinkedList可以作为我们最经常使用的两种数据结构来使用：栈和队列。Java中实现队列一般都是用LinkedList实现。

这是因为LinkedList的实现是一个双向链表，所以无论是FIFO还是FILO都可以实现。

(1)初始化：

先看一下LinkedList的继承情况吧：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

然后看一下LinkedList的成员变量

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

这就是我们很早学过的双向链表的实现基本要素。

看一下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;
    }
}

这里注意一下前面的修饰符 transient 关键字:

当对象被序列化时（写入字节序列到目标文件）时，transient阻止实例中那些用此关键字声明的变量持久化；当对象被反序列化时（从源文件读取字节序列进行重构），这样的实例变量值不会被持久化和恢复。

为什么要有这个关键字呢？因为我们要告诉虚拟机，这三个成员不是LinkedList的永久性变量。点到为止，后续在JVM的总结中会专门介绍一下各种关键字和虚拟机的关系。

(2)用作栈、队列和双向队列

对于这三种不同的数据结构的操作，LinkedList规定了6种基本动作。

getFirst()
getLast()
removeFirst()
removeLast()
addFirst()
addLast()

其中removeFirst()会调用unlinkFirst()函数，removeLast会调用unlinkLast()函数

下面看看是如何实现的栈和队列的功能。

用作栈：

public void push(E e) {
    addFirst(e);
}
public E pop() {
    return removeFirst();
}

View Code

用作队列：

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
public boolean offer(E e) {
    return add(e);
}

View Code

用作双端队列：

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}
public boolean offerLast(E e) {
    addLast(e);
    return true;
}
public E peekFirst() {
    if (size == 0)
        return null;
    return getFirst();
}
public E peekLast() {
    if (size == 0)
        return null;
    return getLast();
}
public E pollFirst() {
    if (size == 0)
        return null;
    return removeFirst();
}
public E pollLast() {
    if (size == 0)
        return null;
    return removeLast();
}

View Code

因为都是最简单的操作，都是望文生义的函数，所以就没写注释并且折叠代码了。

(3)其实没什么好写的

写完第二篇了，最大的感觉这些东西直接看文档就可以了，但是自己再看一遍源码也挺有趣，所以慢慢写吧，看一点写一点，从集合类到IO到并发到JVM，希望可以写完。

之前读了一本关于并发的书，最大的感慨就是数据结构太神奇，被各种思路使用的各种形式的数据结构，尤其是Disruptor使用的环形队列给惊艳到了。

读研以来，一直在看机器学习、并发编程和设计模式的知识，实验室项目从前端都后台到算法都尝试过，但是都不够深入，浮于表面，没什么用。

于是寒假反思了一下，开学又和晓晖聊了聊，感觉自己还是更适合做个软件工程师，而不是算法工程师。

所以趁着在学校，把一切都推倒重来，从零开始，夯实基础。