Java 集合系列04 LinkedList集合

1. LinkedList介绍

　　LinkedList是一个继承于AbstractSequentiaList的双向链表，可以被当作堆栈，队列或双端队列进行操作，它实现了List接口，也实现了java.io.Serializable接口，可以支持序列化，能够通过序列化传输。

2. LinkedList数据结构

　　LinkedList继承关系

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

3. 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.
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     */
    transient Node<E> last;

    /*
    void dataStructureInvariants() {
        assert (size == 0)
            ? (first == null && last == null)
            : (first.prev == null && last.next == null);
    }
    */

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

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

　　LinkedList类中定义了3个变量

　　size：集合长度

　　first：双向链表头节点

　　last：双向链表尾节点

　　first和last是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;
        }
    }

　　LinkedList是通过双向链表实现，双链表是通过Node类实现的，类中item变量保存当前节点的值，通过Next指向下一个节点，通过prev指向前一个节点。

　　get()

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

　　LinkedList中get()方法的实现：是通过node(index)来实现的，它的实现机制是：比较index和集合长度一半的大小，如果index比集合长度一半小，那么就从初始位置依次循环，直到找到为止；如果index大于集合长度一半，那么就从集合末尾依次向前找，直到找到为止；也就是越靠近中间的元素，查找次数越多，效率越低。

　　add()

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        final Node<E> l = last;     //初始时，last为空
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

　　（1）当第一个对象add时，初始时last为空赋值给l，这样newNode的prev，和next都为空，然后让last指向newNode，first指向newNode；

 　　（2）在第二个对象add时，add()方法默认在链表的尾部添加，再次调用linkLast()方法，此时last已经不为空（last开始指向上一个结点）赋值给l，，新的节点的newNode的prev指向上一个节点，next指向null，然后让上一个结点的next指向新的节点维护双向链表。

　　remove()

    public E remove() {
        return removeFirst();
    }

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

　　remove()默认删除链表的第一个结点

　　（1）在removeFirst()中先让first指向第一个结点；

　　（2）获取到第一个结点的item，获取到第二个结点（next = f.next），然后将第一个结点的item置为null，第一个结点的next指向为null，让first指向第二个结点（next）,第二个结点的prev也指向为null，维护链表的关系；

4. LinkedList遍历

public class LinkedList01 {
    public static void main(String[] args) {
        LinkedList<Integer> list = getLinkedList();
        listByNormalGet(list);
        listByForEach(list);
        listByInterator(list);
    }
    /*
        通过迭代器遍历
     */
    private static void listByInterator(LinkedList<Integer> list) {
        long startTime = System.currentTimeMillis();
        for(Iterator it = list.iterator(); it.hasNext(); ){
            it.next();
        }
        long interval = System.currentTimeMillis() - startTime;
        System.out.println("通过迭代器遍历：" + interval + "ms");
    }
    /*
        通过增强for遍历
     */
    private static void listByForEach(LinkedList<Integer> list) {
        long startTime = System.currentTimeMillis();
        for(Integer i : list){

        }
        long interval = System.currentTimeMillis() - startTime;
        System.out.println("通过增强for遍历：" + interval + "ms");
    }

    /*
        通过get遍历
     */
    private static void listByNormalGet(LinkedList<Integer> list) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {
            list.get(i);
        }
        long interval = System.currentTimeMillis() - startTime;
        System.out.println("通过get遍历：" + interval + "ms");
    }

    /*
        创建一个LinedList
     */
    private static LinkedList<Integer> getLinkedList() {
        LinkedList list = new LinkedList();
        for (int i = 0; i < 50000; i++) {
            list.add(i);
        }
        return list;
    }
}

　　通过迭代器和增强for的遍历方式时间远远小于通过get方式遍历，通过反编译工具查看通过增强for循环也是调用迭代器iterator。