精华内容
下载资源
问答
  • Java集合源码分析

    2019-08-02 10:06:05
  • java集合源码分析

    2016-03-09 16:49:07
    .Java中的集合位于java.util包下,主要的结构如下: 2.集合中存放的都是对象的引用而不是对象本身。集合中不能放入原生数据类型,要放入原生数据类型,可以将其转化成包装类型后再放入,不过JDK1.5出现了自动的...
    .Java中的集合位于java.util包下,主要的结构如下:
    

    java集合源码分析
    2.集合中存放的都是对象的引用而不是对象本身。集合中不能放入原生数据类型,要放入原生数据类型,可以将其转化成包装类型后再放入,不过JDK1.5出现了自动的装箱和拆箱,原生数据类型可以直接放入,java自动会将原生数据类型包装成包装类型后放入。
    3.ArrayList底层代码如下:
    java集合源码分析
    由上面代码可以看到ArrayList的带参数的构造方法就是new了一个传入长度的Object数组,而不带参数的构造方法就是默认new一个长度为10的Object数组。因此ArrayList的底层就是一个Object数组。

    java集合源码分析
    以上的add方法,先判断size 1是否大于了ArrayList底层数组的最大容量,如果大于,那么将新new一个长度是原来长度的3/21长度的数组,然后再将原数组copy到新数组中去。将新数组保存到底层数组中

    5.ArrayList中还提供了可以转成数组的方法,如下:

    java集合源码分析
    6.ArrayList中提供了删除某一位置的元素的方法如下

    java集合源码分析
    7.ArrayList类中提供的获取某一位置的元素的方法比较简单如下:

    java集合源码分析
    8.由上面的源码可以看出来ArrayList就是利用数组实现的一个轻量级的集合,该集合是线程不安全的,如果在多线程的环境中使用,需要自行考虑线程安全问题。

    9.Vector(向量)和ArrayList差不多,都是继承自AbstractList,底层都是用数组实现的, 但是与ArrayList相比Vector明显显得笨重了些,因为,Vector底层考虑了线程同步的问题,在方法定义时都加上了synchronized关键字,所以是线程安全的,还有一个区别是,当Vector中容量装满后,如果还往里面加元素那么,就会在底层生成一个原数组两倍容 量的数组,再将原数组拷贝到新数组中去,而在ArrayList中这个新数组长度是原数组的3/2倍1的长度。很明显在非多线程的环境下轻量级的ArrayList性能比Vector快。具体细节可以看底层源码。

    10.Stack(栈):栈是一种先进后出的集合,直接继承自Vector,所有也是线程安全的。先进先出就是一个只有一头开口的盒子,放进一个东西就放在最里面了,要拿出来只能 是上面的都拿完了才能拿出来。需要注意的是Stack类中的几个方法:

      1)压栈的方法(就是放入数据的方法):push方法的源码如下

      java集合源码分析
        java集合源码分析

        由上可以看出数据放入Stack中,其实就是直接将数据赋给了栈底层(Vector 底层)维护的数组中,这个
       时候数据(其实是引用)是直接放入栈中,而不是数据的拷贝放入栈中了,那么这样就会有一个后果就是
       对元数据的任何操作都是会直接影响栈中存放的数据,如下代码(省略一部分代码)

       java集合源码分析

       运行会打印一个zhangsan一个lisi,其中上面的peek方法是获得最上面的一个元素,也就是最后放进去的一
       个元素。
      有很多的情况是不希望出现这样的结果的,那么使用这个Stack后,就必须注意不要在原数据上修改了。也可
       以自己实现一个自己的栈。

      2)查看栈顶的元素:peek()是查看栈顶的一个元素的方法,栈顶就是最上面的一个元素也就是最后压入的一
       个元素。
     3)移除并返回栈顶的元素:pop()是移除栈顶的一个元素的方法,也就是移除栈中最后压入的一个元素
     4)判断栈中是否为空:empty()是判断栈中是否为空
     5)搜索栈中的元素:search(Object o),返回一个元素的位置,栈顶位置为1.

    11.LinkedList(链接列表):链接列表底层是数据结构中的链表结构。

    12.单向链表示意图如下

    java集合源码分析

    如图所示单项链表是一个数据加上后一个数据的引用一对对出现的,一个是本身数据还有一个是指向它的后继元素的引用。用代码表示一个简单的链表如下:

    java集合源码分析
    java集合源码分析
    13.循环链表的示意图如下所示

    java集合源码分析
    14.双向循环链表示意图如下
    java集合源码分析
    比单向链表多了一个前面的引用,既有指向前驱的元素的引用又有指向后继元素的引用

    java集合源码分析
    15.LinkedList的底层主要代码如下:
       1)成员变量和构造方法

        java集合源码分析
        上面代码中的Entry对象就是上面实现双向链表的那个类,由上可见,调用LinkedList的不带参数的构造方
       法生成的是一个长度为一的指向自身的空的循环链表。由上面可以看出LinkedList底层数据直接维护的仅仅
       是链表头(第一个元素)代表的Entry对象,那么后面跟着的对象都是由Entry对象里的前驱和后继引用表示
       的,由构造方法可以看出LinkedList底层是一个双向的循环链表。既然是双向循环链表那么任何一个链表对
       象的头元素的前驱元素必然是该链表的尾部元素。

       2)在链表尾部添加一个元素的方法:add(Ee)源码如下:

        java集合源码分析
    java集合源码分析
      3)删除某个索引位置的元素

      java集合源码分析
     java集合源码分析
       java集合源码分析
    16.由上源码可以分析比较出ArrayList和LinkedList的区别:

      1)ArrayList底层采用数组实现,LinkedList底层采用双向循环链表实现。
     2)当执行插入或者删除操作时,采用LinkedList效率比较高,它只需要改变它前后两个元素的后继和前驱
      引用就行了,也不涉及到扩容问题,而ArrayList是顺序结构的所以需要大量的移动元素,而且当插入元素
       的数量超过当前容量时,在底层还会new一个1.5倍1长度的新数组,然后再将旧数组的所有元素copy到
       新数组中。
     3)当执行搜索操作时,ArrayList效率较高,
     4)当向ArrayList添加一个对象时,实际上是将该对象的引用放置到了ArrayList底层所维护的数组中;而
      向LinkedList中添加一个对象时,实际上LinkedList内部会生成一个Entry对象,该对象的结构是

        class Entry {
         Entry previous;//前驱引用,指向前一个元素的引用
         Object element;//需要添加的元素
         Entry next;//后继引用,指向下一个元素的引用
      }
     最后将这个Entry对象加入到链表当中,在一个链表中直接维护的仅仅是一个代表链表头的Entry对象,链
      表中的其它对象都是由该对象前驱引用或者是后继引用这样一层层往前或往后可以找到的。
    17.和List不同Set是一类不包含重复元素的集合,实现该接口的主要几个类是HashSet,LinkedHashSet和TreeSet。这些类在介绍了映射后再看就简单了,这里先不做介绍。

    18.集合的遍历:集合的遍历主要有三种方式:
       1)使用简单for循环:

        java集合源码分析
       当然这种for循环还有很多不同的写法,就不多说了。
       2)使用迭代器

       java集合源码分析

      模仿for循环上面的迭代器还存在几个写法不同的变种,其实是一个意思
       java集合源码分析

      上面代码就是将初始化过程放在循环外面了。执行流程完全一样

      java集合源码分析
     上面这个可能很少见到,但是模仿简单for循环的执行流程就很清楚了,上面的初始化仍然可以放在外面

      java集合源码分析
     上面这个更狠,for后面的括号里面就有两个分号了,其它的都放在外面了,由上面的发现for循环的写法
      是非常活的,只要自己习惯怎么写就怎么写,其实上面的几种方式效果是一样的。

      3)增强for循环:

      java集合源码分析
     刚看见上面的代码可能不好理解,现在我们将上面的代码生成的.class文件放在反编译软件XJad中反编译后
      得出如下代码
    java集合源码分析
       也就是说增强for循环针对这种集合底层就是使用迭代器,只是简化了我们的操作由上面可以看出增强for循
       环支持泛型,大大降低了代码的简洁性。
      4)对增强for循环可能会有疑问:数组不能使用迭代器迭代,为什么可以使用增强for循环呢?看下面的例子
       就知道了。

       java集合源码分析
       将上面代码产生的class文件进行反编译,如下

       java集合源码分析

      那么可以看出增强for循环针对数组的底层是简单for循环,由上面可以看出针对和数组具有同样的线性结构
       的ArrayList的增强for循环都是使用的迭代器,链式结构就更不用说了,那么我可以大胆猜测增强for循环针
       对不能迭代的数组底层是简单for循环,针对可以迭代的集合底层就是迭代的方式了。这个我没有一一验证,
       如果不确定可以自己试试。

    19.关于集合遍历的时候删除满足特定条件的元素的问题

       1)简单for循环遍历删除

       java集合源码分析
       上面的方式完全没问题

       2)迭代器遍历删除

       java集合源码分析
      上面的代码是使用迭代器自己的删除方法删除该元素也是没有问题的。但是往往我们会习惯性的写成

      java集合源码分析
       那么错误也会随之而来如下

       java集合源码分析

     看看上面报的错误,首先我们知道一般编译后内部类的名字都是:类名$内部类名,那么这样我们上上面的错
      误就很好理解了,就是AbstractLIst类里面的Itr内部类的
      checkForComodification方法有问题,源码如下
       java集合源码分析
      由上面代码知道根源在modCount和expectedModCount不相同才产生了异常。modCount表示数据被修改
      的次数,而expectedModCount是迭代器里面使用的变量表示迭代器期望的集合数据被修改的次数,对于迭
      代器来说,为了遍历方便他当然希望这个次数就是他迭代集合之前的modCount,而expectedModCount只
      有在获得集合迭代器的时候或者是由迭代器修改数据(包括删除)的时候expectedModCount才会和
      modCount同步,所以在迭代的时候通过集合本身的方法添加或删除集合的元素都会使这两个参数不同步,如
      上面那个产生异常的原因是调用了集合本身的remove方法时modCount变化了,但是expectedModCount没
       有变化,所以抛出异常。内部类Itr的代码如下
       java集合源码分析
       3)增强for循环遍历删除:针对集合来说,增强for循环底层是使用迭代器遍历的,但是它是将迭代器封装
      在了增强for循环里面,在循环里面没法拿到那个迭代器,因此无法靠一个增强for循环删除集合中的指定元
       素,不过可以使用两个for循环达到目的如下:

     

      java集合源码分析
    20.对于各种遍历方式的粗略的性能试验:
    java集合源码分析
    (进行20次左右测试)运行结果如下
     java集合源码分析
     上面的实验结果从一定程度上说明了,简单for循环在大数据量遍历的时候性能优于迭代器迭代,所以在能够使用遍历索引方式遍历(简单for循环)的线性结构的集合和数组的时候尽量使用简单for循环,不要装那个啥的使用迭代器,虽然在数据量不是很大的时候差距不大,但是迭代器遍历的同时修改数据很容易因为习惯使代码出现异常就像上面那样。当然对于那种链式结构(LinkedList)这样的集合,我们只能使用迭代器或者是增强for循环了。不过在要求不高的场合,还是可以根据习惯选择遍 历方式。


    展开全文
  • 概述List 应该接口是 Collection 最常被使用的接口了。...从线程安全来说,List 下拥有线程安全的集合类 Vector;从数据结构来说,List 下拥有基于数组实现的 Vector 与 ArrayList,和基于链表实现的 Linked...

    概述

    List 应该接口是 Collection 最常被使用的接口了。其下的实现类皆为有序列表,其中主要分为 Vector,ArrayList,LinkedList 三个实现类,其中 Vecotr 又拥有子类 Stack。

    从线程安全来说,List 下拥有线程安全的集合类 Vector;从数据结构来说,List 下拥有基于数组实现的 Vector 与 ArrayList,和基于链表实现的 LinkedList。

    本篇文章暂不讨论具体的实现类,而将基于 List 接口与其抽象类 AbstractList,了解 List 接口是如何承上启下,进一步从 Collection 抽象到具体的。

    这是关于 java 集合类源码的第二篇文章。往期文章:

    java集合源码分析(一):Collection 与 AbstractCollection

    一、List 接口

    8aa3320984a4ccfb1b8d22abe8592d4d.png

    List 接口的方法

    List 接口继承了 Collection 接口,在 Collection 接口的基础上增加了一些方法。相对于 Collection 接口,我们可以很明显的看到,List 中增加了非常多根据下标操作集合的方法,我们可以简单粗暴的分辨一个方法的抽象方法到底来自 Collection 还是 List:参数里有下标就是来自 List,没有就是来自 Collection。

    可以说,List 接口在 Collection 的基础上,进一步明确了 List 集合运允许根据下标快速存取的特性。

    1.新增的方法

    get():根据下标获取指定元素;

    replaceAll():参数一个函数式接口UnaryOperator,这个方法允许我们通过传入的匿名实现类的方法去对集合中的每一个类做一些处理以后再放回去;

    sort():对集合中的数据进行排序。参数是 Comparator super E>,这个参数让我们传入一个比较的匿名方法,用于数组排序;

    set():用指定的元素替换集合中指定位置的元素;

    indexOf():返回指定元素在此列表中首次出现的索引;如果此列表不包含该元素,则返回-1;

    lastIndexOf():返回指定元素在此列表中最后一次出现的索引,否则返回-1;

    listIterator():这个是个多态的方法。无参的 listIterator()用于获取迭代器,而有参的 listIterator()可以传入下标,从集合的指定位置开始获取迭代器。指定的索引指示首次调用next将返回的第一个元素。

    subList():返回此列表中指定的两个指定下标之间的集合的视图。注意,这里说的是视图,因而对视图的操作会影响到集合,反之亦然。

    2.同名的新方法

    add():添加元素。List 中的 add() 参数的(int,E),而 Collection 中的 add() 参数是 E,因此 List 集合中同时存在指定下标和不指定下标两种添加方式;

    remove():删除指定下标的元素。注意,List 的 remove() 参数是 int ,而 Collection 中的 `remove() 参数是 Objce,也就是说,List 中同时存在根据元素是否相等和根据元素下标删除元素两种方式。

    3.重写的方法

    spliterator():List 接口重写了 Collection 接口的默认实现,换成了根据顺序的分割。

    二、AbstractList 抽象类

    AbstractList 类是一个继承了 AbstractCollection 类并且实现了 List 接口的抽象类,它相当于在 AbstractCollection 后的第二层方法模板。是对 List 接口的初步实现,同时也是 Collection 的进一步实现。

    我们可以根据 JavaDoc 简单的了解一下它:

    此类提供List接口的基本实现,以最大程度地减少实现由“随机访问”数据存储(例如数组)支持的此接口所需的工作。 对于顺序访问数据(例如链表),应优先使用AbstractSequentialList代替此类。

    要实现不可修改的列表,程序员只需要扩展此类并为get(int)和size()方法提供实现即可。

    要实现可修改的列表,程序员必须另外重写set(int, E)方法(否则将抛出UnsupportedOperationException )。 如果列表是可变大小的,则程序员必须另外重写add(int, E)和remove(int)方法。

    不像其他的抽象集合实现,程序员不必提供迭代器实现;

    迭代器和列表迭代器由此类在“随机访问”方法之上实现: get(int) , set(int, E) , add(int, E)和remove(int) 。

    1.不支持的实现与抽象方法

    可以直接通过下标操作的set(),add(),remove()都是 List 引入的新接口,这些都 AbstractList 都不支持,要使用必须由子类重写。

    get()由于不能确定子类是链表还是数组,所以此时get()仍然强制要求子类去实现。

    abstract public E get(int index);

    public E set(int index, E element) {

    throw new UnsupportedOperationException();

    }

    public void add(int index, E element) {

    throw new UnsupportedOperationException();

    }

    public E remove(int index) {

    throw new UnsupportedOperationException();

    }

    iterator():获取 Itr 迭代器类;

    listIterator():获取 ListItr 迭代器类。这是个多态方法,可以选择是否从指定下标开始,默认从下标为0的元素开始迭代;

    视图类 SubList 和 RandomAccessSubList:

    subList():获取视图类,会自动根据实现类是否继承 RandomAccess 而返回 SubList 或 RandomAccessSubList。

    这些内部类同样被一些其他的方法所依赖,所以要全面的了解 AbstractList 方法的实现,就需要先了解这些内部类的作用和实现原理。

    三、subList方法与内部类

    subList()算是一个比较常用的方法了,在 List 接口的规定中,这个方法应该返回一个当前集合的一部分的视图:

    public List subList(int fromIndex, int toIndex) {

    // 是否是实现了RandomAccess接口的类

    return (this instanceof RandomAccess ?

    // 是就返回一个可以随机访问的内部类RandomAccessSubList

    new RandomAccessSubList<>(this, fromIndex, toIndex) :

    // 否则返回一个普通内部类SubList

    new SubList<>(this, fromIndex, toIndex));

    }

    这里涉及到 RandomAccessSubList 和 SubList 这个内部类,其中,RandomAccessSubList 类是 SubList 类的子类,但是实现了 RandomAccess 接口。

    1.SubList 内部类

    我们可以简单的把 SubList 和 AbstractList 理解为装饰器模式的一种实现,就像 SynchronizedList 和 List 接口的实现类一样。SubList 内部类通过对 AbstractList 的方法进行了再一次的封装,把对 AbstractList 的操作转变为了对 “视图的操作”。

    通过对原有的 AbstractList 进行包装,将原本对 AbstractList 操作的方法改为了对 SubList 的操作的方法,是适配器模式思想的一种体现。

    我们先看看 SubList 这个类的成员变量和构造方法:

    class SubList extends AbstractList {

    // 把外部类AbstractList作为成员变量

    private final AbstractList l;

    // 表示视图的起始位置(偏移量)

    private final int offset;

    // SubList视图的长度

    private int size;

    SubList(AbstractList list, int fromIndex, int toIndex) {

    if (fromIndex < 0)

    throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);

    if (toIndex > list.size())

    throw new IndexOutOfBoundsException("toIndex = " + toIndex);

    if (fromIndex > toIndex)

    throw new IllegalArgumentException("fromIndex(" + fromIndex +

    ") > toIndex(" + toIndex + ")");

    // 获取外部类的引用

    // 这也是为什么操作视图或者外部类都会影响对方的原因,因为都操作内存中的同一个实例

    l = list;

    // 获取当前视图在外部类中的起始下标

    offset = fromIndex;

    // 当前视图的长度就是外部类截取的视图长度

    size = toIndex - fromIndex;

    this.modCount = l.modCount;

    }

    }

    我们可以参考图片理解一下:

    4439e37512ccd4026068c4ca2dcfb847.png

    image-20201126114026855

    然后 subList 里面的方法就很好理解了:

    public E set(int index, E element) {

    // 检查下标是否越界

    rangeCheck(index);

    // 判断是存在并发修改

    checkForComodification();

    // 把元素添加到偏移量+视图下标的位置

    return l.set(index+offset, element);

    }

    其他方法都差不多,这里便不再多费笔墨了。

    2.RandomAccessSubList 内部类

    然后是 SubList 的子类 RandomAccessSubList:

    class RandomAccessSubList extends SubList implements RandomAccess {

    RandomAccessSubList(AbstractList list, int fromIndex, int toIndex) {

    super(list, fromIndex, toIndex);

    }

    public List subList(int fromIndex, int toIndex) {

    return new RandomAccessSubList<>(this, fromIndex, toIndex);

    }

    }

    我们可以看见,他实际上还是 SubList,但是实现了 RandomAccess 接口。关于这个接口,其实只是一个标记,实现了该接口的类可以实现快速随机访问(下标),通过 for 循环+下标取值会比用迭代器更快。

    Vector 和 ArrayList 都实现了这个接口,而 LinkedList 没有。专门做此实现也是为了在实现类调用的 subList()方法时可以分辨这三者。

    四、iterator方法与内部类

    在 AbstractList 里面,为我们提供了 Itr 和 ListItr 两种迭代器。

    迭代器是 AbstractList 中很重要的一块内容,他是对整个接口体系的顶层接口,也就是 Iterable 接口中的 iterator() 方法的实现,源码中的很多涉及遍历的方法,都离不开内部实现的迭代器类。

    1.迭代器的 fast-fail 机制

    我们知道,AbstractList 默认是不提供线程安全的保证的,但是为了尽可能的避免并发修改对迭代带来的影响,JDK 引入一种 fast-fail 的机制,即如果检测的发生并发修改,就立刻抛出异常,而不是让可能出错的参数被使用从而引发不可预知的错误。

    对此,AbstractList 提供了一个成员变量 modCount,JavaDoc 是这么描述它的:

    已对该列表进行结构修改的次数。

    结构修改是指更改列表大小或以其他方式干扰列表的方式,即正在进行的迭代可能会产生错误的结果。该字段由iterator和listIterator方法返回的迭代器和列表迭代器实现使用。如果此字段的值意外更改,则迭代器(或列表迭代器)将抛出ConcurrentModificationException,以响应下一个,移除,上一个,设置或添加操作。

    面对迭代期间的并发修改,这提供了快速失败的行为,而不是不确定的行为。

    子类对此字段的使用是可选的。如果子类希望提供快速失败的迭代器(和列表迭代器),则只需在其add(int,E)和remove(int)方法(以及任何其他覆盖该方法导致结构化的方法)中递增此字段即可)。

    一次调用add(int,E)或remove(int)不得在此字段中添加不超过一个,否则迭代器(和列表迭代器)将抛出虚假的ConcurrentModificationExceptions。

    如果实现不希望提供快速失败迭代器,则可以忽略此字段。

    这个时候我们再回去看看迭代器类 Itr 的一部分代码,可以看到:

    private class Itr implements Iterator {

    // 迭代器认为后备列表应该具有的modCount值。如果违反了此期望,则迭代器已检测到并发修改。

    int expectedModCount = modCount;

    // 检查是否发生并发操作

    final void checkForComodification() {

    if (modCount != expectedModCount)

    throw new ConcurrentModificationException();

    }

    }

    结合代码,我们就不难理解这个 fast-fail 机制是怎么实现的了:

    AbstractList 提供了一个成员变量用于记录对集合结构性修改的次数,如果子类希望实现并发修改错误的检查,就需要结构性操作的方法里让modCount+1。这样。在获取迭代器以后,迭代器内部会获取当前的modCount赋值给expectedModCount。

    当使用迭代器迭代的时候,每一次迭代都会检测modCount和expectedModCount是否相等。如果不相等,说明迭代器创建以后,集合结构被修改了,这个时候再去进行迭代可能会出现错误(比如少遍历一个,多遍历一个),因此检测到后会直接抛出 ConcurrentModificationException异常。

    ListItr 继承了 Itr ,因此他们都有一样的 fast-fail机制。

    值得一提的是,对于启用了 fast-fail 机制的实现类,只有使用迭代器才能边遍历边删除,原因也是因为并发修改检测:

    2.Itr 迭代器

    现在,回到 Itr 的代码上:

    private class Itr implements Iterator {

    // 后续调用next返回的元素索引

    int cursor = 0;

    // 最近一次调用返回的元素的索引。如果通过调用remove删除了此元素,则重置为-1。

    int lastRet = -1;

    // 迭代器认为后备列表应该具有的modCount值。如果违反了此期望,则迭代器已检测到并发修改。

    int expectedModCount = modCount;

    public boolean hasNext() {

    return cursor != size();

    }

    public E next() {

    checkForComodification();

    try {

    int i = cursor;

    E next = get(i);

    lastRet = i;

    cursor = i + 1;

    return next;

    } catch (IndexOutOfBoundsException e) {

    checkForComodification();

    throw new NoSuchElementException();

    }

    }

    public void remove() {

    if (lastRet < 0)

    throw new IllegalStateException();

    checkForComodification();

    try {

    AbstractList.this.remove(lastRet);

    if (lastRet < cursor)

    cursor--;

    lastRet = -1;

    expectedModCount = modCount;

    } catch (IndexOutOfBoundsException e) {

    throw new ConcurrentModificationException();

    }

    }./*欢迎加入java交流Q君样:909038429一起吹水聊天

    final void checkForComodification() {

    if (modCount != expectedModCount)

    throw new ConcurrentModificationException();

    }

    }

    迭代方法

    除了并发修改检测外,迭代器迭代的方式也出乎意料。我们可以看看 hasNext()方法:

    public E next() {

    // 检验是否发生并发修改

    checkForComodification();

    try {

    int i = cursor;

    E next = get(i);

    lastRet = i;

    cursor = i + 1;

    return next;

    } catch (IndexOutOfBoundsException e) {

    checkForComodification();

    throw new NoSuchElementException();

    }

    }

    这个逻辑其实跟链表的遍历是一样的,只不过指针变成了数组的下标。以链表的方式去理解:

    我们把循环里调用next()之后的节点叫做下一个节点,反正称为当前节点。假如现在有 a,b,c 三个元素:

    当初始化的时候,指向最后一次操作的的节点的指针 lastRet=-1,即当前节点不存在,当前游标 cursor=0,即指向下一个节点 a;

    当开始迭代的时候,把游标的值赋给临时指针 i,然后通过游标获取并返回下一个节点 a,再把游标指向 a 的下一个节点 b,此时 cursor=1,lastRet=-1,i=1;

    接着让lastRet=i,也就是当前指针指向新的当前节点 a,现在 lastRet=0,cursor=1`,完成了对第一个节点 a 的迭代;

    重复上述过程,把节点中的每一个元素都处理完。

    现在我们知道了迭代的方式,cursor和 lastRet 的作用,也就不难理解 remove()方法了:

    public void remove() {

    if (lastRet < 0)

    throw new IllegalStateException();

    checkForComodification();

    try {

    // 调用删除方法

    AbstractList.this.remove(lastRet);

    if (lastRet < cursor)

    // 因为删除了当前第i个节点,所以i+1个节点就会变成第i个节点,

    // 调用next()以后cursor会+1,因此如果不让cursor-1,就会,next()以后跳过原本的第i+1个节点

    // 拿上面的例子来说,你要删除abc,但是在删除a以后会跳过b直接删除c

    cursor--;

    // 最近一个操作的节点被删除了,故重置为-1

    lastRet = -1;

    // 因为调用了外部类的remove方法,所以会改变modCount值,迭代器里也要获取最新的modCount

    expectedModCount = modCount;

    } catch (IndexOutOfBoundsException e) {

    throw new ConcurrentModificationException();

    }

    }

    至于hasNext()方法没啥好说的,如果 cursor已经跟集合的长度一样长了,说明就已经迭代到底了。

    2.ListItr 迭代器

    ListItr 继承了 Itr 类,并且实现了 ListIterator 接口。其中,ListIterator 接口又继承了 Iterator 接口。他们的类关系图是这样的:

    c97caa4d83a2dc858da9482394ceb2e6.png

    ListIterator 的类关系图

    ListIterator 接口在 Iterator 接口的基础上,主要提供了六个新的抽象方法:

    hasPrevious():是否有前驱节点;

    previous():向前迭代;

    nextIndex():获取下一个元素的索引;

    previousIndex():返回上一个元素的索引;

    set():替换元素;

    add():添加元素;

    可以看出来,实现了 ListIterator 的 ListItr 类要比 Itr 更加强大,不但可以向后迭代,还能向前迭代,还可以在迭代过程中更新或者添加节点。

    private class ListItr extends Itr implements ListIterator {

    // 可以自己设置迭代的开始位置

    ListItr(int index) {

    cursor = index;

    }

    // 下一节点是否就是第一个节点

    public boolean hasPrevious() {

    return cursor != 0;

    }

    public E previous() {

    // 检查并发修改

    checkForComodification();

    try {

    // 让游标指向当前节点

    int i = cursor - 1;

    // 使用AbstractList的get方法获取当前节点

    E previous = get(i);

    lastRet = cursor = i;

    return previous;

    } catch (IndexOutOfBoundsException e) {

    checkForComodification();

    throw new NoSuchElementException();

    }

    }

    // 获取下一节点的下标

    public int nextIndex() {

    return cursor;

    }

    // 获取当前节点(下一个节点的上一个节点)的下标

    public int previousIndex() {

    return cursor-1;

    }

    public void set(E e) {

    if (lastRet < 0)

    throw new IllegalStateException();

    checkForComodification();

    try {

    AbstractList.this.set(lastRet, e);

    expectedModCount = modCount;

    } catch (IndexOutOfBoundsException ex) {

    throw new ConcurrentModificationException();

    }

    }

    public void add(E e) {

    checkForComodification();

    try {

    int i = cursor;

    // 往下一个节点的位置添加新节点

    AbstractList.this.add(i, e);

    lastRet = -1;

    cursor = i + 1;

    expectedModCount = modCount;

    } catch (IndexOutOfBoundsException ex) {

    throw new ConcurrentModificationException();

    }

    }

    }

    这里比较不好理解的是下一节点还有当前节点这个概念,其实可以这么理解:cursor游标指定的必定是下一次 next()操作要得到的节点,因此cursor在操作前或者操作后指向的必定就是下一节点,因此相对下一节点,cursor其实就是当前节点,相对下一节点来说就是上一节点。

    也就是说,假如现在有 a,b,c 三个元素,现在的 cursor 为2,也就是指向 b。调用 next()以后游标就会指向 c,而调用previous()以后游标又会指回 b。

    至于lastRet这个成员变量只是用于记录最近一次操作的节点是哪个,跟方向性是无关。

    五、AbstractList 实现的方法

    1.add

    注意,现在现在 AbstractList 的 add(int index, E e)仍然还不被支持,add(E e)只是定义了通过 add(int index, E e)把元素添加到队尾的逻辑。

    // 不指定下标的add,默认逻辑为添加到队尾

    public boolean add(E e) {

    add(size(), e);

    return true;

    }

    关于 AbstractList 和 AbstractCollection 中 add()方法之间的关系是这样的:

    7c0ce2bf1fbdd6d8e5ef4b24d8248c0d.png

    add方法的实现逻辑

    2.indexOf/LastIndexOf

    public int indexOf(Object o) {

    ListIterator it = listIterator();

    if (o==null) {

    while (it.hasNext())

    if (it.next()==null)

    return it.previousIndex();

    } else {

    while (it.hasNext())

    if (o.equals(it.next()))

    return it.previousIndex();

    }

    return -1;

    }./*欢迎加入java交流Q君样:909038429一起吹水聊天

    public int lastIndexOf(Object o) {

    ListIterator it = listIterator(size());

    if (o==null) {

    while (it.hasPrevious())

    if (it.previous()==null)

    return it.nextIndex();

    } else {

    while (it.hasPrevious())

    if (o.equals(it.previous()))

    return it.nextIndex();

    }

    return -1;

    }

    3.addAll

    这里的addAll来自于List 集合的 addAll。参数是需要合并的集合跟起始下标:

    public boolean addAll(int index, Collection extends E> c) {

    rangeCheckForAdd(index);

    boolean modified = false;

    for (E e : c) {

    add(index++, e);

    modified = true;

    }

    return modified;

    }

    这里的 rangeCheckForAdd()方法是一个检查下标是否越界的方法:

    private void rangeCheckForAdd(int index) {

    // 不得小于0或者大于集合长度

    if (index < 0 || index > size())

    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    4.removeRange

    这个方法是 AbstractList 私有的方法,一般被子类用于删除一段多个元素,实现上借助了 ListIter 迭代器。

    protected void removeRange(int fromIndex, int toIndex) {

    ListIterator it = listIterator(fromIndex);

    // 从fromIndex的下一个开始,删到toIndex

    for (int i=0, n=toIndex-fromIndex; i

    it.next();

    it.remove();

    }

    }

    六、AbstractList 重写的方法

    1.equals

    equals()方法比较特殊,他是来自于 Collection 和 List 接口中的抽象方法,在 AbstractList 得中实现,但是实际上也是对 Object 中方法的重写。考虑到 equals()情况特殊,所以我们也认为它是一个重写的方法。

    我们可以先看看 JavaDoc 是怎么说的:

    比较指定对象与此列表是否相等。当且仅当指定对象也是一个列表,并且两个列表具有相同的大小,并且两个列表中所有对应的元素对相等时,才返回true

    然后再看看源码是什么样的:

    public boolean equals(Object o) {

    // 是否同一个集合

    if (o == this)

    return true;

    // 是否实现了List接口

    if (!(o instanceof List))

    return false;

    // 获取集合的迭代器并同时遍历

    ListIterator e1 = listIterator();

    ListIterator> e2 = ((List>) o).listIterator();

    while (e1.hasNext() && e2.hasNext()) {

    E o1 = e1.next();

    Object o2 = e2.next();

    // 两个集合中的元素是否相等

    if (!(o1==null ? o2==null : o1.equals(o2)))

    return false;

    }

    // 是否两个集合长度相同

    return !(e1.hasNext() || e2.hasNext());

    }

    从源码也可以看出,AbstractList 的 equals() 是要求两个集合绝对相等的:顺序相等,并且相同位置的元素也要相等。

    2.hashCode

    hashCode() 和 equals()情况相同。AbstractList 重新定义了 hashCode()

    public int hashCode() {

    int hashCode = 1;

    for (E e : this)

    hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

    return hashCode;

    }

    新的计算方式会获取集合中每一个元素的 hashCode 去计算集合的 hashCode,这可能是考虑到原本情况下,同一个集合哪怕装入的元素不同也会获得相同的 hashCode,可能会引起不必要的麻烦,因此重写了次方法。

    我们可以写个测试看看:

    List list1 = new ArrayList<>();

    list1.add("a");

    System.out.println(list1.hashCode()); // 128

    list1.add("c");

    System.out.println(list1.hashCode()); // 4067

    七、总结

    List 接口继承了 Collection 接口,新增方法的特点主要体现在可以通过下标去操作节点,可以说大部分下标可以作为参数的方法都是 List 中添加的方法。

    AbstractList 是实现了 List 的抽象类,他实现了 List 接口中的大部分方法,同时他继承了 AbstractCollection ,沿用了一些 AbstractCollection 中的实现。这两个抽象类可以看成是模板方法模式的一种体现。

    他提供了下标版的 add(),remove(),set()的空实现。

    AbstractList 内部提供两个迭代器,Itr 和 ListItr,Itr 实现了 Iterator接口,实现了基本的迭代删除,而 ListItr 实现了ListIterator,在前者的基础上增加了迭代中添加修改,以及反向迭代的相关方法,并且可以从指定的位置开始创建迭代器。

    AbstractList 的 SubList 可以看成 AbstractList 的包装类,他在实例化的时候会把外部类实例的引用赋值给成员变量,同名的操作方法还仍然是调用 AbstractList 的,但是基于下标的调用会在默认参数的基础上加上步长,以实现对“视图”的操作,这是适配器模式思想的一种体现。

    AbstractList 引入了并发修改下 fast-fail 的机制,在内部维护一个成员变量 modelCount,默认为零,每次结构性修改都会让其+1。在迭代过程中会默认检查 modelCount是否符合预期值,否则抛出异常。值得注意的是,这个需要实现类的配合,在实现 add()等方法的时候要让 modelCount+1。对于一些实现类,在迭代中删除可能会抛出 ConcurrentModificationExceptions,就是这方面的问题。

    AbstractList 重写了 hashCode()方法,不再直接获取实例的 HashCode 值,而遍历集合,根据每一个元素的 HashCode 计算集合的 HashCode,这样保证了内容不同的相同集合不会得到相同的 HashCode。

    3bde27d3f4b7bdc838c0968d90f837e5.png

    最新2020整理收集的一些高频面试题(都整理成文档),有很多干货,包含mysql,netty,spring,线程,spring cloud、jvm、源码、算法等详细讲解,也有详细的学习规划图,面试题整理等,需要获取这些内容的朋友请加Q君样:909038429

    /./*欢迎加入java交流Q君样:909038429一起吹水聊天

    展开全文
  • Java集合源码分析(二)Linkedlist 阅读目录(Content)一、LinkedList简介1.1、LinkedList概述1.2、LinkedList的数据结构1.3、LinkedList的特性二、LinkedList源码分析2.1、LinkedList的...

    Java集合源码分析(二)Linkedlist

    前言

      前面一篇我们分析了ArrayList的源码,这一篇分享的是LinkedList。我们都知道它的底层是由链表实现的,所以我们要明白什么是链表?

    一、LinkedList简介

    1.1、LinkedList概述

      

      LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列,它是基于双向链表实现的

      LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
      LinkedList 实现 List 接口,能对它进行队列操作。
      LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。
      LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
      LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
      LinkedList 是非同步的。

    1.2、LinkedList的数据结构

      1)基础知识补充

        1.1)单向链表:

          element:用来存放元素

          next:用来指向下一个节点元素

          通过每个结点的指针指向下一个结点从而链接起来的结构,最后一个节点的next指向null

          

        1.2)单向循环链表

          element、next 跟前面一样

          在单向链表的最后一个节点的next会指向头节点,而不是指向null,这样存成一个环

          

        1.3)双向链表

          element:存放元素

          pre:用来指向前一个元素

          next:指向后一个元素

          双向链表是包含两个指针的,pre指向前一个节点,next指向后一个节点,但是第一个节点head的pre指向null,最后一个节点的tail指向null。

          

        1.4)双向循环链表

          element、pre、next 跟前面的一样

          第一个节点的pre指向最后一个节点,最后一个节点的next指向第一个节点,也形成一个“环”

          

      2)LinkedList的数据结构

        

        如上图所示,LinkedList底层使用的双向链表结构,有一个头结点和一个尾结点,双向链表意味着我们可以从头开始正向遍历,或者是从尾开始逆向遍历,并且可以针对头部和尾部进行相应的操作。

    1.3、LinkedList的特性

      在我们平常中我们只知道一些常识性的特点:

        1)是通过链表实现的,

        2)如果在频繁的插入,或者删除数据时,就用linkedList性能会更好。

      那我们通过API去查看它的一些特性

        1)Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).

          这告诉我们,linkedList是一个双向链表,并且实现了List和Deque接口中所有的列表操作并且能存储任何元素,包括null

          这里我们可以知道linkedList除了可以当链表使用,还可以当作队列使用,并能进行相应的操作。

        2)All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

          这个告诉我们,linkedList在执行任何操作的时候,都必须先遍历此列表来靠近通过index查找我们所需要的的值。通俗点讲,这就告诉了我们这个是顺序存取,

          每次操作必须先按开始到结束的顺序遍历,随机存取,就是arrayList,能够通过index。随便访问其中的任意位置的数据,这就是随机列表的意思

        3)api中接下来讲的一大堆,就是说明linkedList是一个非线程安全的(异步),其中在操作Interator时,如果改变列表结构(add\delete等),会发生fail-fast。

      通过API再次总结一下LinkedList的特性:  

        1)异步,也就是非线程安全

        2)双向链表。由于实现了list和Deque接口,能够当作队列来使用。

          链表:查询效率不高,但是插入和删除这种操作性能好。

        3)是顺序存取结构(注意和随机存取结构两个概念搞清楚)

    二、LinkedList源码分析

    2.1、LinkedList的继承结构以及层次关系

      

      分析:

        我们可以看到,linkedList在最底层,说明他的功能最为强大,并且细心的还会发现,arrayList只有四层,这里多了一层AbstractSequentialList的抽象类,为什么呢?

        通过API我们会发现:

          1)减少实现顺序存取(例如LinkedList)这种类的工作,通俗的讲就是方便,抽象出类似LinkedList这种类的一些共同的方法

          2)既然有了上面这句话,那么以后如果自己想实现顺序存取这种特性的类(就是链表形式),那么就继承这个AbstractSequentialList抽象类

            如果想像数组那样的随机存取的类,那么就去实现AbstracList抽象类

          3)这样的分层,就很符合我们抽象的概念,越在高处的类,就越抽象,往在底层的类,就越有自己独特的个性。自己要慢慢领会这种思想。

          4)LinkedList的类继承结构很有意思,我们着重要看是Deque接口,Deque接口表示是一个双端队列,

            那么也意味着LinkedList是双端队列的一种实现,所以,基于双端队列的操作在LinkedList中全部有效。  

    public abstract class AbstractSequentialList<E>
    extends AbstractList<E>
    //这里第一段就解释了这个类的作用,这个类为实现list接口提供了一些重要的方法,
    //尽最大努力去减少实现这个“顺序存取”的特性的数据存储(例如链表)的什么鬼,对于
    //随机存取数据(例如数组)的类应该优先使用AbstractList
    //从上面就可以大概知道,AbstractSwquentialList这个类是为了减少LinkedList这种顺//序存取的类的代码复杂度而抽象的一个类,
    This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a "sequential access" data store (such as a linked list). For random access data (such as an array), AbstractList should be used in preference to this class.
    
    //这一段大概讲的就是这个AbstractSequentialList这个类和AbstractList这个类是完全//相反的。比如get、add这个方法的实现
    This class is the opposite of the AbstractList class in the sense that it implements the "random access" methods (get(int index), set(int index, E element), add(int index, E element) and remove(int index)) on top of the list's list iterator, instead of the other way around.
    
    //这里就是讲一些我们自己要继承该类,该做些什么事情,一些规范。
    To implement a list the programmer needs only to extend this class and provide implementations for the listIterator and size methods. For an unmodifiable list, the programmer need only implement the list iterator's hasNext, next, hasPrevious, previous and index methods.
    
    For a modifiable list the programmer should additionally implement the list iterator's set method. For a variable-size list the programmer should additionally implement the list iterator's remove and add methods.
    
    The programmer should generally provide a void (no argument) and collection constructor, as per the recommendation in the Collection interface specification.

    AbstractSequentialList

      实现接口分析:

        

          1)List接口:列表,add、set、等一些对列表进行操作的方法

          2)Deque接口:有队列的各种特性,

          3)Cloneable接口:能够复制,使用那个copy方法。

          4)Serializable接口:能够序列化。

          5)应该注意到没有RandomAccess:那么就推荐使用iterator,在其中就有一个foreach,增强的for循环,其中原理也就是iterator,我们在使用的时候,使用foreach或者iterator都可以

    2.2、类的属性  

    复制代码
    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
        // 实际元素个数
        transient int size = 0;
        // 头结点
        transient Node<E> first;
        // 尾结点
        transient Node<E> last;
    }
    复制代码

      LinkedList的属性非常简单,一个头结点、一个尾结点、一个表示链表中实际元素个数的变量。注意,头结点、尾结点都有transient关键字修饰,这也意味着在序列化时该域是不会序列化的。

    2.3、LinkedList的构造方法

      两个构造方法(两个构造方法都是规范规定需要写的)

      1)空参构造函数

        /**
         * Constructs an empty list.
         */
        public LinkedList() {
        }

      2)有参构造函数

    复制代码
    /**
         * 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中的各个元素构建成LinkedList链表。
        public LinkedList(Collection<? extends E> c) {
    
         // 调用无参构造函数
            this();
            // 添加集合中所有的元素
            addAll(c);
    }
    复制代码

      说明:会调用无参构造函数,并且会把集合中所有的元素添加到LinkedList中。   

    2.4、内部类(Node)

    复制代码
    
    
    //根据前面介绍双向链表就知道这个代表什么了,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;
            }
        }
    复制代码

      说明:内部类Node就是实际的结点,用于存放实际元素的地方。     

     2.5、核心方法

      2.5.1、add()方法

        

        1)add(E)

        public boolean add(E e) {
              // 添加到末尾
              linkLast(e);
              return true;
          }

        说明:add函数用于向LinkedList中添加一个元素,并且添加到链表尾部。具体添加到尾部的逻辑是由linkLast函数完成的

        分析:

          LinkLast(XXXXX)

    复制代码
    /**
         * Links e as last element.
         */
        void linkLast(E e) {
            final Node<E> l = last;    //临时节点l(L的小写)保存last,也就是l指向了最后一个节点
            final Node<E> newNode = new Node<>(l, e, null);//将e封装为节点,并且e.prev指向了最后一个节点
            last = newNode;//newNode成为了最后一个节点,所以last指向了它
            if (l == null)    //判断是不是一开始链表中就什么都没有,如果没有,则newNode就成为了第一个节点,first和last都要指向它
                first = newNode;
            else    //正常的在最后一个节点后追加,那么原先的最后一个节点的next就要指向现在真正的最后一个节点,原先的最后一个节点就变成了倒数第二个节点
                l.next = newNode;
            size++;//添加一个节点,size自增
            modCount++;
        }
    复制代码

        说明:对于添加一个元素至链表中会调用add方法 -> linkLast方法

        举例一:

        List<Integer> lists = new LinkedList<Integer>();
        lists.add(5);
        lists.add(6);

         首先调用无参构造函数,之后添加元素5,之后再添加元素6。具体的示意图如下:

          

          上图的表明了在执行每一条语句后,链表对应的状态。

      2.5.2、addAll方法

        addAll有两个重载函数,addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型,我们平时习惯调用的addAll(Collection<? extends E>)型会转化为addAll(int, Collection<? extends E>)型。

        1)addAll(c);

        public boolean addAll(Collection<? extends E> c) {
        //继续往下看
            return addAll(size, c);
        }

        2)addAll(size,c):这个方法,能包含三种情况下的添加,我们这里分析的只是构造方法,空链表的情况(情况一)看的时候只需要按照不同的情况分析下去就行了。

    复制代码
    //真正核心的地方就是这里了,记得我们传过来的是size,c
        public boolean addAll(int index, Collection<? extends E> c) {
    //检查index这个是否为合理。这个很简单,自己点进去看下就明白了。
            checkPositionIndex(index);
    //将集合c转换为Object数组 a
            Object[] a = c.toArray();
    //数组a的长度numNew,也就是由多少个元素
            int numNew = a.length;
            if (numNew == 0)
    //集合c是个空的,直接返回false,什么也不做。
                return false;
    //集合c是非空的,定义两个节点(内部类),每个节点都有三个属性,item、next、prev。注意:不要管这两个什么含义,就是用来做临时存储节点的。这个Node看下面一步的源码分析,Node就是linkedList的最核心的实现,可以直接先跳下一个去看Node的分析
            Node<E> pred, succ;
    //构造方法中传过来的就是index==size
            if (index == size) {
    //linkedList中三个属性:size、first、last。 size:链表中的元素个数。 first:头节点  last:尾节点,就两种情况能进来这里
    
    //情况一、:构造方法创建的一个空的链表,那么size=0,last、和first都为null。linkedList中是空的。什么节点都没有。succ=null、pred=last=null
    
    //情况二、:链表中有节点,size就不是为0,first和last都分别指向第一个节点,和最后一个节点,在最后一个节点之后追加元素,就得记录一下最后一个节点是什么,所以把last保存到pred临时节点中。
                succ = null;
                pred = last;
            } else {
    //情况三、index!=size,说明不是前面两种情况,而是在链表中间插入元素,那么就得知道index上的节点是谁,保存到succ临时节点中,然后将succ的前一个节点保存到pred中,这样保存了这两个节点,就能够准确的插入节点了
     //举个简单的例子,有2个位置,1、2、如果想插数据到第二个位置,双向链表中,就需要知道第一个位置是谁,原位置也就是第二个位置上是谁,然后才能将自己插到第二个位置上。如果这里还不明白,先看一下文章开头对于各种链表的删除,add操作是怎么实现的。
                succ = node(index);
                pred = succ.prev;
            }
    //前面的准备工作做完了,将遍历数组a中的元素,封装为一个个节点。
            for (Object o : a) {
                @SuppressWarnings("unchecked") E e = (E) o;
    //pred就是之前所构建好的,可能为null、也可能不为null,为null的话就是属于情况一、不为null则可能是情况二、或者情况三
                Node<E> newNode = new Node<>(pred, e, null);
    //如果pred==null,说明是情况一,构造方法,是刚创建的一个空链表,此时的newNode就当作第一个节点,所以把newNode给first头节点
                if (pred == null)
                    first = newNode;
                else
    //如果pred!=null,说明可能是情况2或者情况3,如果是情况2,pred就是last,那么在最后一个节点之后追加到newNode,如果是情况3,在中间插入,pred为原index节点之前的一个节点,将它的next指向插入的节点,也是对的
                    pred.next = newNode;
    //然后将pred换成newNode,注意,这个不在else之中,请看清楚了。
                pred = newNode;
            }
            if (succ == null) {
    //如果succ==null,说明是情况一或者情况二,
    情况一、构造方法,也就是刚创建的一个空链表,pred已经是newNode了,last=newNode,所以linkedList的first、last都指向第一个节点。
    情况二、在最后节后之后追加节点,那么原先的last就应该指向现在的最后一个节点了,就是newNode。
                last = pred;
            } else {
    //如果succ!=null,说明可能是情况三、在中间插入节点,举例说明这几个参数的意义,有1、2两个节点,现在想在第二个位置插入节点newNode,根据前面的代码,pred=newNode,succ=2,并且1.next=newNode,
    1已经构建好了,pred.next=succ,相当于在newNode.next = 2; succ.prev = pred,相当于 2.prev = newNode, 这样一来,这种指向关系就完成了。first和last不用变,因为头节点和尾节点没变
                pred.next = succ;
    //。。
                succ.prev = pred;
            }
    //增加了几个元素,就把 size = size +numNew 就可以了
            size += numNew;
            modCount++;
            return true;
        }
    复制代码

        说明:参数中的index表示在索引下标为index的结点(实际上是第index + 1个结点)的前面插入。     

           在addAll函数中,addAll函数中还会调用到node函数,get函数也会调用到node函数,此函数是根据索引下标找到该结点并返回,具体代码如下:

    复制代码
    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; // 返回该结点
            }
        }
    复制代码

        说明:在根据索引查找结点时,会有一个小优化,结点在前半段则从头开始遍历,在后半段则从尾开始遍历,这样就保证了只需要遍历最多一半结点就可以找到指定索引的结点。

        举例说明调用addAll函数后的链表状态:

        List<Integer> lists = new LinkedList<Integer>();
        lists.add(5);
        lists.addAll(0, Arrays.asList(2, 3, 4, 5));

          上述代码内部的链表结构如下:

            

      addAll()中的一个问题

        在addAll函数中,传入一个集合参数和插入位置,然后将集合转化为数组,然后再遍历数组,挨个添加数组的元素,但是问题来了,为什么要先转化为数组再进行遍历,而不是直接遍历集合呢?

        从效果上两者是完全等价的,都可以达到遍历的效果。关于为什么要转化为数组的问题,我的思考如下:1. 如果直接遍历集合的话,那么在遍历过程中需要插入元素,在堆上分配内存空间,修改指针域,

        这个过程中就会一直占用着这个集合,考虑正确同步的话,其他线程只能一直等待。2. 如果转化为数组,只需要遍历集合,而遍历集合过程中不需要额外的操作,

        所以占用的时间相对是较短的,这样就利于其他线程尽快的使用这个集合。说白了,就是有利于提高多线程访问该集合的效率,尽可能短时间的阻塞。

      2.5.3、remove(Object o)

    复制代码
    /**
         * Removes the first occurrence of the specified element from this list,
         * if it is present.  If this list does not contain the element, it is
         * unchanged.  More formally, removes the element with the lowest index
         * {@code i} such that
         * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
         * (if such an element exists).  Returns {@code true} if this list
         * contained the specified element (or equivalently, if this list
         * changed as a result of the call).
         *
         * @param o element to be removed from this list, if present
         * @return {@code true} if this list contained the specified element
         */
    //首先通过看上面的注释,我们可以知道,如果我们要移除的值在链表中存在多个一样的值,那么我们会移除index最小的那个,也就是最先找到的那个值,如果不存在这个值,那么什么也不做
        public boolean remove(Object o) {
    //这里可以看到,linkedList也能存储null
            if (o == null) {
    //循环遍历链表,直到找到null值,然后使用unlink移除该值。下面的这个else中也一样
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null) {
                        unlink(x);
                        return true;
                    }
                }
            } else {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item)) {
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
        }
    复制代码

        unlink(xxxx)

    复制代码
    /**
         * Unlinks non-null node x.
         */
    //不能传一个null值过,注意,看之前要注意之前的next、prev这些都是谁。
        E unlink(Node<E> x) {
            // assert x != null;
    //拿到节点x的三个属性
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
    
    //这里开始往下就进行移除该元素之后的操作,也就是把指向哪个节点搞定。
            if (prev == null) {
    //说明移除的节点是头节点,则first头节点应该指向下一个节点
                first = next;
            } else {
    //不是头节点,prev.next=next:有1、2、3,将1.next指向3
                prev.next = next;
    //然后解除x节点的前指向。
                x.prev = null;
            }
    
            if (next == null) {
    //说明移除的节点是尾节点
                last = prev;
            } else {
    //不是尾节点,有1、2、3,将3.prev指向1. 然后将2.next=解除指向。
                next.prev = prev;
                x.next = null;
            }
    //x的前后指向都为null了,也把item为null,让gc回收它
            x.item = null;
            size--;    //移除一个节点,size自减
            modCount++;
            return element;    //由于一开始已经保存了x的值到element,所以返回。
        }
    复制代码

      2.5.4、get(index)

        get(index)查询元素的方法

    复制代码
    /**
         * Returns the element at the specified position in this list.
         *
         * @param index index of the element to return
         * @return the element at the specified position in this list
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
    //这里没有什么,重点还是在node(index)中
        public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }
    复制代码

        node(index)

    复制代码
    /**
         * Returns the (non-null) Node at the specified element index.
         */
    //这里查询使用的是先从中间分一半查找
        Node<E> node(int index) {
            // assert isElementIndex(index);
    //"<<":*2的几次方 “>>”:/2的几次方,例如:size<<1:size*2的1次方,
    //这个if中就是查询前半部分
             if (index < (size >> 1)) {//index<size/2
                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.5.5、indexOf(Object o)

    复制代码
    //这个很简单,就是通过实体元素来查找到该元素在链表中的位置。跟remove中的代码类似,只是返回类型不一样。
       public int indexOf(Object o) {
            int index = 0;
            if (o == null) {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null)
                        return index;
                    index++;
                }
            } else {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item))
                        return index;
                    index++;
                }
            }
            return -1;
        }
    复制代码

    三、LinkedList的迭代器

      在LinkedList中除了有一个Node的内部类外,应该还能看到另外两个内部类,那就是ListItr,还有一个是DescendingIterator。

      3.1、ListItr内部类

        

        看一下他的继承结构,发现只继承了一个ListIterator,到ListIterator中一看:

        

        看到方法名之后,就发现不止有向后迭代的方法,还有向前迭代的方法,所以我们就知道了这个ListItr这个内部类干嘛用的了,就是能让linkedList不光能像后迭代,也能向前迭代。

         看一下ListItr中的方法,可以发现,在迭代的过程中,还能移除、修改、添加值得操作。

        

      3.2、DescendingIterator内部类    

    复制代码
    /**
         * Adapter to provide descending iterators via ListItr.previous
         */
        看一下这个类,还是调用的ListItr,作用是封装一下Itr中几个方法,让使用者以正常的思维去写代码,例如,在从后往前遍历的时候,也是跟从前往后遍历一样,使用next等操作,而不用使用特殊的previous。
        private class DescendingIterator implements Iterator<E> {
            private final ListItr itr = new ListItr(size());
            public boolean hasNext() {
                return itr.hasPrevious();
            }
            public E next() {
                return itr.previous();
            }
            public void remove() {
                itr.remove();
            }
        }
    复制代码

    四、总结

      1)linkedList本质上是一个双向链表,通过一个Node内部类实现的这种链表结构
      2)能存储null值
      3)跟arrayList相比较,就真正的知道了,LinkedList在删除和增加等操作上性能好,而ArrayList在查询的性能上好
      4)从源码中看,它不存在容量不足的情况
      5)linkedList不光能够向前迭代,还能像后迭代,并且在迭代的过程中,可以修改值、添加值、还能移除值
      6)linkedList不光能当链表,还能当队列使用,这个就是因为实现了Deque接口

     

    喜欢就点个“推荐”!

     

    0
    0
    currentDiggType = 0;
    « 上一篇:Java集合源码分析(一)ArrayList
    » 下一篇:JavaProblem之hashCode详解
    posted @ 2017-10-18 23:18 苦水润喉 阅读(109) 评论(0) 编辑 收藏

    展开全文
  • Java集合源码分析详解系列https://www.cnblogs.com/zhangyinhua/tag/Java%E9%9B%86%E5%90%88%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90%E8%AF%A6%E8%A7%A3%E7%B3%BB%E5%88%97/
  • ArrayList源码分析前言在之前的文章中我们提到过ArrayList,ArrayList可以说是每一个学java的人使用最多最熟练的集合了,但是知其然不知其所以然。关于ArrayList的具体实现,一些基本的都也知道,譬如数组实现,线程...
  • Java集合源码分析(二)Linkedlist 阅读目录(Content) 一、LinkedList简介 1.1、LinkedList概述 1.2、LinkedList的数据结构 1.3、LinkedList的特性 二、LinkedList源码分析 2.1、LinkedList...
  • Java集合源码分析(一)ArrayList 阅读目录(Content) 一、ArrayList简介 1.1、ArrayList概述 1.2、ArrayList的数据结构 二、ArrayList源码分析 2.1、继承结构和层次关系 2.2、类中的属性 2.3...
  • [Java教程]Java集合源码分析(五)HashSetE0 2016-07-08 17:00:05HashSet简介HashSet实现Set接口,由哈希表(实际上是一个HashMap实例)支持。它不保证set 的迭代顺序;特别是它不保证该顺序恒久不变。此类允许使用null...
  • Java集合源码分析(三)Vevtor和Stack 阅读目录(Content) 一、Vector简介 1.1、Vector概述 二、Vector源码分析 2.1、继承结构和层次关系 2.2、构造方法 2.3、核心方法  2.3.1、add()方法 三...
  • 浅说java集合源码分析

    2020-06-09 13:56:50
    学javase已经有一段时间,现在回过头来看看java集合中重要的List与Map的实现原理与源码分析。 直接上图,个人做的总结 来源参考: java核心技术卷一、宋红康javase精讲。
  • 一:简述List集合代表一个有序集合集合中每个元素...因为List中的元素是有序的,所以我们可以通过使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,这类似于Java的数组。List接口为Collection直...
  • Java集合源码分析一、ArrayList二、LinkedList 一、ArrayList 继承结构与接口实现 JDK 8.0中ArrayList的变化: ArrayList list = new ArrayList();//底层Object[] elementData初始化为{}.并没创建长度为10的...
  • TreeMap是红黑树的java实现,对红黑树不太了解的可以查阅这篇文章Java集合源码分析之基础(六):红黑树(RB Tree)。红黑树能保证增、删、查等基本操作的时间复杂度为O(lgN)。本文将对TreeMap的源码进行分析。...
  • Java集合源码分析之List(二):ArrayList 大大纸飞机 关注2018.04.17 16:02* 字数 1952 阅读 427评论 5喜欢 2做了这么多准备,终于到了ArrayList了,ArrayList是我们使用最为频繁的集合类了,我们先看看文档是...
  • 前言在前面的学习集合中只是介绍了集合的相关用法,我们想要更深入的去了解集合那就要通过我们去分析它的源码来了解它。希望对集合有一个更进一步的理解!既然是看源码那我们要怎么看一个类的源码呢?这里我推荐的...
  • 前两篇文章分别分析Java的ArrayList和LinkedList实现原理,这篇文章分析下HashSet和LinkedHashSet的源码。重点讲解HashSet,因为LinkedHashSet是继承自HashSet,只是它的成员变量map类型是LinkedHashMap而不是...
  • Java集合估计是我们开发过程中,用的最多的API了,它位于java.util包下,同时支持多线程的集合类位于java.util.concurrent包下。 我们都知道各种数据结构最底层的组成都是数组或者链表,其实各种集合类也是基于最...
  • LinkedList源码分析 #一.LinkedList简介 LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能对它进行队列操作。 ...
  • 1)HashMap是基于哈希表实现Map接口的JAVA集合类 2)HashMap的两个重要变量影响其是否要扩增容量,loadFactory(加载因子),初始化容量(initCapacity) HashMap继承层次和实现接口 HashMap源码分析 总结 .....
  • Java中的数组相比,它的容量能动态增长。它继承于AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。ArrayList 继承了AbstractList,实现了List。它是一个数组队列,提供了相关...
  • CollectionCollection是List、Queue和Set的超集,它直接继承于Iterable,也就是所有的Collection集合类都支持for-each循环。除此之外,Collection也是面向接口编程的典范,通过它可以在多种实现类间转换,这也是面向...
  • HashSet是一个没有重复元素的集合。 它是由HashMap实现的,不保证元素的顺序,而且HashSet允许使用 null 元素。 HashSet的父类和实现的接口 public class HashSet < E > extends AbstractSet < ...
  • TreeMap源码分析 treemap的数据结构基础是红黑树。 可以到如下复习一下红黑树: http://blog.csdn.net/a910626/article/details/54378874 节点 static final class Entry,V> implements Map....
  • TreeSet 是一个有序的集合,它的作用是提供有序的Set集合。它继承于AbstractSet抽象类,实现了NavigableSet, Cloneable, java.io.Serializable接口。 TreeSet 继承于AbstractSet,所以它是一个Set集合,具有Set的...
  • HashSet概述 1)HashSet属于单列集合体系 ...HashSet源码分析 public class HashSet&lt;E&gt; extends AbstractSet&lt;E&gt; implements Set&lt;E&gt;, Cloneable, java.io.Serializ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,406
精华内容 2,162
关键字:

java集合源码分析

java 订阅