400-616-5551

您所在位置: 首页> 学习课程> java培训 | Java集合框架——LinkedList源码分析

java培训 | Java集合框架——LinkedList源码分析

发布百知教育 来源:学习课程 2019-11-11

LinkedList的源码分析

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

LinkedList的结构图示:


1.png

从结构图中,可以看的出来以下信息:

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

LinkedList中的源码解释:

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

  1. /**

  2.    存储数据的内部类,用于创建结点

  3. */

  4. private static class Node<E> {

  5.    E item;

  6.    Node<E> next;

  7.    Node<E> prev;


  8.    //内部类构造方法,传入参数前结点,要添加的元素和后结点

  9.    Node(Node<E> prev,E element,Node<E> next){

  10.        this.item = element;

  11.        this.next = next;

  12.        this.prev = prev;

  13.    }

  14. }


一、字段

1、int size = 0:记录LinkedList集合容器中的实际存储的元素个数
2、Node
first:记录双向链表中的头结点
3、Node
last:记录双向链表中的尾结点

二、构造方法

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






上一篇:java培训 | Spring Boot 2.2.1 发布,一个有点坑的版本!

下一篇:应届生去公司找个Java程序员的职位需要什么技能?

相关推荐

www.baizhiedu.com

有位老师想和您聊一聊

关闭

立即申请