java LinkedList源码详解及实例
一、LinkedList概述:
LinkedList与ArrayList一样,是实现了List接口。由于LinkedList是基于链表实现的,所以它执行插入和删除操作时比ArrayList更高效,而随机访问的性能要比ArrayList低。
二、LinkedList的实现:
1、构造方法
//构造一个空的LinkedList publicLinkedList(){ } //接收一个Collection参数c,默认构造方法构造一个空的链表,并通过addAll将c中的元素全部添加到链表中。 publicLinkedList(Collectionc){ this(); addAll(c); }
2、一些方法
2.1getFirst()
//获取LinkedList第一个元素,如果LinkedList为空,则抛出异常。 publicEgetFirst(){ finalNodef=first; if(f==null) thrownewNoSuchElementException(); returnf.item; }
2.2getLast()
//获取getLast()最后一个元素,如果LinkedList为空,则抛出异常。 publicEgetLast(){ finalNodel=last; if(l==null) thrownewNoSuchElementException(); returnl.item; }
2.3removeFirst()
//删除LinkedList第一个元素,如果LinkedList为空,则抛出异常。 publicEremoveFirst(){ finalNodef=first; if(f==null) thrownewNoSuchElementException(); returnunlinkFirst(f); }
2.4removeLast()
//删除LinkedList最后一个元素,如果LinkedList为空,则抛出异常。 publicEremoveLast(){ finalNodel=last; if(l==null) thrownewNoSuchElementException(); returnunlinkLast(l); }
2.5addFirst(Ee)
//在LinkedList开始的位置插入一个新元素。 publicvoidaddFirst(Ee){ linkFirst(e); }
2.6addLast(Ee)
//在LinkedList末尾的位置插入一个新的元素。 publicvoidaddLast(Ee){ linkLast(e); }
2.7contains(Objecto)
//判断LinkedList中是否包含某个元素,若包含返回True,否则返回False publicbooleancontains(Objecto){ returnindexOf(o)!=-1; }
2.8add(Ee)
//在LinkedList末尾处添加一个新的元素。 publicbooleanadd(Ee){ linkLast(e); returntrue; }
2.9remove(Objecto)
//删除LinkedList中第一个出现的指定元素,如果LinkedList中不包含该元素,则链表保持不变。 publicbooleanremove(Objecto){ if(o==null){ for(Nodex=first;x!=null;x=x.next){ if(x.item==null){ unlink(x); returntrue; } } }else{ for(Node x=first;x!=null;x=x.next){ if(o.equals(x.item)){ unlink(x); returntrue; } } } returnfalse; }
2.10addAll()
//增加Collection中的所有元素, publicbooleanaddAll(Collectionc){ returnaddAll(size,c); } //index参数指定collection中插入的第一个元素的位置 publicbooleanaddAll(intindex,Collectionc){ checkPositionIndex(index); Object[]a=c.toArray(); intnumNew=a.length; if(numNew==0) returnfalse; Nodepred,succ; if(index==size){ succ=null; pred=last; }else{ succ=node(index); pred=succ.prev; } for(Objecto:a){ @SuppressWarnings("unchecked")Ee=(E)o; Node newNode=newNode<>(pred,e,null); if(pred==null) first=newNode; else pred.next=newNode; pred=newNode; } if(succ==null){ last=pred; }else{ pred.next=succ; succ.prev=pred; } size+=numNew; modCount++; returntrue; }
2.11clear()
//删除LinkedList中的所有元素。 publicvoidclear(){ //删除LinkedList中所有链接是没有必要的,但是: //可以帮助分代GC,如果删除节点超过一代就会释放内存,因为有一个可用的迭代器。 for(Nodex=first;x!=null;){ Node next=x.next; x.item=null; x.next=null; x.prev=null; x=next; } first=last=null; size=0; modCount++; }
2.12get(intindex)
//获取指定位置的节点 publicEget(intindex){ checkElementIndex(index); returnnode(index).item; }
2.13set(intindex,Eelement)
//给指定节点赋一个指定的值,替换原来的值。 publicEset(intindex,Eelement){ checkElementIndex(index); Nodex=node(index); EoldVal=x.item; x.item=element; returnoldVal; }
2.14add(intindex,Eelement)
//在指定位置插入一个指定的值,原来该位置上以后的节点依次向后移动一位。 publicvoidadd(intindex,Eelement){ checkPositionIndex(index); if(index==size) linkLast(element); else linkBefore(element,node(index)); }
2.15remove(intindex)
//删除指定位置的值,该位置之后的节点依次向前移动一位。 publicEremove(intindex){ checkElementIndex(index); returnunlink(node(index)); }
三、总结
LinkedList,通俗的理解就是数据结构中讲的链表在Java语言中的实现,所以在链表中所有操作,LinkedList中都有,其实现原理也都是基于数据结构中所讲的对链表中的节点插入、删除、移动等方法。
LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList实现List接口,能对它进行队列操作。
LinkedList实现Deque接口,即能将LinkedList当作双端队列使用。
LinkedList实现了Cloneable接口,即覆盖了函数clone(),能克隆。
LinkedList实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
LinkedList是非同步的。
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!