Java集合之LinkedList源码解析
LinkedList简介
LinkedList基于双向链表,即FIFO(先进先出)和FILO(先进后出)都是支持的,这样它可以作为堆栈,队列使用
继承AbstractSequentialList,该类我认为和RandomAccess是一个对立,它通过次序访问数据,
实现了List,Deque,Cloneable和Serializable接口
LinkedList构造函数
- public LinkedList()
-
LinkedList(Collection<? extends E> c)
可以看出和ArrayList对比是少了一个指定容量的构造函数,因为LinkedList不存在扩容的概念,
它通过判断链表的节点next属性判断是否还有下一个节点,增加删除都是针对节点prev和next属性;
结构分析
从结构图可以看出LinkedList有三个属性,size:LinkedList大小,
first:LinkedList的第一个节点,last:LinkedList最后一个节点
LinkedList源码分析(java version:1.8.0_111)
Node
链表节点Node:LinkedList内部类Node代表的就是节点信息,
item表示的是我们存储在链表当前位置的数据,next记录的是下一个节点指向,
prev记录的是上一个节点指向,这样俯视看LinkedList就会像下面图
添加元素
可以看出来,默认时候我们添加元素都是在LinkedList末尾添加元素的,
当我们添加一个元素e时候,先创建一个prev指向LinkedList最后一个节点,item为e,next指向null
的节点newNode,然后LinkedList的last就指向了newNode,
再让LinkedList原来的最后一个节点指向newNode
添加指定元素到指定位置:从代码中可以看出,首先检查当前index是否合法,
然后和LinkedList的长度比较,如果相等这是再末尾添加元素,上一个add方法类似;
如果不相等则是再LinkedList中间段添加,此时取出原来在index位置的节点,添加一个新节点,
改变对应的节点指向
这里的node(int index)方法是比较有趣的,你查看源码时候会发现这个方法好像总是在出现,
因为本质上来说,LinkedList的操作就是节点的操作,而对应的定位到某个位置的节点这个方法当然
出现的频率就是有点高了,在开始的时候知道LinkedList的几个属性,可以看出来如果我们想知道
节点信息只能从first和last属性着手,这也是node(int index)方法的由来,是从开始还是从最后
遍历这个方法做了个判断,能加快一定的遍历速度
LinkedList遍历
1.迭代器遍历
2.ForEach遍历
for (Object s : list)
3.随机访问遍历
for (int i =0; i<list.size();i++){
list.get(i);
}
4.pollFirst()/pollLast()/removeFirst()/removeLast()方法
while (list.pollFirst() != null){
}
总结
对应的LinkedList的增删改查操作都是对节点的prev,next和item的操作,遍历测试可以发现
使用随机访问遍历时候速度是最慢的,因为在每一次list.get(index)时候都从开始或者最后遍历
一次链表[查看源码可以看见get方法也是需要上面的node(index)方法],而foreach和迭代器
速度差不多
相关文章
- java实现报数游戏
- Java实现 蓝桥杯 算法训练 关联矩阵
- Java集合源码分析(三)LinkedList
- 【JAVA】java中的length和length()
- 【JAVA】 01-Java基础知识
- java集合框架07——Map架构与源码分析
- [Java] String、StringBuffer与StringBuilder区别和联系(源码)
- java junit Assert断言用法示例: Assert.assertEquals(期望的结果,运算的结果)
- SSO单点登录系列1:cas客户端源码分析cas-client-java-2.1.1.jar
- 【错误记录】IntelliJ IDEA 中右键点击源码目录选择 New 选项 没有创建 Java Class 选项 ( 将对应的源码目录标记为 Sources 选项 )
- JVM源码分析之一个Java进程究竟能创建多少线程
- Java集合源码学习(四)HashMap
- Java集合源码学习(三)LinkedList
- JAVA虚拟机源码学习笔记之二
- java集合: LinkedList源码浅析
- 独特视角带你走进Java并发编程的世界
- ZZNUOJ_用Java编写程序实现1538:都是素数么(附源码)
- ZZNUOJ_用Java编写程序实现1594:特殊的生日礼物(附源码)
- 【java】如何去阅读源码,我总结了18条心得
- JAVA开发讲义(二)-Java程序设计之数据之谜三