来看Java汇合源码分析：LinkedList源码分析
多谢指点，其实我对.net和ruby也不是很了解，对与java也只是刚起步的阶段，只是在学习中有了点想法就写出来了，现在俺本科还没毕业，所以对大型项目基本上也没有什么经验。LinkedList简介
LinkedList是基于双向轮回链表（从源码中能够很简单看出）完成的，除能够当作链表来操纵外，它还能够当作栈、行列和双端行列来利用。
LinkedList一样长短线程平安的，只在单线程下合适利用。
LinkedList完成了Serializable接口，因而它撑持序列化，可以经由过程序列化传输，完成了Cloneable接口，能被克隆。
LinkedList源码分析
LinkedList的源码以下（到场了对照具体的正文）：
packagejava.util;
publicclassLinkedList<E>
extendsAbstractSequentialList<E>
implementsList<E>,Deque<E>,Cloneable,java.io.Serializable
{
//链表的表头，表头不包括任何数据。Entry是个链表类数据布局。
privatetransientEntry<E>header=newEntry<E>(null,null,null);
//LinkedList中元素个数
privatetransientintsize=0;
//默许机关函数：创立一个空的链表
publicLinkedList(){
header.next=header.previous=header;
}
//包括“汇合”的机关函数:创立一个包括“汇合”的LinkedList
//本栏目更多出色内容：http://www.bianceng.cn/Programming/Java/
publicLinkedList(Collection<?extendsE>c){
this();
addAll(c);
}
//猎取LinkedList的第一个元素
publicEgetFirst(){
if(size==0)
thrownewNoSuchElementException();
//链表的表头header中不包括数据。
//这里前往header所指下一个节点所包括的数据。
returnheader.next.element;
}
//猎取LinkedList的最初一个元素
publicEgetLast(){
if(size==0)
thrownewNoSuchElementException();
//因为LinkedList是双向链表；而表头header不包括数据。
//因此，这里前往表头header的前一个节点所包括的数据。
returnheader.previous.element;
}
//删除LinkedList的第一个元素
publicEremoveFirst(){
returnremove(header.next);
}
//删除LinkedList的最初一个元素
publicEremoveLast(){
returnremove(header.previous);
}
//将元素增加到LinkedList的肇端地位
publicvoidaddFirst(Ee){
addBefore(e,header.next);
}
//将元素增加到LinkedList的停止地位
publicvoidaddLast(Ee){
addBefore(e,header);
}
//判别LinkedList是不是包括元素(o)
publicbooleancontains(Objecto){
returnindexOf(o)!=-1;
}
//前往LinkedList的巨细
publicintsize(){
returnsize;
}
//将元素(E)增加到LinkedList中
publicbooleanadd(Ee){
//将节点(节点数据是e)增加到表头(header)之前。
//即，将节点增加到双向链表的末了。
addBefore(e,header);
returntrue;
}
//从LinkedList中删除元素(o)
//从链表入手下手查找，如存在元素(o)则删除该元素并前往true；
//不然，前往false。
publicbooleanremove(Objecto){
if(o==null){
//若o为null的删除情形
for(Entry<E>e=header.next;e!=header;e=e.next){
if(e.element==null){
remove(e);
returntrue;
}
}
}else{
//若o不为null的删除情形
for(Entry<E>e=header.next;e!=header;e=e.next){
if(o.equals(e.element)){
remove(e);
returntrue;
}
}
}
returnfalse;
}
//将“汇合(c)”增加到LinkedList中。
//实践上，是从双向链表的开端入手下手，将“汇合(c)”增加到双向链表中。
publicbooleanaddAll(Collection<?extendsE>c){
returnaddAll(size,c);
}
//从双向链表的index入手下手，将“汇合(c)”增加到双向链表中。
publicbooleanaddAll(intindex,Collection<?extendsE>c){
if(index<0||index>size)
thrownewIndexOutOfBoundsException("Index:"+index+
",Size:"+size);
Object[]a=c.toArray();
//猎取汇合的长度
intnumNew=a.length;
if(numNew==0)
returnfalse;
modCount++;
//设置“以后要拔出节点的后一个节点”
Entry<E>successor=(index==size?header:entry(index));
//设置“以后要拔出节点的前一个节点”
Entry<E>predecessor=successor.previous;
//将汇合(c)全体拔出双向链表中
for(inti=0;i<numNew;i++){
Entry<E>e=newEntry<E>((E)a,successor,predecessor);
predecessor.next=e;
predecessor=e;
}
successor.previous=predecessor;
//调剂LinkedList的实践巨细
size+=numNew;
returntrue;
}
//清空双向链表
publicvoidclear(){
Entry<E>e=header.next;
//从表头入手下手，逐一向后遍历；对遍历到的节点实行一下操纵：
//(01)设置前一个节点为null
//(02)设置以后节点的内容为null
//(03)设置后一个节点为“新确当前节点”
while(e!=header){
Entry<E>next=e.next;
e.next=e.previous=null;
e.element=null;
e=next;
}
header.next=header.previous=header;
//设置巨细为0
size=0;
modCount++;
}
//前往LinkedList指定地位的元素
publicEget(intindex){
returnentry(index).element;
}
//设置index地位对应的节点的值为element
publicEset(intindex,Eelement){
Entry<E>e=entry(index);
EoldVal=e.element;
e.element=element;
returnoldVal;
}
//在index前增加节点，且节点的值为element
publicvoidadd(intindex,Eelement){
addBefore(element,(index==size?header:entry(index)));
}
//删除index地位的节点
publicEremove(intindex){
returnremove(entry(index));
}
//猎取双向链表中指定地位的节点
privateEntry<E>entry(intindex){
if(index<0||index>=size)
thrownewIndexOutOfBoundsException("Index:"+index+
",Size:"+size);
Entry<E>e=header;
//猎取index处的节点。
//若index<双向链表长度的1/2,则夙昔前后查找;
//不然，从后向前查找。
if(index<(size>>1)){
for(inti=0;i<=index;i++)
e=e.next;
}else{
for(inti=size;i>index;i--)
e=e.previous;
}
returne;
}
//夙昔向后查找，前往“值为对象(o)的节点对应的索引”
//不存在就前往-1
publicintindexOf(Objecto){
intindex=0;
if(o==null){
for(Entrye=header.next;e!=header;e=e.next){
if(e.element==null)
returnindex;
index++;
}
}else{
for(Entrye=header.next;e!=header;e=e.next){
if(o.equals(e.element))
returnindex;
index++;
}
}
return-1;
}
//从后向前查找，前往“值为对象(o)的节点对应的索引”
//不存在就前往-1
publicintlastIndexOf(Objecto){
intindex=size;
if(o==null){
for(Entrye=header.previous;e!=header;e=e.previous){
index--;
if(e.element==null)
returnindex;
}
}else{
for(Entrye=header.previous;e!=header;e=e.previous){
index--;
if(o.equals(e.element))
returnindex;
}
}
return-1;
}
//前往第一个节点
//若LinkedList的巨细为0,则前往null
publicEpeek(){
if(size==0)
returnnull;
returngetFirst();
}
//前往第一个节点
//若LinkedList的巨细为0,则抛出非常
publicEelement(){
returngetFirst();
}
//删除并前往第一个节点
//若LinkedList的巨细为0,则前往null
publicEpoll(){
if(size==0)
returnnull;
returnremoveFirst();
}
//将e增加双向链表开端
publicbooleanoffer(Ee){
returnadd(e);
}
//将e增加双向链表开首
publicbooleanofferFirst(Ee){
addFirst(e);
returntrue;
}
//将e增加双向链表开端
publicbooleanofferLast(Ee){
addLast(e);
returntrue;
}
//前往第一个节点
//若LinkedList的巨细为0,则前往null
publicEpeekFirst(){
if(size==0)
returnnull;
returngetFirst();
}
//前往最初一个节点
//若LinkedList的巨细为0,则前往null
publicEpeekLast(){
if(size==0)
returnnull;
returngetLast();
}
//删除并前往第一个节点
//若LinkedList的巨细为0,则前往null
publicEpollFirst(){
if(size==0)
returnnull;
returnremoveFirst();
}
//删除并前往最初一个节点
//若LinkedList的巨细为0,则前往null
publicEpollLast(){
if(size==0)
returnnull;
returnremoveLast();
}
//将e拔出到双向链表开首
publicvoidpush(Ee){
addFirst(e);
}
//删除并前往第一个节点
publicEpop(){
returnremoveFirst();
}
//从LinkedList入手下手向后查找，删除第一个值为元素(o)的节点
//从链表入手下手查找，如存在节点的值为元素(o)的节点，则删除该节点
publicbooleanremoveFirstOccurrence(Objecto){
returnremove(o);
}
//从LinkedList开端向前查找，删除第一个值为元素(o)的节点
//从链表入手下手查找，如存在节点的值为元素(o)的节点，则删除该节点
publicbooleanremoveLastOccurrence(Objecto){
if(o==null){
for(Entry<E>e=header.previous;e!=header;e=e.previous){
if(e.element==null){
remove(e);
returntrue;
}
}
}else{
for(Entry<E>e=header.previous;e!=header;e=e.previous){
if(o.equals(e.element)){
remove(e);
returntrue;
}
}
}
returnfalse;
}
//前往“index到开端的全体节点”对应的ListIterator对象(List迭代器)
publicListIterator<E>listIterator(intindex){
returnnewListItr(index);
}
//List迭代器
privateclassListItrimplementsListIterator<E>{
//上一次前往的节点
privateEntry<E>lastReturned=header;
//下一个节点
privateEntry<E>next;
//下一个节点对应的索引值
privateintnextIndex;
//希冀的改动计数。用来完成fail-fast机制。
privateintexpectedModCount=modCount;
//机关函数。
//从index地位入手下手举行迭代
ListItr(intindex){
//index的无效性处置
if(index<0||index>size)
thrownewIndexOutOfBoundsException("Index:"+index+",Size:"+size);
//若“index小于‘双向链表长度的一半’”，则从第一个元素入手下手今后查找；
//不然，从最初一个元素往前查找。
if(index<(size>>1)){
next=header.next;
for(nextIndex=0;nextIndex<index;nextIndex++)
next=next.next;
}else{
next=header;
for(nextIndex=size;nextIndex>index;nextIndex--)
next=next.previous;
}
}
//是不是存鄙人一个元素
publicbooleanhasNext(){
//经由过程元素索引是不是即是“双向链表巨细”来判别是不是到达最初。
returnnextIndex!=size;
}
//猎取下一个元素
publicEnext(){
checkForComodification();
if(nextIndex==size)
thrownewNoSuchElementException();
lastReturned=next;
//next指向链表的下一个元素
next=next.next;
nextIndex++;
returnlastReturned.element;
}
//是不是存在上一个元素
publicbooleanhasPrevious(){
//经由过程元素索引是不是即是0，来判别是不是到达开首。
returnnextIndex!=0;
}
//猎取上一个元素
publicEprevious(){
if(nextIndex==0)
thrownewNoSuchElementException();
//next指向链表的上一个元素
lastReturned=next=next.previous;
nextIndex--;
checkForComodification();
returnlastReturned.element;
}
//猎取下一个元素的索引
publicintnextIndex(){
returnnextIndex;
}
//猎取上一个元素的索引
publicintpreviousIndex(){
returnnextIndex-1;
}
//删除以后元素。
//删除双向链表中确当前节点
publicvoidremove(){
checkForComodification();
Entry<E>lastNext=lastReturned.next;
try{
LinkedList.this.remove(lastReturned);
}catch(NoSuchElementExceptione){
thrownewIllegalStateException();
}
if(next==lastReturned)
next=lastNext;
else
nextIndex--;
lastReturned=header;
expectedModCount++;
}
//设置以后节点为e
publicvoidset(Ee){
if(lastReturned==header)
thrownewIllegalStateException();
checkForComodification();
lastReturned.element=e;
}
//将e增加到以后节点的后面
publicvoidadd(Ee){
checkForComodification();
lastReturned=header;
addBefore(e,next);
nextIndex++;
expectedModCount++;
}
//判别“modCount和expectedModCount是不是相称”，顺次来完成fail-fast机制。
finalvoidcheckForComodification(){
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
}
}
//双向链表的节点所对应的数据布局。
//包括3部分：上一节点，下一节点，以后节点值。
privatestaticclassEntry<E>{
//以后节点所包括的值
Eelement;
//下一个节点
Entry<E>next;
//上一个节点
Entry<E>previous;
/**
*链表节点的机关函数。
*参数申明：
*element——节点所包括的数据
*next——下一个节点
*previous——上一个节点
*/
Entry(Eelement,Entry<E>next,Entry<E>previous){
this.element=element;
this.next=next;
this.previous=previous;
}
}
//将节点(节点数据是e)增加到entry节点之前。
privateEntry<E>addBefore(Ee,Entry<E>entry){
//新建节点newEntry，将newEntry拔出到节点e之前；而且设置newEntry的数据是e
Entry<E>newEntry=newEntry<E>(e,entry,entry.previous);
newEntry.previous.next=newEntry;
newEntry.next.previous=newEntry;
//修正LinkedList巨细
size++;
//修正LinkedList的修正统计数：用来完成fail-fast机制。
modCount++;
returnnewEntry;
}
//将节点从链表中删除
privateEremove(Entry<E>e){
if(e==header)
thrownewNoSuchElementException();
Eresult=e.element;
e.previous.next=e.next;
e.next.previous=e.previous;
e.next=e.previous=null;
e.element=null;
size--;
modCount++;
returnresult;
}
//反向迭代器
publicIterator<E>descendingIterator(){
returnnewDescendingIterator();
}
//反向迭代器完成类。
privateclassDescendingIteratorimplementsIterator{
finalListItritr=newListItr(size());
//反向迭代器是不是下一个元素。
//实践上是判别双向链表确当前节点是不是到达开首
publicbooleanhasNext(){
returnitr.hasPrevious();
}
//反向迭代器猎取下一个元素。
//实践上是猎取双向链表的前一个节点
publicEnext(){
returnitr.previous();
}
//删除以后节点
publicvoidremove(){
itr.remove();
}
}
//前往LinkedList的Object[]数组
publicObject[]toArray(){
//新建Object[]数组
Object[]result=newObject;
inti=0;
//将链表中一切节点的数据都增加到Object[]数组中
for(Entry<E>e=header.next;e!=header;e=e.next)
result=e.element;
returnresult;
}
//前往LinkedList的模板数组。所谓模板数组，便可以将T设为恣意的数据范例
public<T>T[]toArray(T[]a){
//若数组a的巨细<LinkedList的元素个数(意味着数组a不克不及包容LinkedList中全体元素)
//则新建一个T[]数组，T[]的巨细为LinkedList巨细，并将该T[]赋值给a。
if(a.length<size)
a=(T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(),size);
//将链表中一切节点的数据都增加到数组a中
inti=0;
Object[]result=a;
for(Entry<E>e=header.next;e!=header;e=e.next)
result=e.element;
if(a.length>size)
a=null;
returna;
}
//克隆函数。前往LinkedList的克隆对象。
publicObjectclone(){
LinkedList<E>clone=null;
//克隆一个LinkedList克隆对象
try{
clone=(LinkedList<E>)super.clone();
}catch(CloneNotSupportedExceptione){
thrownewInternalError();
}
//新建LinkedList表头节点
clone.header=newEntry<E>(null,null,null);
clone.header.next=clone.header.previous=clone.header;
clone.size=0;
clone.modCount=0;
//将链表中一切节点的数据都增加到克隆对象中
for(Entry<E>e=header.next;e!=header;e=e.next)
clone.add(e.element);
returnclone;
}
//java.io.Serializable的写进函数
//将LinkedList的“容量，一切的元素值”都写进到输入流中
privatevoidwriteObject(java.io.ObjectOutputStreams)
throwsjava.io.IOException{
//Writeoutanyhiddenserializationmagic
s.defaultWriteObject();
//写进“容量”
s.writeInt(size);
//将链表中一切节点的数据都写进到输入流中
for(Entrye=header.next;e!=header;e=e.next)
s.writeObject(e.element);
}
//java.io.Serializable的读取函数：依据写进体例反向读出
//先将LinkedList的“容量”读出，然后将“一切的元素值”读出
privatevoidreadObject(java.io.ObjectInputStreams)
throwsjava.io.IOException,ClassNotFoundException{
//Readinanyhiddenserializationmagic
s.defaultReadObject();
//从输出流中读取“容量”
intsize=s.readInt();
//新建链表表头节点
header=newEntry<E>(null,null,null);
header.next=header.previous=header;
//从输出流中将“一切的元素值”并逐一增加到链表中
for(inti=0;i<size;i++)
addBefore((E)s.readObject(),header);
}
}几点总结
关于LinkedList的源码，给出几点对照主要的总结：
<p>
微软什么都提供了。你可以试想一下，如果你是新手，你是希望你点一下按钮程序就能运行那，还是想自己一点一点的组织结构，然后打包发部，调错再打包...... 你一定会高兴地说，哈哈，原来成为Java高手就这么简单啊!记得Tomjava也曾碰到过一个项目经理，号称Java很简单，只要三个月就可以学会。 是一种将安全性(Security)列为第一优先考虑的语言 多重继承（以接口取代）等特性，增加了垃圾回收器功能用于回收不再被引用的对象所占据的内存空间，使得程序员不用再为内存管理而担忧。在 Java 1.5 版本中，Java 又引入了泛型编程（Generic Programming）、类型安全的枚举、不定长参数和自动装/拆箱等语言特性。 Java自面世后就非常流行，发展迅速，对C++语言形成了有力冲击。Java 技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于个人PC、数据中心、游戏控制台 是一种使网页(Web Page)产生生动活泼画面的语言 至于JDBC，就不用我多说了，你如果用java编过存取数据库的程序，就应该很熟悉。还有，如果你要用Java编发送电子邮件的程序，你就得看看Javamail 了。 科学超级计算机、移动电话和互联网，同时拥有全球最大的开发者专业社群。 Jive的资料在很多网站上都有，大家可以找来研究一下。相信你读完代码后，会有脱胎换骨的感觉。遗憾的是Jive从2.5以后就不再无条件的开放源代码，同时有licence限制。不过幸好还有中国一流的Java程序员关注它，外国人不开源了，中国人就不能开源吗？这里向大家推荐一个汉化的Jive版本—J道。Jive(J道版)是由中国Java界大名 鼎鼎的banq在Jive 2.1版本基础上改编而成, 全中文，增加了一些实用功能，如贴图，用户头像和用户资料查询等，而且有一个开发团队在不断升级。你可以访问banq的网站
页:
[1]