【JAVA基础——LinkedList】

学习记录之路。。。

LinkedList双向链表实现的接口列表和deque容器。实现所有可选的列表操作，并允许所有元素（包括null）。

先来看一下LinkedList 类 的创建：

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;  

    /**
     * Pointer to first node.
     * 指向第一节点的指针
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * 指向最后一个节点的指针
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }
           

实现的接口有四个， 分别是列表接口，队列接口，克隆标记类，序列化标记类。 

这里顺便提一下 “transient”：表示临时性， 也就是说，被修饰的变量，不会被序列化。（需要了解的可以自行查找资料）

接下来是链表的源码的核心代码：

核心思想是在内部创建了一个内部类Node，通过内部类来存放链表中的元素。下面是源码节选：

/**
     * Node对象， 链表的每个节点都存储了， 上个一个节点标记， 当前节点元素， 下一个节点标记 ， 三个值。
     *
     * 所以采用，定义一个Node对象来存这三个值。 注意： 三个参数。
     * @param <E>
     */
    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;
        }
    }
           

几乎每个方法都会创建这个对象，来对链表元素进行添加等的操作。例如下面的这个addFirst()方法：

/**
     * Inserts the specified element at the beginning of this list.
     * 在列表的头部插入指定的元素
     * @param e the element to add
     */
    public void addFirst(E e) {
        linkFirst(e);
    }
           

/**
     * Links e as first element.
     *
     *添加第一个元素时， 是第一个元素，也是最后一个元素。
     *
     * 创建了一个Node对象，里面有三个Node对象？ 上一个节点，目前节点，下一个节点，
     *
     * 添加的元素，都赋值给Node对象的item（当前节点）上。
     */
    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++;
    }
           

源码就到这里结束，其他都跟这个思路差不多，这里就不贴了。

LinkedList 的方法很多，由于他是两个接口的实现类，所以，会根据列表，还是队列的实现会用不同的方法。

下面是链表的部分方法（来自jdk7）：