TOP

Java集合 LinkedList的原理及使用
2019-08-14 00:07:04 】 浏览:51
Tags:Java 集合 LinkedList 原理 使用

LinkedList和ArrayList一样是集合List的实现类,虽然较之ArrayList,其使用场景并不多,但同样有用到的时候,那么接下来,我们来认识一下它。


上面代码中采用了两种方式来定义LinkedList,可以定义一个空集合,也可以传递已有的集合,将其转化为LinkedList。我们看一下源码


LinkedList继承了AbstractSequentialList类,实现了List接口,AbstractSequentialList中已经实现了很多方法,如get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index),这些方法是我们集合操作时使用最多的,不过这些方法在LinkedList中都已经被重写了,而抽象方法在LinkedList中有了具体实现。因此我们回到LinkedList类


LinkedList类中定义了三个变量


针对first变量和last变量,我们看到是Node类的实体,这是一个静态内部类,关于静态内部类的讲解,我们在static五大应用场景一章已经有说明


我们知道LinkedList是通过双向链表实现的,而双向链表就是通过Node类来体现的,类中通过item变量保存了当前节点的值,通过next变量指向下一个节点,通过prev变量指向上一个节点。


我们知道随机读取元素不是LinkedList所擅长的,读取效率比起ArrayList也低得多,那么我来看一下为什么


从上述代码中我们可以看到get(int index)方法是通过node(int index)来实现的,它的实现机制是:


比较传入的索引参数index与集合长度size/2,如果是index小,那么从第一个顺序循环,直到找到为止;如果index大,那么从最后一个倒序循环,直到找到为止。也就是说越靠近中间的元素,调用get(int index方法遍历的次数越多,效率也就越低,而且随着集合的越来越大,get(int index)执行性能也会指数级降低。因此在使用LinkedList的时候,我们不建议使用这种方式读取数据,可以使用getFirst(),getLast()方法,将直接用到类中的first和last变量。


大家都在说LinkedList插入、删除操作效率比较高,以stringList.add(“猪八戒”)为例来看到底发生了什么?


在LinkedList中我们找到add(E e)方法的源码


很好理解:


情况1:假如stringList为空,那么添加进来的node就是first,也是last,这个node的prev和next都为null;



情况2:假如stringList不为空,那么添加进来的node就是last,node的prev指向以前的最后一个元素,node的next为null;同时以前的最后一个元素的next.



而如果通过stringList.add(1, “猪八戒”)这种方式将元素添加到集合中呢?


其实从代码中看到和add(E e)的代码实现没有本质区别,都是通过新建一个Node实体,同时指定其prev和next来实现,不同点在于需要调用node(int index)通过传入的index来定位到要插入的位置,这个也是比较耗时的,参考上面的get(int index)方法。


其实看到这里,大家也都明白了。


这里removeFirst()和removeLast()就不多说了,会用到类中定义的first和last变量,非常简单,我们看一下remove(Object o) 和 remove(int index)源码


其实实现都非常简单,先找到要删除的节点,remove(Object o)方法遍历整个集合,通过 == 或 equals方法进行判断;remove(int index)通过node(index)方法。



我们主要列举一下三种常用的遍历方式,


普通for循环,增强for循环,Iterator迭代器


执行结果如下:


通过普通for循环随机访问的方式执行时间远远大于迭代器访问方式,这个我们可以理解,在前面的get(int index)方法中已经有过说明,那么为什么增强for循环能做到迭代器遍历差不多的效率?


通过反编译???具后得到如下代码


很明显了,增强for循环遍历时也调用了迭代器Iterator,不过多了一个赋值的过程。


还有类似于pollFirst(),pollLast()取值后删除的方法也能达到部分的遍历效果。


本文基于Java8从定义一个LinkList入手,逐步展开,从源码角度分析LinkedList双向链表的结构是如何构建的,同时针对其常用方法进行分析,包括get,add,remove以及常用的遍历方法,并简单的说明了它的插入、删除操作为何相对高效,而取值操作性能相对较低,若有不对之处,请批评指正,望共同进步,谢谢!



Java集合 LinkedList的原理及使用 https://www.cppentry.com/bencandy.php?fid=54&id=228474

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇红黑树(R-B tree)原理图文详解 下一篇逆波兰表达式 - 中缀表达式转后缀..