linkedList源码分析

LinkedList是通过双向链表去实现的，他的数据结构具有双向链表的优缺点

链表

1.灵活的空间要求，存储空间不要求连续

2.不支持下标的访问，只支持顺序遍历检索

3.针对增删效率会更高些，只和操作节点的前后节点有关系，无需移动元素。

LinkedList 顺序访问效率会非常高，而随机访问的效率会比较低

一、重要属性

熟悉重要属性，便于理解源码逻辑

    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;
    
    // 重要内部类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;
		}
    }

重要方法

理解一两个基本上就都懂了

1、push

因为linkedList内部保存了链表的收尾节点，所有push（addFirst）和add（addLast）都能非常方便快速的插入新节点

针对增删效率会更高些，只和操作节点的前后节点有关系，无需移动元素。

    public void push(E e) {
        addFirst(linkFirst(e));
    }  
	// 在最前面加入节点-对象
    private void linkFirst(E e) {
        // 直接拿到第一个节点
        final Node<E> f = first;
        // 构建需要插入的节点对象
        final Node<E> newNode = new Node<>(null, e, f);
        // 因为是要在第一个节点对象前插入节点，所以把新节点给first
        first = newNode;
        // 如果原来的first节点是null，那么新节点也是最后一个节点
        if (f == null)
            last = newNode;
        else
            // 否则原来的first前面就赋值为新节点，成为新的first节点
            f.prev = newNode;
        size++;
        modCount++;
    }

2、get

不支持下标的访问，只支持顺序遍历检索

那么的它的顺序访问效率会非常高，而随机访问的效率会比较低

    public E get(int index) {
        // 跟arraylist类型，跟size比较，检查下标  IndexOutOfBoundsException
        checkElementIndex(index); 
        return node(index).item;
    }
    // 顺序遍历链表，获取元素
    Node<E> node(int index) {
        // assert isElementIndex(index);
        // 遍历的时候有个算法，类似于二分法
        // 索引位置小于size的一半的位置--正向遍历
        // 否则    -   			   反向遍历
        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;
        }
    }