1.先看下LinkedList 的继承关系:
2. 我们看到其主要实现了List,Queue接口,通过继承一个模板类AbstractSequentialList来实现链表,首先看下成员变量:
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
可以看到,有两个成员变量,一个是Entry-静态内部类,还有一个size,代表链表的实际大小,看下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-数据项,next-指向下一条数据项,previous-指向前一条数据项,可以看出这是一个双向链接,每个节点
都会指向前一个节点和后一个节点。
这里简要说明一下为什么要使用静态内部类:
摘自网络:
静态内部类的实例不会自动持有外部类的特定实例的引用, 因此在创建内部类的实例时, 不必创建外部类的实例.
静态内部类可以直接访问外部类的静态成员, 如果要访问外部类的实例成员, 就必须通过外部类的实例去访问
静态内部类中可以定义静态成员和实例成员
客户类可以通过完整的类名直接访问静态内部类的静态成员.
那这里,我认为是方便外部类访问,同时因为不包含任何方法,可以不用拿出来单独形成一个类,其他的好处,暂时还没看出来:(
下边重点看下几个方法的实现:
增加一条记录,add(E o),实现代码:
public boolean add(E o) {
addBefore(o, header);
return true;
}
内部调用了addBefore,再看addBefore的实现方式:
private Entry<E> addBefore(E o, Entry<E> e) {
//创建一个新的Entry实例
Entry<E> newEntry = new Entry<E>(o, e, e.previous);
//将header前一条数据的next指向newEntry,同时把header的previous指向newEntry,
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
//长度和修改计数递增
size++;
modCount++;
return newEntry;
}
在指定位置添加:
public void add(int index, E element) {
addBefore(element, (index==size ? header : entry(index)));
}
传递参数为:待添加的数据项O和header引用,详细分析参见注释,这里我们可以清晰的看到如何在一个链表结构中添加一条记录。
删除一条记录,remove(Object c):
public boolean remove(Object o) {
//判断插入数据项是否为null
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;
}
再看 remove(e)方法:
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
//提取待删除数据作为返回值
E result = e.element;
/*将待删除数据的next付给前一条数据项的next
* 将待删除数据的previous指向后一条数据previous
* 同时释放待删除数据项的next和previous链接,是否element
*/
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
//总条数size和修改计数递减
size--;
modCount++;
return result;
}
这里需要注意的是我们需要释放待删除节点的next和previous链接 ,以便于JVM在适当的时候进行垃圾回收。
获取数据,get(int index):
public E get(int index) {
return entry(index).element;
}
我们看下entry方法:
private Entry<E> entry(int index) {
//判断边界--前置条件判断
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
//如果index小于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的随机访问,会有所缓慢
最后看下contails(Object o)
public boolean contains(Object o) {
return indexOf(o) != -1;
}
看下indexOf(Object c)
public int indexOf(Object o) {
int index = 0;
if (o==null) {
for (Entry e = header.next; e != header; e = e.next) {
if (e.element==null)
return index;
index++;
}
} else {
for (Entry e = header.next; e != header; e = e.next) {
if (o.equals(e.element))
return index;
index++;
}
}
return -1;
}
这里分两种情况进行遍历,跟删除是相同的。
3.典型应用:
暂无
4,优点与缺点
优点:
LinkedList的中间插入或删除一个元素的开销是固定的
缺点:
LinkedList不支持高效的随机元素访问
最后,我感觉平时做项目ArrayList还是相对比较常用,LinkedList很少用,不知道有没有人在实际项目中使用过LinkedList ,切实的体会
到两者之间的差异,而不是向我最后分析的优缺点那样 都是些理论写的说辞,希望大家补充,谢谢。
- 大小: 21.8 KB
分享到:
相关推荐
源码解析jdk7.0集合:LinkedList的底层实现原理.pdf
主要给大家介绍了关于Java基于JDK 1.8的LinkedList源码的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
这是我从JDK中拿出的Arraylist,Vector,LinkedList源码,自己看源码的时候弄出来的,并写了一点自己的分析,仅供源码分析者使用
jdk源码学习 JavaSourceLearn 版本号 版本 corretto-1.8.0_275 方式 逐步阅读源码添加注释、notes文件夹添加笔记 计划学习任务计划 标题为包名,后面序号为优先级1-4,优先级递减 java.lang Object 1 String 1 ...
NULL 博文链接:https://brokendreams.iteye.com/blog/1916061
JDK 1.5的泛型實現(Generics in JDK 1.5) 1 侯捷觀點 JDK 1.5的泛型實現 — Generics in JDK 1.5 — 北京《程序員》 2004/09 台北《Run!PC》2004/09 作者簡介:侯捷,資訊教育、專欄執筆、大學教師...
这个源代码在http://www.wrox.com上可以获得,并且还有课后习题的答案以及JDK5到JDK6的变动说明,甚至还有书中LinkedList类的纠正版本。(都在压缩包里的Beg_Java_15文件夹里) 但是为了学习JAVA我自己亲自把书上...
JDK源码学习 JDK版本基于1.7 集合框架的学习 ArrayList原始码学习 HashMap原始码学习 LinkedList原始码学习 HashSet原始码学习 LinkedHashMap原始学习 LinkedHashSet原始码学习
本仓库记录了我的Java学习进阶之路,涵盖了Java基础、JDK源码、JVM中的重要知识,附有代码和博客讲解,旨在提供一个Java在线共享学习平台,帮助更多的Java学习入门者进阶。 Java学习 本仓库记录了我的Java学习进阶...
(这个类是大致相当于Vector,不同之处在于它是不同步的)。 该size,isEmpty,get,set,iterator和listIterator操作在固定时间内运行。 add操作以摊余常数运行 ,即添加n个元素需要O(n)个时间。 所有其他操作...
Generics 是JDK 1.5 一个最重要的特性,主要用来处理Collection。 以下代码在JDK 1.5 调试通过。 代码实例1: Demo.java package ... import java.util.LinkedList; import java.util.List; import java.util.Map;
在ArrayList和LinkedList尾部添加元素,谁的效率更高 如果HashMap或者hashTable的key是一个自定义的类该怎么办 为什么重写equals还要重写hashCode? 介绍一下volatile jdk1.5新特性 jdk1.7新特性 jdk1.8新特性 java...
缓慢更新一些个人学习java相关源码过程中的笔记,在这里你将不可避免地看到以下情况: 个别不懂/没想好的地方留空待补全 限于个人水平出现的解读错误 编辑错误 排版不统一 如发现有错,欢迎指正! 如果对你有用,...
全部代码出自电子工业出版社夏先波的《Java JDK实例宝典》一书,本书以J2SE 5.0为开发环境,选取Java应用的典型实例,循序渐进地介绍了Java语言的各种开发方法和技巧,实例代码注释详细规范,思路清晰。 第1章 ...
首先,List接口继承于Collection接口,其中的所有方法都被继承,而Collection是无序、无下标,元素不可重复的,List是有序,有下标,元素可以重复,所以,List就有一些自己独有的方法。...JDK1.2版本,运行效率快、线
主要基于jdk8, 可能会有些特性与jdk7之前不相同, 例如LinkedList LinkedHashMap中的双向列表不再是回环的。 HashMap中的单链表是尾插, 而不是头插入等等, 后文不再赘叙这些差异, 本文目录结构如下: LinkedList 经典...
java为数据结构中的列表定义了一个接口类java.util.list同时提供了3个实现类,分别是ArrayList、Vector、LinkedList使用; 生成不重复的随机数序列;列表、集合与数组的互相转换;java为数据结构中的映射定义一个接口...
源码刻意学习小组[目录]一,学习周期(2个月)时间内容主要类第一周(2019/12 / 09-2019 / 12.15)简单集合ArrayList,HashMap,LinkedList第二周(2019/12 / 16-2019 / 12.22)原子类不安全,AtomicInteger,...
JDK-s-source-parser ## Java的JDK原始解析###完成部分Collection / ArrayList.java由:me 2016-3-31 Collection / LinkedList.java发布者:CBQ 2016-4-4
第四题 ArrayList LinkedList Vector的区别.pdf docker讲得最清楚.doc Dubbo是什么?能做什么?.doc java 基于TCP协议的Socket编程和通信.doc Java面试高级篇—说说TCP,UDP和socket,Http之间联系和区别.doc MySQL...