来看Java汇合源码分析：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[i],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[size];
inti=0;
//将链表中一切节点的数据都增加到Object[]数组中
for(Entry<E>e=header.next;e!=header;e=e.next)
result[i++]=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[i++]=e.element;
if(a.length>size)
a[size]=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);
}
}

复制代码