- 浏览: 1360970 次
- 性别:
- 来自: 广州
文章分类
最新评论
-
daye0209:
sohuexe 写道C++恐怕它还不行吧,推荐看看 http: ...
JNA入门实例 -
cxhcxheret:
...
每日一Vim(29)ctags -
qdujunjie:
学会了recording,感谢~~
每日一Vim(23)宏---Record、Play -
perfectionhello:
很棒的vim
每日一Vim(5)c命令 -
zc-111:
看完了才发现这篇文章果然是你写的
5分钟了解Mockito
LinkedList的源码分析
LinkedList是一个双向循环链表,既然是双向的列表,就不能像ArrayList一样交给一个Object数组来存储。LinkedList需要定义新的数据类型来解决链表的问题,他就是Entry,Entry必须拥有指向前一个节点和指向下一个节点的属性,还有将要保存的元素本身。
private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous; } }
element: 当前节点的值
previous: 指向前一个节点
next: 指向后一个节点
几个重要的方法:
add(E e)方法
public boolean add(E e) { addBefore(e, header); return true; }
再看addBefore
private Entry<E> addBefore(E e, Entry<E> entry) { Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; }
上面这方法代码没几行,但是理解还是结合我们在学校学的数据结构把思路给缕一缕,直接看图说话:
0:调用add(E e)时,相当于把元素插在最后一个位置
1、2:相当于初始化一个newEntry对象
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
因为这是一个循环双向队列,最后一个元素的next始终指向header,同时header的previous始终指向最后一个元素,那么就刚好对应
1:newEntry.next=head,
2:newEntry.previous=header.previous
这两步还仅仅是newEntry的初始化过程,给newEntry的属性赋值而已,header和未插入之前的最后那个元素的关系并没有断开。
这里假设把原来最后那个元素叫tail
3:就是把tail.next指向newEntry,相应的代码就是:
newEntry.previous.next = newEntry;
4:header的preview需要指向新的最后一个元素newEntry:
newEntry.next.previous = newEntry;
这样整个插入过程基本上就完成了。add(E e)的时间复杂度o(1),大家猜猜如果要是在中间某个位置插入又是怎么实现的呢?
add(int index E e)方法
public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); }
为了找到插入点需要,如果不是插在最后一个位置的话,需要调用entry(index)
private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }
看到没有,从header开始找,并不是一味的header.next.next.....,而是当index小于size/2是往next方向找,小于size/2时逆向查找,这样它的复杂度就是o(n/2),这点和ArrayList是一样的都需要遍历,不同的是LinkedList不需要移动元素。
来看看删除的方法
public boolean remove(Object o) { if (o==null) { for (Entry<E> e = header.next; e != header; e = e.next) { if (e.element==null) { remove(e); return true; } } } else { for (Entry<E> e = header.next; e != header; e = e.next) { if (o.equals(e.element)) { remove(e); return true; } } } return false; }
private E remove(Entry<E> e) { if (e == header) throw new NoSuchElementException(); E result = e.element; e.previous.next = e.next; e.next.previous = e.previous; e.next = e.previous = null; e.element = null; size--; modCount++; return result; }
因为LinkedList是由Entry维护,Entry即我们所说的节点,为了删除对象o时,就不能去找到由o构成的Entry对象,移除Entry对象时,刚好与add相反,删除它的操作很简单,只要把前一个节点的next属性指下一个节点(e.previous.next = e.next;),然后下一个节点的previous指向当前节点的前一个节点(e.next.previous = e.previous;),最后把当前节点的next,previous、element置为null,以便GC回收(e.next = e.previous = null; e.element = null;)删除操作就完成了,我们从中可以看出这个方法的时间复杂度仅为O(1),所以他的操作是非常快的。但是为了找到Entry,他要从header节点开始找,直到找到那个值与传入的参数值相等,我们可以看出他的时间复杂度就不是我们普遍认为的O(1)了,而变成了O(n)。
再来看看下面这个方法
public E remove(int index) { return remove(entry(index)); }
这是删除某个指定位置元素的方法,与add(int index E e)对应
private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; }
总结:相对于ArrayList来说,普遍认为对数据的修改频繁时最好使用LinkedList,但是我们发现针对LinkedList要移除某个元素时,发现其效率也并不见得非常的高,因为其中还涉及到一个查询的操作。,所以,要是性能要求很高的话,可以自己实现满足要求的LinkedList,而不用jdk提供的通用的java.util.LinkedList。
发表评论
-
helloworld
2013-04-13 00:31 1hello,iteye,just a test -
helloworld
2013-04-13 00:23 1hello,iteye,just a test -
快速了解Log4J
2012-12-13 00:23 27630Log4J的三个组件: Logger:日志记录器,负责收集 ... -
JNA入门实例
2012-12-09 20:22 19812JNA(Java Native Access):建立在JNI之 ... -
Effective Java 读书笔记-----异常
2012-12-08 17:25 0学习一门编程语言,需要掌握三点: 其一:了解语言的核心:需要 ... -
Ubuntu安装配置JDK、Tomcat 、Eclipse
2012-11-19 15:22 3177在Linux下安装JDK Tomcat等Java运行环境,安装 ... -
Java Thread 部分方法及概念
2012-08-25 23:58 3122这里并不打算说明什么叫线程,但是可以简单举一线程的应用场景 ... -
5分钟了解Mockito
2012-05-05 16:15 105698一、什么是mock测试, ... -
Java利器收集
2012-04-20 11:34 4test -
Java程序员,不要过度依赖于String
2012-04-03 13:43 7462在Java中永远,永远不要过度使用String ... -
Java程序员,不要过度依赖于String
2012-04-03 13:41 1在Java中永远,永远不要过度使用String ... -
Java SE 7 Exception的使用
2012-03-01 01:23 3371Java SE 7 Exception的使用 在Ja ... -
一些实用类
2012-02-16 01:55 20991、TimeUnit TimeUnit出现在concurre ... -
关于并发的一篇短文
2012-02-14 01:02 1583JAVA并发 前言:这是一篇根据《java编程思想》并发章节 ... -
谈谈接口
2011-12-25 01:57 1295接口 一、此接口非 ... -
对Boolean.getBoolean(String name)的己见
2011-10-12 15:24 48151、今天遇到这样一件事:想把String类型的true和fal ... -
对optional operations的理解
2011-08-11 01:36 0optional operations(可选操作):接口中的一 ... -
适配器模式
2012-06-24 09:13 1Adapter ... -
适配器模式
2012-06-24 09:15 1256Adapter 问题引出: 大家生活中可能碰到的一个问题就 ... -
enum(java中的枚举)
2011-06-04 00:50 7421Java 中的枚举(enum) 枚举就是一组有限数据的集合, ...
相关推荐
LinkedList源码分析_016.pdf
学习linkedList源码,数据结构是链表。模仿LinkedList集合自己写一个
简介 LinkedList 是一个常用的集合类,用于顺序存储元素。 LinkedList 经常和 ArrayList 一起被提及。...本文分析 LinkedList 的具体实现。 继承关系 public class LinkedList extends AbstractS
主要为大家详细介绍了Java集合系列之LinkedList源码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
LinkedList是通过节点的连接实现链表的数据结构,向linkedList中插入或删除元素的速度是特别快,而随机访问的速度相对较慢,这个是由于链表本身的性质造成的,在链表中,每个节点都包含了前一个节点的引用,后一个...
这是我从JDK中拿出的Arraylist,Vector,LinkedList源码,自己看源码的时候弄出来的,并写了一点自己的分析,仅供源码分析者使用
计算机后端-Java-Java核心基础-第24章 集合01 15. LinkedList的源码分析.avi
主要给大家介绍了关于Java基于JDK 1.8的LinkedList源码的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
主要介绍了java LinkedList源码详解及实例的相关资料,需要的朋友可以参考下
能学到什么:ArrayList的源码分析,自动扩容和自动缩容的源码分析,相关参数的深度解析,从是什么,为什么,怎么做三个角度进行讲解,用通俗易懂的白话进行介绍,LinkedList和Vector以及ArrayList的区别以及使用场景...
*要点分析: *1)主要部分已经集成为一个对象SnakeModel,利用键盘控制实现操作。 *文件名:SnakeModel.java *作者:C.Jason *要点分析: *1)数据结构:matrix[][]用来存储地图上面的信息,如果什么也没有设置为...
java8 源码 List相关实现类的源码解析(JDK1.8) 2018.9.22- List的架构图 ArrayList 继承关系: ArrayList -> AbstractList ...与Java中的数组相比,它的容量能动态增长。...LinkedList 继承关系: LinkedLis
主要给大家介绍了ArrayList和LinkedList这两种list的五种循环遍历方式,各种方式的性能测试对比,根据ArrayList和LinkedList的源码实现分析性能结果,总结结论。相信对大家的理解和学习具有一定的参考价值,有需要的...
集合源码分析 JAVA: 基本语法 static 修饰变量 方法 静态块(初始化块 构造函数 ) 静态内部类() 静态导包 final() transient() foreach循环原理() volatile底层实现() equals和hashcode(, ) string,stringbuffer和...
ArrayList 底层结构和源码分析 Vector 底层结构和源码剖析 LinkedList 底层结构 ArrayList 和 LinkedList 比较 Set 接口和常用方法 Map 接口和常用方法 总结-开发中如何选择集合实现类(记住) Collections工具类 泛型...
源码分析:ArrayList、Vector、LinkedList、HashMap、ConcurrentHashMap、HashSet、LinkedHashSet and LinkedHashMap 线程状态、线程机制、线程通信、J.U.C 组件、JMM、线程安全、锁优化 磁盘操作、字节操作、字符...
Collections 源码 java Java Java的ArrayList、LinkedList、HashMap、TreeMap、LinkedHashMap、HashSet、TreeSet相关源码分析,及相关问题和应用总结。
Source code analysis for Java or JDK 记录一些重要的JDK/Java相关的源码分析。 Java 集合框架 ArrayList LinkedList HashMap 参考文章:
主要介绍了Java中ArrayList与LinkedList列表结构的源码,文章最后对LinkedList和ArrayList以及Vector的特性有一个对比总结,需要的朋友可以参考下