1.初始化一个空的节点header:
private transient Entry<E> header = new Entry<E>(null, null, null);
该节点在《算法导论》里应该叫“哨兵节点”。
2.初始化一个空的LinkedList,即设置header节点的前后节点都是空。
/**
* Constructs an empty list.
*/
public LinkedList() {
header.next = header.previous = header;
}
3.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.
4.主要的api包含删除元素,添加元素等,有许多重载方法。
1)删除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;
}
2)删除指定位置的节点。
public E remove(int index) {
return remove(entry(index));
}
首先根据索引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;
}
这里的技巧是,先判断index在LinkedList中是前半部分还是后半部分,如果前半部分就从头往后遍历,反之从后往前遍历,可以这么做的原因是该LinkedList是双向链表。
接下来的删除节点就比较简单了。
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;
}
先保存节点的数据E result = e.element;最后返回。
主要的操作是,让该节点的前一节点指向该节点的后一节点;
让该节点的后一节点的前一节点指向该节点的前一节点;
然后将该节点的前后节点置为空,节点数据也置为空;
链表的节点数减一,链表的修改次数加一。
返回之前保存的节点数据,删除操作结束。
3)在指定的位置index插入一个集合Collection c。
主要是将集合c转换为数组,遍历数组元素;
如果正好是在最后的位置(即index==size)插入,那么直接在header前面插入即可,因为LinkedList是一个双向链表。
否则,那么在指定的index之前插入,然后遍历集合数组,依次在此插入各个元素。
public boolean addAll(int index, Collection<? extends E> c) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew==0)
return false;
modCount++;
Entry<E> successor = (index==size ? header : entry(index));
Entry<E> predecessor = successor.previous;
for (int i=0; i<numNew; i++) {
Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
predecessor.next = e;
predecessor = e;
}
successor.previous = predecessor;
size += numNew;
return true;
}
4)clear()方法,删除所有的节点
遍历该LinkedList,设置每个节点的前后节点及element为null
最后设置header前点的前后节点为null
public void clear() {
Entry<E> e = header.next;
while (e != header) {
Entry<E> next = e.next;
e.next = e.previous = null;
e.element = null;
e = next;
}
header.next = header.previous = header;
size = 0;
modCount++;
}
就列举这么多吧。
分享到:
相关推荐
源码解析jdk7.0集合:LinkedList的底层实现原理.pdf
jdk源码学习 JavaSourceLearn 版本号 版本 corretto-1.8.0_275 方式 逐步阅读源码添加注释、notes文件夹添加笔记 计划学习任务计划 标题为包名,后面序号为优先级1-4,优先级递减 java.lang Object 1 String 1 ...
这是我从JDK中拿出的Arraylist,Vector,LinkedList源码,自己看源码的时候弄出来的,并写了一点自己的分析,仅供源码分析者使用
主要给大家介绍了关于Java基于JDK 1.8的LinkedList源码的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
leetcode中文官网链接 前言 由于在面试过程中,有关数据结构的题都回答的不是很好,再加上工作和...阅读jdk源码 LinkedList ArrayList 刷题:剑指offer或者leetCode 剑指offer,刷题可以使用 leetCode,刷题可以使用
NULL 博文链接:https://brokendreams.iteye.com/blog/1916061
本仓库记录了我的Java学习进阶之路,涵盖了Java基础、JDK源码、JVM中的重要知识,附有代码和博客讲解,旨在提供一个Java在线共享学习平台,帮助更多的Java学习入门者进阶。 Java学习 本仓库记录了我的Java学习进阶...
JDK-s-source-parser ## Java的JDK原始解析###完成部分Collection / ArrayList.java由:me 2016-3-31 Collection / LinkedList.java发布者:CBQ 2016-4-4
java jdk1.8 源码 Java-source-reading 缓慢更新一些个人学习java相关源码过程中的笔记,在这里你将不可避免地看到以下情况: 个别不懂/没想好的地方留空待补全 ...LinkedList HashMap HashSet LinkedHashMap
文章目录Collection源码剖析(一)简介(二)源码分析 Collection源码剖析 ...JDK不提供此接口的任何直接实现:它提供了更具体的子接口(如Set和List)的实现。 (2)Collection的继承体系 关于Ite
从无到有手写LinkedList,深入理解JDK源码,并实现自己的数据结构。
jdk1.8.0_151-源码的中文翻译和一些自己的理解 声明 作者现在大四快要毕业,在实习中,为了在未来成为一名架构师,下定决心开始读Java的源代码;读源码的过程非常难熬,我在以前也曾读过源码,但都坚持的不久,也...
JDK源码学习 JDK版本基于1.7 集合框架的学习 ArrayList原始码学习 HashMap原始码学习 LinkedList原始码学习 HashSet原始码学习 LinkedHashMap原始学习 LinkedHashSet原始码学习
Source code analysis for Java or JDK 记录一些重要的JDK/Java相关的源码分析。 Java 集合框架 ArrayList LinkedList HashMap 参考文章:
List相关实现类的源码解析(JDK1.8) 2018.9.22- List的架构图 ArrayList 继承关系: ArrayList -> AbstractList 实现 List接口 ArrayList 是一个数组队列,相当于 动态数组。与Java中的数组相比,它的容量能动态...
LinkedList ctor-2 addFirst addLast addAll add indexOf lastIndexOf peek 获取第一个元素,是 null 就返回 null peekFirst/Last 获取第一个最后一个元素 poll 删除第一个元素并返回 没有返回 null pollFirst/Last ...
全部代码出自电子工业出版社夏先波的《Java JDK实例宝典》一书,本书以J2SE 5.0为开发环境,选取Java应用的典型实例,循序渐进地介绍了Java语言的各种开发方法和技巧,实例代码注释详细规范,思路清晰。 第1章 ...
说明:如无特别说明,所有代码都基于JDK8 JavaSE(Java基础) Java Core 关键字 synchronized关键字 Java String Java Arrays Java Collections Java 泛型 Java NIO Buffer Channel Selector Java 8 Features 源码解读...
JDK源码学习: Java 容器 ArrayList LinkedList PriorityQueue HashMap LinkedHashMap ConcurrentHashMap J.U.C包 AQS CountDownLatch CyclicBarrier Semaphore ForkJoin FutureTask BlockingQueue Spring AOP IOC ...
·基于JDK 11,将Java8、Java9、Java10、Java11新特性一网打尽 ·课程中,Eclipse和IDEA这两种企业一线开发环境都使用到了 3.技术讲解更深入、更全面: ·课程共30天,715个知识视频小节,涉及主流Java使用的...