初识Linkedlist底层

前言

LinkedList底层是基于双端链表实现的，也就是说它具有指向其前驱与后继的引用，而且，在插入与删除数据时效率极高

至于它继承谁和实现什么接口，直接看源码

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

和ArrayList一样，从源码分析其add、get以及remove方法

add方法

首先通过MyEclipse进入LinkedList的源码

找到add（）方法

public boolean add(E e) {
 //把e放在链表的最后一个位置
       linkLast(e);
       return true;
   }

找到linkLast（）方法

/**
    * Pointer to last node.
    * Invariant: (first == null && last == null) ||
    *            (last.next == null && last.item != null)
    */
   transient Node<E> last; //链表最后一个结点的引用

   transient Node<E> first; //链表第一个结点的引用


void linkLast(E e) {
       //将l也指向最后一个结点
       final Node<E> l = last;

       //调用Node（Node<E> prev，E element，Node<e> next）构造方法
       //其中prev为前驱结点，element为对象元素，next为后继结点
       //这里构造新节点，并且是作为尾节点
       final Node<E> newNode = new Node<>(l, e, null);

       //last结点指向newNode
       last = newNode;

       //如果l为空，则表示链表为空，直接把newNode作为首节点，否则放在l结点之后
       if (l == null)
           first = newNode;
       else
           l.next = newNode;

        //链表的元素个数加一
       size++;

       //链表发生结构性修改的次数，这里主要指添加及删除操作
       modCount++;
   }

以上便是add方法的源码，主要通过改变链表的前驱及后继引用来完成插入，可想而知，使用链表，使插入数据的速度异常快，相对顺序查找

get方法

找到get方法

public E get(int index) {

     //检查index是否合法
       checkElementIndex(index);

     //如果合法就返回该节点位置的值
       return node(index).item;
   }

找到checkElementIndex(int index)方法

private void checkElementIndex(int index) {
    //检查index是否合法
       if (!isElementIndex(index))
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }

找到isElementIndex(index)方法

//判断index是否存在于链表中
private boolean isElementIndex(int index) {
       return index >= 0 && index < size;
   }

找到node(int index)方法

Node<E> node(int index) {
    //index已在链表中
    // assert isElementIndex(index);
    //从第一个位置开始寻找，知道找到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在查找时的效率非常低，就是因为它是从头或从尾部遍历链表，所以当数据量大时，造成效率低下

remove方法

找到remove方法

public E remove(int index) {
      //检查index是否合法
        checkElementIndex(index);


        return unlink(node(index));
    }

找到unlink(node(index))方法

 E unlink(Node<E> x) {
        // assert x != null;
        //保存x节点的值
        final E element = x.item;
        //保存x节点的后继
        final Node<E> next = x.next;
        //保存x节点的前驱
        final Node<E> prev = x.prev;

       //如果前驱为空，则表明要移除的是第一个结点，在把first指向下一个节点
        if (prev == null) {
            first = next;
        } else {
        	//否则把x前驱的后继指向x的后继，并把x前驱设置为null
            prev.next = next;
            x.prev = null;
        }

 //如果后继为空，则表明要移除的是最后一个结点，在把last引用指向x的前驱
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

//把x结点的值设置为null，保证x没有任何引用了
        x.item = null;

 //链表的size减一
        size--;

   //链表的结构性修改次数加一
        modCount++;

   //这里该节点移除之前以保存在element中，然后返回该节点
        return element;
    }

至此，简单把上面三个方法的源码简单过了一遍
当然，还有一点不得不提的是LinkedList可以当做stack（栈），queue（队列）处理，因为它是双端链表，另外，在遍历时，有index < (size >> 1)，即判断index与size/2比较，这样可以缩小范围，选择是从前遍历还是从后遍历，从而大大增加查找效率