LinkedList的源码分析

LinkedList的数据结是双向链表，因为是链表结构，所以LinkedList更加适用于增删频繁而查询修改不频繁的场景，其适用场景和ArrayList有一些相反的。

LinkedList的结构图示：

从结构图中，可以看的出来以下信息：

1、实现了List接口：可以使用List接口中的所有方法。
2、实现了Cloneable接口，因此LinkedList支持克隆，但是只支持浅克隆，在LinkedList类中，其中的内部类Node并没有被克隆，只是调用了Object类中的clone方法进行可克隆。
3、实现了Serializable接口，因此LinkedList支持可序列化。
4、实现了Deque接口，实现了Deque的可选操作。
5、继承了AbstractSequentialList抽象类，在遍历的时候，推荐使用迭代器进行遍历。

LinkedList中的源码解释：

一、LinkedList源码的核心组成：用来存储数据的结点，在LinkedList中设计成了内部类

/**
    存储数据的内部类，用于创建结点
*/
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、int size = 0:记录LinkedList集合容器中的实际存储的元素个数
2、Nodefirst:记录双向链表中的头结点
3、Nodelast:记录双向链表中的尾结点

二、构造方法

LinkedList的构造方法只提供了两个，和ArrayList相比，没有初始化容量的构造方法，这主要是因为ArrayList是数组，传入初始容量是为了创建一个具有初始长度的数组，而LinkedList是链表结构，每次新增都是在原有结点后面链接上，因此没有初始容量的构造函数

1、无参构造

/**    无参构造方法*/public LinkedList(){}/**    有参构造方法：将一个容器作为参数传入*/public LinkedList(Collection<? extends E> c){    //首先调用无参构造函数    this();    //然后调用addAll(c);将传入的参数集合中元素全部添加到新创建的LinkedList容器中    addAll(c);}

三、LinkedList常用方法实现

1、添加元素

1） 添加单个元素:add(E e)

/**添加的方法*/public boolean add(E e){    //调用添加在最后的方法    linkLast(e);    return true;}//添加在最后的方法void linkLast(E e){    //要将添加的e元素添加在最后，就先记录原来的last元素，指向给l    final Node<E> l = last;    //新建一个结点，将e元素封装进去,前结点为l，元素为e，后元素没有为null    final Node<E> newNode = new Node<>(l,e,null);    //将新结点设置为最后结点    last = newNode;    //判断原尾结点l是否为null    if(l == null){        //如果为null，则说明还没有元素，则新结点就为头结点        first = newNode;    }else{        //否则将原结点的next指向新结点        l.next = newNode;    }    //实际元素个数增加1    size++;    //操作次数加1    modCount++;}

2）在尾部添加一个元素

/**    在链表的尾部添加一个元素*/public void addLast(E e){    //直接调用在尾部添元素的方法linkLast(E e)，源码在上面已经描述，不再重复。    linkLast(E e);}

3）在第一个位置添加元素

/**    在LinkedList容器中第一个位置添加元素*/public void addFirst(E e){    //直接调用linkFirst(e);    linkFirst(e);}//在第一个位置添加元素的方法private void linkFirst(E e){    //记录原头元素    final Node<E> f = first;    //新建一个结点，前元素为null，next指向原头元素f    final Node<E> newNode = new Node<>(null,e,f);    //将头结点设置为newNode    first = newNode;    //判断原头结点f是否为null，    if(f == null){        //如果为null,则头结点和尾结点都应该是newNode        last = newNode;    }else{        //否则原头结点的前结点设置为newNode        f.prev = newNode;    }    //实际元素个数增加1；    size++;    //操作次数增加1    modCount++;}

4）在指定索引处添加元素

/**    在指定索引出的位置添加元素*/public void add(int index,E element){    //判断传入的索引参数是否合法    checkPositionIndex(index);    //判断传入的索引index是否是最后一个位置，和size比较即可    if(index == size){        //直接将元素添加在尾部        linkLast(element);    }else{        //否则添加在指定索引位置        linkBefore(element,node(index));    }}//在执行索引位置添加元素的方法,在非空的succ结点之前添加元素。void linkBefore(E element,Node<E> succ){    //声明一个结点，暂时记录succ结点的前结点，因为新结点需要添加在succ的前面    final Node<E> pred = succ.prev;    //新建一个结点，并且新结点的前指向pred，后结点指向当前结点succ    final Node<E> newNode = new Node<E>(prev,element,succ);    //判断succ指向的原前结点pred是否为空    if(pred == null){        //如果为空，则说明前面没有元素，那新结点就为头结点        first = newNode;    }else{        //否则记录的succ原前结点pred的next指向新结点newNode即可        pred.next = newNode;    }    //实际元素个数增加1    size++;    //实际操作次数增加1    modCount++:}//根据传入索引计算要插入位置的结点元素Node<E> node(int index){    //在LinkedList集合容器中，对遍历元素进行了优化，判断传入的index索引是靠近尾结点还是头结点位置    if(index < (size >>1)){        //从头结点开始遍历，一直遍历到index指定索引处        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;    }}

2、删除的方法

1）删除LinkedList集合容器中的指定元素

public boolean remove(Object obj){    //判断传入的元素obj是否为null    if(obj == null){        //遍历LinkList中的所有结点        for(Node<E> x = first;x!= null;x = x.next){            //如果x结点的元素值等于null，则删除该结点            if(x.item == null){                //删除结点                unlink(x);                return true;            }        }    }else{        //否则说明传入的元素obj的值不为null        for(Node<E> x = first;x != null;x = x.next){            //是否为null的差别在这里            if(obj.equals(x.item)){                //删除该结点                unlink(x);                return true;            }        }    }    //否则返回false    return false;}//删除结点的方法E unlink(Node<E> x){    //定义一个变量来记录当前要删除结点的值，因为最后要返回去    final E element = x.item;    //定义一个结点变量来记录该结点的后结点    final Node<E> next = x.next;    //定义一个结点变量，用来记录该结点的前结点    final Node<E> prev = x.prev;    //判断待删除结点x的前结点是否为null，如果为null，则待删结点的后结点next设置为头结点    if(prev == null){       first = next;     }else{        //否则将待删结点x的前结点和后结点连接起来        prev.next = next;        //并将待删结点x的前结点置为null,相当于断开连接        x.prev = null;    }    //判断待删除结点的next结点是否为null    if(next == null){        //直接将待删除结点设置为尾结点即可        last = prev;    }else{        //否则待删结点x的后结点的prev指向待删结点的前结点        next.prev = prev;        x.next = null;    }    //将待删结点的元素值设置为null    x.item = null;    //实际长度减少1    size--;    //操作增加1    modCount++;    //返回待删结点的原元素值    return element;}

2）清空LinkedList集合框架中的所有元素

/***   清空LinkedList集合中的所有元素*/public void clear(){    //遍历LinkedList集合容器中的所有元素，将所有的结点都置为null    for(Node<E> x = first;x != null){        Node<E> next = x.next();        x.item = null;        x.next = null;        x.prev = null;    }    //将头结点和尾结点全部置为null    first = last = null;    //实际元素设置为0    size = 0;    //操作次数增加1    modCount++:}

3）删除指定索引位置的结点

/***   根据传入的索引位置删除元素*/public E remove(int index){    //校验用户名是否合法    checkElementIndex(index);    //直接返回删除的方法，上面已经介绍，就不再重复分析    return unlink(node(index));}

3、查询元素

1）根据索引查询所在位置的元素

/***   根据索引位置查询该位置的元素值*/public E get(int index){    //校验用户名是否合法    checkElementIndex(index);    //返回结点的元素值，其中使用到node(index)上面已经介绍，不再重复介绍。    return node(index).item;}

4、修改结点元素

1）根据索引位置设置元素值

/***  根据索引值设置索引值*/public E set(int index,E element){    //校验索引位置是否合法    checkElementIndex(index);    //根据索引获取该结点    Node<E> x = node(index);    //定义变量用来记录原结点的元素值    E oldVol = x.item;    //用传入的元素值替换原来的元素值    x.item = element;    //将原结点的元素值返回    return oldVol;}

java培训：http://www.baizhiedu.com/java2019