LinkedList源码分析
1. 数据结构
1.1. 单链表
1.2. 双向链表
LinkedList采用的是双向链表模式,而每一个节点就是一个LinkedList类的一个私有静态的内部类Entry,Entry含有三个成员:E element (E就是申明变量时需要的泛型参数)、Entry next、Entry
previous。
2. 类的申明
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
继承至AbstractSequentialList(此类提供了List接口的骨干实现,从而最大限度减少了实现受“连续访问”数据存储支持的此接口的所需工作)
在实现的接口中Cloneable表示LinkedList能够被复制,实现java.io.Serializable表示此类能被序列化
3. 成员变量分析
private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;
关键字transient的作用是表示一个域不是该对象串行化(序列化)的一部分,当这个对象串行化的时候transient申明的变量不包括在串行化的表示中,而非transient的变量会被包括进去。
4. 构造函数分析
/**
* Constructs an empty list. //构造一个空链表
*/
public LinkedList() {
header.next = header.previous = header;
}
public LinkedList(Collection<? extends E> c) {
this(); //首先构造一个空链表
addAll(c); //将初始化的Collection加入到此链表中
}
5. 成员方法分析
5.1. 增加元素
LinkedList提供像链表中增加元素的方法有很多,例如:add(e)、add(int,e)、addAll(int,Collection)、addAll(Collection),只需分析add(int,e)以及addAll(int,Collection)即可,其余的都是基于这两个函数实现的。
5.1.1. Add(int,e)
public void add(int index, E element) {
addBefore(element, (index==size ? header : entry(index)));
}
entry(index)将在链表中返回位置是index的链表元素,因为链表不像数组可以随机读取,对于链表来说得到某一位置的元素只能一个一个遍历得到位置,然后将前后位置元素的索引改变,而LinkedList是一个双向链表,在寻找插入位置的时候,会判断是位于前半部分还是后半部分,如果是前半部分则从第一个往后遍历,如果是后半部分则有最后一个往前遍历,然后将位置属于index的元素返回。
addBefore(E e,Entry entry)
private Entry<E> addBefore(E e, Entry<E> entry) {
//将newEntry的next指向entry,previous指向尾部entry的尾部
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
//将entry前面元素的后驱指向newEntry
newEntry.previous.next = newEntry;
//将entry元素的前驱指向newEntry
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
对于add(E e)则是调用方法addBefore(e,header)
5.1.2. addAll(int,Collection)
public boolean addAll(int index, Collection<? extends E> c) {
//验证链表的长度与要插入的位置的大小
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
//将要插入的Collection转换成数组
Object[] a = c.toArray();
int numNew = a.length;
if (numNew==0)
return false;
modCount++;//是AbstractList中得一个字段,用来记录list结构变化的次数
//得到index位置的entry
Entry<E> successor = (index==size ? header : entry(index));
Entry<E> predecessor = successor.previous;
//依次将c插入原链表中
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;
}
5.2. 删除元素
仅分析remove(Entry<E> e),因为其余有关删除的操作都是基于这个函数实现的
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;
}
6. 迭代器
与ArrayList不同的是LinkedList实现了自己的迭代器,实现了ListIterator接口,ListIterator接口继承至Iterator接口,LinkedList,没有直接使用AbstractList虚类中的实现,LinkedList内部自定义了一个内部类ListItr,该类实现了ListIterator接口,专门对LinkedList进行迭代,但是要注意的是因为ArrayList与LinkedList的迭代器的功能和特点都是一样的,所以符合ArrayList迭代器的特点都符合LinkedList的特点。AbstractList实现了两个迭代器分别是Itr以及ListItr,其中ListItr更适用于LinkedList,因为LinkedList是一个双向链表。以下是LinkedList中的:ListIterator的实现:
private class LinkedList implements ListIterator<E> {
//最近一次next或previous操作所返回的元素,初始为头结点,表示链表的开始与结尾
private Entry<E> lastReturned = header;
//next操作所返回的节点
private Entry<E> next;
//记录当前next指向的entry的位置,与next保持一致
private int nextIndex;
//检测外界是否改变结合的结构
private int expectedModCount = modCount;
//得到第index位置的元素(entry)
ListItr(int index) {
//此方法运行完毕next指向的就是index位置的元素
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
if (index < (size >> 1)) { //当index小于size的一半是在前半部找
next = header.next; //从第一个元素开始
for (nextIndex=0; nextIndex<index; nextIndex++)
next = next.next;
} else {
next = header;
for (nextIndex=size; nextIndex>index; nextIndex--)
next = next.previous;
}
}
public boolean hasNext() {
return nextIndex != size;
}
public E next() {
checkForComodification();
if (nextIndex == size)
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
//执行next的结果是next与lastReturned不相等
nextIndex++;
return lastReturned.element;
}
public boolean hasPrevious() {
return nextIndex != 0;
}
public E previous() {
if (nextIndex == 0)
throw new NoSuchElementException();
//执行previous的结果是next与lastReturned不相等
lastReturned = next = next.previous;
nextIndex--;
checkForComodification();
return lastReturned.element;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex-1;
}
public void remove() {
checkForComodification();
Entry<E> lastNext = lastReturned.next;
try {
LinkedList.this.remove(lastReturned);
} catch (NoSuchElementException e) {
throw new IllegalStateException();
}
if (next==lastReturned)
next = lastNext;
else
nextIndex--;
//每次remove操作之后就会将lastReturned指向header
lastReturned = header;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == header)
throw new IllegalStateException();
checkForComodification();
lastReturned.element = e;
}
public void add(E e) {
checkForComodification();
//每次add操作之后就会将lastReturned指向header
lastReturned = header;
addBefore(e, next);
nextIndex++;
expectedModCount++;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
从源码中可以看出:
1. 刚实例化的迭代器lastReturned是指向header节点的,是不能马上进行删除跟修改操作的,需要首先进行后移或者前移操作;
2. 只要lastReturned指向header是不能进行删除以及修改操作的,所以以下成立:
可以对迭代器进行连续的添加或者修改,但是不能进行连续的删除,因为删除后lastReturned指向header是不能再删除的;
进行添加操作后不能立刻进行删除或者修改操作;
进行删除操作操作后可以进行添加操作,但是不能进行修改操作;
进行修改后是可以进行删除和增加操作的;
分享到:
相关推荐
主要为大家详细介绍了Java集合系列之LinkedList源码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
能学到什么:ArrayList的源码分析,自动扩容和自动缩容的源码分析,相关参数的深度解析,从是什么,为什么,怎么做三个角度进行讲解,用通俗易懂的白话进行介绍,LinkedList和Vector以及ArrayList的区别以及使用场景...
计算机后端-Java-Java核心基础-第24章 集合01 15. LinkedList的源码分析.avi
*文件名:GreedSnake.java *作者:C.Jason *要点分析: *1)主要部分已经集成为一个对象SnakeModel,利用键盘控制实现操作。 *文件名:SnakeModel.java *作者:C.Jason *要点分析: *1)数据结构:matrix[][]用来...
LinkedList源码分析,java作业,主要是对rar包中的LinkedList分析
Java API中提供了链表的Java实现—LinkedList下。LinkedList是通过节点的连接实现链表的数据结构,向linkedList中插入或删除元素的速度是特别快,而随机访问的速度相对较慢,这个是由于链表本身的性质造成的,在链表...
简介 LinkedList 是一个常用的集合类,用于顺序存储元素。 LinkedList 经常和 ArrayList 一起被提及。...本文分析 LinkedList 的具体实现。 继承关系 public class LinkedList extends AbstractS
Collections 源码 java Java Java的ArrayList、LinkedList、HashMap、TreeMap、LinkedHashMap、HashSet、TreeSet相关源码分析,及相关问题和应用总结。
主要介绍了Java中ArrayList与LinkedList列表结构的源码,文章最后对LinkedList和ArrayList以及Vector的特性有一个对比总结,需要的朋友可以参考下
主要给大家介绍了关于Java基于JDK 1.8的LinkedList源码的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
word源码java ...源码分析(LinkedList) LRU Cache - Linked list: LRU 缓存机制 Redis - Skip List:跳跃表、为啥 Redis 使用跳表(Skip List)而不是使用 Red-Black? Java 的 PriorityQueue 文档 ...
│ │ 13.RPC底层通讯原理之Netty线程模型源码分析.wmv │ │ │ ├─14.分库分表之后分布式下如何保证ID全局唯一性 │ │ 14.分库分表之后分布式下如何保证ID全局唯一性.mp4 │ │ │ └─15.大型公司面试必答之...
主要介绍了java LinkedList源码详解及实例的相关资料,需要的朋友可以参考下
主要给大家介绍了ArrayList和LinkedList这两种list的五种循环遍历方式,各种方式的性能测试对比,根据ArrayList和LinkedList的源码实现分析性能结果,总结结论。相信对大家的理解和学习具有一定的参考价值,有需要的...
java8 源码 List相关实现类的源码解析(JDK1.8) 2018.9.22- List的架构图 ArrayList 继承关系: ArrayList -> AbstractList ...与Java中的数组相比,它的容量能动态增长。...LinkedList 继承关系: LinkedLis
Source code analysis for Java or JDK 记录一些重要的JDK/Java相关的源码分析。 Java 集合框架 ArrayList LinkedList HashMap 参考文章:
bitset源码Java源码分析 基础集合列表 ArrayList (done) Vector (done) LinkedList (done) Stack (done) ReferenceQueue (done) ArrayDeque (done) Set HashSet (done) TreeSet (done) LinkedHashSet (done) BitSet ...
集合源码分析 JAVA: 基本语法 static 修饰变量 方法 静态块(初始化块 构造函数 ) 静态内部类() 静态导包 final() transient() foreach循环原理() volatile底层实现() equals和hashcode(, ) string,stringbuffer和...
集合源码分析 java基础复习 [TOC] 一、集合 1.Iterator 2.Collection 2.1 List--->有序、有索引、元素可重复 1.ArrayList: 底层是数组结构、查询快、增删慢、不同步 添加第一个元素的时候,创建默认个数是10个,...
源码分析:ArrayList、Vector、LinkedList、HashMap、ConcurrentHashMap、HashSet、LinkedHashSet and LinkedHashMap 线程状态、线程机制、线程通信、J.U.C 组件、JMM、线程安全、锁优化 磁盘操作、字节操作、字符...