Java语言之LinkedList源码分析(jdk1.8）

1、LinkedList简介

        LinkedList见名知意，他在数据结构中是一个类似于链表的链式存储结构。学习过数据结构的我们都知道链式存储最大的特点有以下

•   链表长度不受限制（理论上在内存空间允许的情况下链表可以申请无限的长度
•   插入删除较为方便 （在链表的数据结构上进行增删，相比较数组而言较为方便，不需要像数组一样整体移动元素
•   索引元素较为麻烦 （链式存储在索引元素时较为麻烦，如果采用遍历方式寻找，有着较高的时间复杂度，当数据较多时链式一般采用采用二叉搜索树的形式进行存储)  

2、LinkedList数据结构

        和普通链表相似，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;

         在LinkedList中每个节点元素都是以Node形式储存，在LinkedList中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;
        }
    }

        由Node的定义可知，在java的LinkedList中其以一个双向链表的形式存储并使用

3、LinkedList构造方法与核心方法

        构造方法：

    //无参构造方法
	 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
     */
	 //创建一个链表序列，并将指定集合C中的元素放入链表序列中
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

        add方法：

    //在链表中增加一个元素
	public boolean add(E e) {
		//在没有指定位置的情况下，默认将新增元素放入链表的最后位置
        linkLast(e);
        return true;
    }
	
	//将指定的元素e放入链表的最后位置
	 void linkLast(E e) {
        final Node<E> l = last;
		//存放最后的位置，e节点的前驱为l，后继为null
        final Node<E> newNode = new Node<>(l, e, null);
		
		//更新最后一个节点的信息
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
		
		//更新长度
        size++;
        modCount++;
    }

        在指定位置添加数据add(int index，E e)方法

    //在指定的索引位置插入一个元素
	public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
	
	 /**
     * 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;
        }
    }
	
	/**
     * Inserts element e before non-null Node succ.
     */
	 //在一个为空节点succ前插入指定节点e
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
		//执行插入操作
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
		
		//更新长度等数据
        size++;
        modCount++;
    }

        获取指定位置的元素get(int index)

    //获取指定位置的元素
	 public E get(int index) {
		 
        checkElementIndex(index);
		
		//获取指定位置的元素信息，不包含前驱与后继节点位置
        return node(index).item;
    }

        获取首尾元素的值

    //获取首尾节点的元素值
	 public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

        未完待续.............

        附：以上皆由作者原创，转载请注明出处