LinkedList源码解析

目标

• 
  
• 理解LinkedList底层数据结构
  
• 深入源码掌握LinkedList查询慢，新增快的原因
  

1.简介

List 接口的链接列表实现。实现所有可选的列表操作，并且允许所有元素（包括 null ）。除了实现 List 接口外， LinkedList 类还为在列表的开头及结尾 get 、 remove 和 insert 元素提供了统一 的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

特点 :

• 
  
• 有序性 : 存入和取出的顺序是一致的
  
• 元素可以重复
  
• 含有带索引的方法
  
• 独有特点 : 数据结构是链表，可以作为栈、队列或者双端队列！
  

2.LinkedList原理分析

双向链表

底层数据结构源码

public class LinkedList<E> {

    transient int size = 0;

    //双向链表的头结点

    transient Node<E> first;

    //双向链表的最后一个节点

    transient Node<E> last;


    //节点类【内部类】

    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;

        }

    } /

            /...

}

2.1 LinkedList的数据结构

LinkedList是双向链表，在代码中是一个Node类。内部并没有数组的结构。双向链表肯定存在一个头节 点和一个尾部节点。node节点类，是以内部类的形式存在于LinkedList中的。Node类都有两个成员变 量:

• 
  
• prev : 当前节点上一个节点，头节点的上一个节点是null
  
• next : 当前节点下一个节点，尾结点的下一个节点是null
  

链表数据结构的特点 : 查询慢，增删快！

• 
  
• 链表数据结构基本构成，是一个node类
  
• 每个node类中，有上一个节点【prev】和下一个节点【next】
  
• 链表一定存在至少两个节点，first和last节点
  
• 如果LinkedList没有数据，first和last都是为null
  

2.2 LinkedList默认容量&最大容量

没有默认容量，也没有最大容量

2.3 LinkedList扩容机制

无需扩容机制，只要你的内存足够大，可以无限制扩容下去。前提是不考虑查询的效率。

2.4 为什么LinkedList查询慢，增删快？

LinkedList的数据结构的特点，链表的数据结构就是这样的特点！

• 
  
• 链表是一种查询慢的结构【相对于数组来说】
  
• 链表是一种增删快的结构【相对于数组来说】
  

2.5 LinkedList源码剖析-为什么增删快？

新增add

//想LinkedList添加一个元素

public boolean add(E e){

//连接到链表的末尾

        linkLast(e);

        return true;

        }/

        /连接到最后一个节点上去

        void linkLast(E e){

//将全局末尾节点赋值给l

final Node<E> l=last;

//创建一个新节点 : (上一个节点, 当前插入元素, null)

final Node<E> newNode=new Node<>(l,e,null);

//将当前节点作为末尾节点

        last=newNode;

//判断l节点是否为null

        if(l==null)

//既是尾结点也是头节点

        first=newNode;

        else

//之前的末尾节点，下一个节点时末尾节点！

        l.next=newNode;

        size++;//当前集合的元素数量+1

        modCount++;//操作集合数+1。modCount属性是修改技术器

        }/

        /------------------------------------------------------------------

//向链表中部添加

//参数1，添加的索引位置，添加元素

public void add(int index,E element){

//检查索引位是否符合要求

        checkPositionIndex(index);

//判断当前所有是否是存储元素个数

        if(index==size)//true，最后一个元素

        linkLast(element);

        else

//连接到指定节点的后面【链表中部插入】

        linkBefore(element,node(index));

        }/

        /根据索引查询链表中节点！

        Node<E> node(int index){

// 判断索引是否小于 已经存储元素个数的1/2

        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;

        }

        }/

        /将当前元素添加到指定节点之前

        void linkBefore(E e,Node<E> succ){

        // 取出当前节点的前一个节点

        final Node<E> pred=succ.prev;

        //创建当前元素的节点 : 上一个节点，当前元素，下一个节点

        final Node<E> newNode=new Node<>(pred,e,succ);

        //为指定节点上一个节点重新值

        succ.prev=newNode;

//判断当前节点的上一个节点是否为null

        if(pred==null)

        first=newNode;//当前节点作为头部节点

        else

        pred.next=newNode;//将新插入节点作为上一个节点的下个节点

        size++;//新增元素+1

        modCount++;//操作次数+1

        }

remove删除指定索引元素

//删除指定索引位置元素

public E remove(int index){

//检查元素索引

        checkElementIndex(index);

//删除元素节点，

//node(index) 根据索引查到要删除的节点

//unlink()删除节点

        return unlink(node(index));

        }//根据索引查询链表中节点！

        Node<E> node(int index){

// 判断索引是否小于 已经存储元素个数的1/2

        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;

        }

        }/

        /删除一个指定节点

        E unlink(Node<E> x){

//获取当前节点中的元素

final E element=x.item;

//获取当前节点的上一个节点

final Node<E> next=x.next;

//获取当前节点的下一个节点

final Node<E> prev=x.prev;

//判断上一个节点是否为null

        if(prev==null){

//如果为null，说明当前节点为头部节点

        first=next;

        }else{

//上一个节点，的下一个节点改为下下节点

        prev.next=next;

//将当前节点的上一个节点置空

        x.prev=null;

        }/

        /判断下一个节点是否为null

        if(next==null){

//如果为null，说明当前节点为尾部节点

        last=prev;

        }else{

//下一个节点的上节点，改为上上节点

        next.prev=prev;

//当前节点的上节点置空

        x.next=null;

        }/

        /删除当前节点内的元素

        x.item=null;

        size--;//集合中的元素个数-1

        modCount++;//当前集合操作数+1。modCount计数器，记录当前集合操作次数

        return element;//返回删除的元素

        }

2.6 LinkedList源码剖析-为什么查询慢？

查询快和慢是一个相对概念！相对于数组来说

//根据索引查询一个元素

public E get(int index){

//检查索引是否存在

        checkElementIndex(index);

// node(index)获取索引对应节点，获取节点中的数据item

        return node(index).item;

        }/

        /根据索引获取对应节点对象

        Node<E> node(int 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;

        }

        }/

        /查看ArrayList里的数组获取元素的方式

public E get(int index){

        rangeCheck(index);//检查范围

        return elementData(index);//获取元素

        }E

        elementData(int index){

        return(E)elementData[index];//一次性操作

        }