簡(jiǎn)介
LinkedList是一個(gè)實(shí)現(xiàn)了List接口和Deque接口的雙端鏈表呻畸。 LinkedList底層的鏈表結(jié)構(gòu)使它支持高效的插入和刪除操作，另外它實(shí)現(xiàn)了Deque接口堪澎，使得LinkedList類也具有隊(duì)列的特性; LinkedList不是線程安全的擂错，如果想使LinkedList變成線程安全的，可以調(diào)用靜態(tài)類Collections類中的synchronizedList方法：
Listlist=Collections.synchronizedList(newLinkedList(...));
如下圖所示：??看完了圖之后樱蛤，我們?cè)倏碙inkedList類中的一個(gè)內(nèi)部私有類Node就很好理解了：
privatestaticclassNode {Eitem;//節(jié)點(diǎn)值Nodenext;//后繼節(jié)點(diǎn)Nodeprev;//前驅(qū)節(jié)點(diǎn)Node(Nodeprev,Eelement,Nodenext) {this.item=element;this.next=next;this.prev=prev;? ? ? ? }? ? }
這個(gè)類就代表雙端鏈表的節(jié)點(diǎn)Node。這個(gè)類有三個(gè)屬性剑鞍，分別是前驅(qū)節(jié)點(diǎn)昨凡，本節(jié)點(diǎn)的值，后繼結(jié)點(diǎn)蚁署。
空構(gòu)造方法：
publicLinkedList() {? ? }
用已有的集合創(chuàng)建鏈表的構(gòu)造方法：
publicLinkedList(Collectionc) {this();? ? ? ? addAll(c);? ? }
add(E e)?方法：將元素添加到鏈表尾部
publicbooleanadd(Ee) {? ? ? ? linkLast(e);//這里就只調(diào)用了這一個(gè)方法returntrue;? ? }
/**? ? * 鏈接使e作為最后一個(gè)元素便脊。*/voidlinkLast(Ee) {finalNodel=last;finalNodenewNode=newNode<>(l, e,null);? ? ? ? last=newNode;//新建節(jié)點(diǎn)if(l==null)? ? ? ? ? ? first=newNode;elsel.next=newNode;//指向后繼元素也就是指向下一個(gè)元素size++;? ? ? ? modCount++;? ? }
add(int index,E e)：在指定位置添加元素
publicvoidadd(intindex,Eelement) {? ? ? ? checkPositionIndex(index);//檢查索引是否處于[0-size]之間if(index==size)//添加在鏈表尾部linkLast(element);else//添加在鏈表中間linkBefore(element, node(index));? ? }
linkBefore方法需要給定兩個(gè)參數(shù)，一個(gè)插入節(jié)點(diǎn)的值光戈，一個(gè)指定的node哪痰，所以我們又調(diào)用了Node(index)去找到index對(duì)應(yīng)的node
addAll(Collection c )：將集合插入到鏈表尾部
publicbooleanaddAll(Collectionc) {returnaddAll(size, c);? ? }
addAll(int index, Collection c)：?將集合從指定位置開始插入
publicbooleanaddAll(intindex,Collectionc) {//1:檢查index范圍是否在size之內(nèi)checkPositionIndex(index);//2:toArray()方法把集合的數(shù)據(jù)存到對(duì)象數(shù)組中Object[] a=c.toArray();intnumNew=a.length;if(numNew==0)returnfalse;//3：得到插入位置的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)Nodepred, succ;//如果插入位置為尾部，前驅(qū)節(jié)點(diǎn)為last久妆，后繼節(jié)點(diǎn)為nullif(index==size) {? ? ? ? ? ? succ=null;? ? ? ? ? ? pred=last;? ? ? ? }//否則晌杰，調(diào)用node()方法得到后繼節(jié)點(diǎn)，再得到前驅(qū)節(jié)點(diǎn)else{? ? ? ? ? ? succ=node(index);? ? ? ? ? ? pred=succ.prev;? ? ? ? }//4：遍歷數(shù)據(jù)將數(shù)據(jù)插入for(Objecto:a) {@SuppressWarnings("unchecked")Ee=(E) o;//創(chuàng)建新節(jié)點(diǎn)NodenewNode=newNode<>(pred, e,null);//如果插入位置在鏈表頭部if(pred==null)? ? ? ? ? ? ? ? first=newNode;elsepred.next=newNode;? ? ? ? ? ? pred=newNode;? ? ? ? }//如果插入位置在尾部筷弦，重置last節(jié)點(diǎn)if(succ==null) {? ? ? ? ? ? last=pred;? ? ? ? }//否則肋演，將插入的鏈表與先前鏈表連接起來(lái)else{? ? ? ? ? ? pred.next=succ;? ? ? ? ? ? succ.prev=pred;? ? ? ? }? ? ? ? size+=numNew;? ? ? ? modCount++;returntrue;? ? }
上面可以看出addAll方法通常包括下面四個(gè)步驟：
檢查index范圍是否在size之內(nèi)
toArray()方法把集合的數(shù)據(jù)存到對(duì)象數(shù)組中
得到插入位置的前驅(qū)和后繼節(jié)點(diǎn)
遍歷數(shù)據(jù)，將數(shù)據(jù)插入到指定位置
addFirst(E e)：?將元素添加到鏈表頭部
publicvoidaddFirst(Ee) {? ? ? ? linkFirst(e);? ? }
privatevoidlinkFirst(Ee) {finalNodef=first;finalNodenewNode=newNode<>(null, e, f);//新建節(jié)點(diǎn)烂琴，以頭節(jié)點(diǎn)為后繼節(jié)點(diǎn)first=newNode;//如果鏈表為空爹殊，last節(jié)點(diǎn)也指向該節(jié)點(diǎn)if(f==null)? ? ? ? ? ? last=newNode;//否則，將頭節(jié)點(diǎn)的前驅(qū)指針指向新節(jié)點(diǎn)奸绷，也就是指向前一個(gè)元素elsef.prev=newNode;? ? ? ? size++;? ? ? ? modCount++;? ? }
addLast(E e)：?將元素添加到鏈表尾部梗夸，與?add(E e)?方法一樣
publicvoidaddLast(Ee) {? ? ? ? linkLast(e);? ? }
get(int index)：：根據(jù)指定索引返回?cái)?shù)據(jù)
publicEget(intindex) {//檢查index范圍是否在size之內(nèi)checkElementIndex(index);//調(diào)用Node(index)去找到index對(duì)應(yīng)的node然后返回它的值returnnode(index).item;? ? }
獲取頭節(jié)點(diǎn)（index=0）數(shù)據(jù)方法:
publicEgetFirst() {finalNodef=first;if(f==null)thrownewNoSuchElementException();returnf.item;? ? }publicEelement() {returngetFirst();? ? }publicEpeek() {finalNodef=first;return(f==null)?null:f.item;? ? }publicEpeekFirst() {finalNodef=first;return(f==null)?null:f.item;? ? }
區(qū)別：?getFirst(),element(),peek(),peekFirst() 這四個(gè)獲取頭結(jié)點(diǎn)方法的區(qū)別在于對(duì)鏈表為空時(shí)的處理，是拋出異常還是返回null号醉，其中getFirst()?和element()?方法將會(huì)在鏈表為空時(shí)反症，拋出異常
element()方法的內(nèi)部就是使用getFirst()實(shí)現(xiàn)的。它們會(huì)在鏈表為空時(shí)扣癣，拋出NoSuchElementException?獲取尾節(jié)點(diǎn)（index=-1）數(shù)據(jù)方法:
publicEgetLast() {finalNodel=last;if(l==null)thrownewNoSuchElementException();returnl.item;? ? }publicEpeekLast() {finalNodel=last;return(l==null)?null:l.item;? ? }
兩者區(qū)別：?getLast()?方法在鏈表為空時(shí)惰帽，會(huì)拋出NoSuchElementException，而peekLast()?則不會(huì)父虑，只是會(huì)返回?null该酗。
int indexOf(Object o)：?從頭遍歷找
publicintindexOf(Objecto) {intindex=0;if(o==null) {//從頭遍歷for(Nodex=first; x!=null; x=x.next) {if(x.item==null)returnindex;? ? ? ? ? ? ? ? index++;? ? ? ? ? ? }? ? ? ? }else{//從頭遍歷for(Nodex=first; x!=null; x=x.next) {if(o.equals(x.item))returnindex;? ? ? ? ? ? ? ? index++;? ? ? ? ? ? }? ? ? ? }return-1;? ? }
int lastIndexOf(Object o)：?從尾遍歷找
publicintlastIndexOf(Objecto) {intindex=size;if(o==null) {//從尾遍歷for(Nodex=last; x!=null; x=x.prev) {? ? ? ? ? ? ? ? index--;if(x.item==null)returnindex;? ? ? ? ? ? }? ? ? ? }else{//從尾遍歷for(Nodex=last; x!=null; x=x.prev) {? ? ? ? ? ? ? ? index--;if(o.equals(x.item))returnindex;? ? ? ? ? ? }? ? ? ? }return-1;? ? }
contains(Object o)：?檢查對(duì)象o是否存在于鏈表中
publicbooleancontains(Objecto) {returnindexOf(o)!=-1;? ? }
###刪除方法?remove()?,removeFirst(),pop():?刪除頭節(jié)點(diǎn)
public E pop() {
? ? ? ? return removeFirst();
? ? }
public E remove() {
? ? ? ? return removeFirst();
? ? }
public E removeFirst() {
? ? ? ? final Node<E> f = first;
? ? ? ? if (f == null)
? ? ? ? ? ? throw new NoSuchElementException();
? ? ? ? return unlinkFirst(f);
? ? }
removeLast(),pollLast():?刪除尾節(jié)點(diǎn)
publicEremoveLast() {finalNodel=last;if(l==null)thrownewNoSuchElementException();returnunlinkLast(l);? ? }publicEpollLast() {finalNodel=last;return(l==null)?null:unlinkLast(l);? ? }
區(qū)別：?removeLast()在鏈表為空時(shí)將拋出NoSuchElementException，而pollLast()方法返回null。
remove(Object o):?刪除指定元素
publicbooleanremove(Objecto) {//如果刪除對(duì)象為nullif(o==null) {//從頭開始遍歷for(Nodex=first; x!=null; x=x.next) {//找到元素if(x.item==null) {//從鏈表中移除找到的元素unlink(x);returntrue;? ? ? ? ? ? ? ? }? ? ? ? ? ? }? ? ? ? }else{//從頭開始遍歷for(Nodex=first; x!=null; x=x.next) {//找到元素if(o.equals(x.item)) {//從鏈表中移除找到的元素unlink(x);returntrue;? ? ? ? ? ? ? ? }? ? ? ? ? ? }? ? ? ? }returnfalse;? ? }
當(dāng)刪除指定對(duì)象時(shí)呜魄，只需調(diào)用remove(Object o)即可吗讶，不過該方法一次只會(huì)刪除一個(gè)匹配的對(duì)象悉罕，如果刪除了匹配對(duì)象，返回true，否則false缕溉。
unlink(Node x) 方法：
Eunlink(Nodex) {//assert x != null;finalEelement=x.item;finalNodenext=x.next;//得到后繼節(jié)點(diǎn)finalNodeprev=x.prev;//得到前驅(qū)節(jié)點(diǎn)//刪除前驅(qū)指針if(prev==null) {? ? ? ? ? ? first=next;如果刪除的節(jié)點(diǎn)是頭節(jié)點(diǎn),令頭節(jié)點(diǎn)指向該節(jié)點(diǎn)的后繼節(jié)點(diǎn)? ? ? ? }else{? ? ? ? ? ? prev.next=next;//將前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向后繼節(jié)點(diǎn)x.prev=null;? ? ? ? }//刪除后繼指針if(next==null) {? ? ? ? ? ? last=prev;//如果刪除的節(jié)點(diǎn)是尾節(jié)點(diǎn),令尾節(jié)點(diǎn)指向該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)}else{? ? ? ? ? ? next.prev=prev;? ? ? ? ? ? x.next=null;? ? ? ? }? ? ? ? x.item=null;? ? ? ? size--;? ? ? ? modCount++;returnelement;? ? }
remove(int index)：刪除指定位置的元素
publicEremove(intindex) {//檢查index范圍checkElementIndex(index);//將節(jié)點(diǎn)刪除returnunlink(node(index));? ? }
packagelist;importjava.util.Iterator;importjava.util.LinkedList;publicclassLinkedListDemo{publicstaticvoidmain(String[]srgs) {//創(chuàng)建存放int類型的linkedListLinkedListlinkedList=newLinkedList<>();/************************** linkedList的基本操作 ************************/linkedList.addFirst(0);//添加元素到列表開頭linkedList.add(1);//在列表結(jié)尾添加元素linkedList.add(2,2);//在指定位置添加元素linkedList.addLast(3);//添加元素到列表結(jié)尾System.out.println("LinkedList（直接輸出的）:"+linkedList);System.out.println("getFirst()獲得第一個(gè)元素:"+linkedList.getFirst());//返回此列表的第一個(gè)元素System.out.println("getLast()獲得第最后一個(gè)元素:"+linkedList.getLast());//返回此列表的最后一個(gè)元素System.out.println("removeFirst()刪除第一個(gè)元素并返回:"+linkedList.removeFirst());//移除并返回此列表的第一個(gè)元素System.out.println("removeLast()刪除最后一個(gè)元素并返回:"+linkedList.removeLast());//移除并返回此列表的最后一個(gè)元素System.out.println("After remove:"+linkedList);System.out.println("contains()方法判斷列表是否包含1這個(gè)元素:"+linkedList.contains(1));//判斷此列表包含指定元素，如果是漂辐，則返回trueSystem.out.println("該linkedList的大小 :"+linkedList.size());//返回此列表的元素個(gè)數(shù)/************************** 位置訪問操作 ************************/System.out.println("-----------------------------------------");? ? ? ? linkedList.set(1,3);//將此列表中指定位置的元素替換為指定的元素System.out.println("After set(1, 3):"+linkedList);System.out.println("get(1)獲得指定位置（這里為1）的元素:"+linkedList.get(1));//返回此列表中指定位置處的元素/************************** Search操作 ************************/System.out.println("-----------------------------------------");? ? ? ? linkedList.add(3);System.out.println("indexOf(3):"+linkedList.indexOf(3));//返回此列表中首次出現(xiàn)的指定元素的索引System.out.println("lastIndexOf(3):"+linkedList.lastIndexOf(3));//返回此列表中最后出現(xiàn)的指定元素的索引/************************** Queue操作 ************************/System.out.println("-----------------------------------------");System.out.println("peek():"+linkedList.peek());//獲取但不移除此列表的頭System.out.println("element():"+linkedList.element());//獲取但不移除此列表的頭linkedList.poll();//獲取并移除此列表的頭System.out.println("After poll():"+linkedList);? ? ? ? linkedList.remove();System.out.println("After remove():"+linkedList);//獲取并移除此列表的頭linkedList.offer(4);System.out.println("After offer(4):"+linkedList);//將指定元素添加到此列表的末尾/************************** Deque操作 ************************/System.out.println("-----------------------------------------");? ? ? ? linkedList.offerFirst(2);//在此列表的開頭插入指定的元素System.out.println("After offerFirst(2):"+linkedList);? ? ? ? linkedList.offerLast(5);//在此列表末尾插入指定的元素System.out.println("After offerLast(5):"+linkedList);System.out.println("peekFirst():"+linkedList.peekFirst());//獲取但不移除此列表的第一個(gè)元素System.out.println("peekLast():"+linkedList.peekLast());//獲取但不移除此列表的第一個(gè)元素linkedList.pollFirst();//獲取并移除此列表的第一個(gè)元素System.out.println("After pollFirst():"+linkedList);? ? ? ? linkedList.pollLast();//獲取并移除此列表的最后一個(gè)元素System.out.println("After pollLast():"+linkedList);? ? ? ? linkedList.push(2);//將元素推入此列表所表示的堆棧（插入到列表的頭）System.out.println("After push(2):"+linkedList);? ? ? ? linkedList.pop();//從此列表所表示的堆棧處彈出一個(gè)元素（獲取并移除列表第一個(gè)元素）System.out.println("After pop():"+linkedList);? ? ? ? linkedList.add(3);? ? ? ? linkedList.removeFirstOccurrence(3);//從此列表中移除第一次出現(xiàn)的指定元素（從頭部到尾部遍歷列表）System.out.println("After removeFirstOccurrence(3):"+linkedList);? ? ? ? linkedList.removeLastOccurrence(3);//從此列表中移除最后一次出現(xiàn)的指定元素（從頭部到尾部遍歷列表）System.out.println("After removeFirstOccurrence(3):"+linkedList);/************************** 遍歷操作 ************************/System.out.println("-----------------------------------------");? ? ? ? linkedList.clear();for(inti=0; i<100000; i++) {? ? ? ? ? ? linkedList.add(i);? ? ? ? }//迭代器遍歷longstart=System.currentTimeMillis();Iteratoriterator=linkedList.iterator();while(iterator.hasNext()) {? ? ? ? ? ? iterator.next();? ? ? ? }longend=System.currentTimeMillis();System.out.println("Iterator："+(end-start)+"ms");//順序遍歷(隨機(jī)遍歷)start=System.currentTimeMillis();for(inti=0; i<linkedList.size(); i++) {? ? ? ? ? ? linkedList.get(i);? ? ? ? }? ? ? ? end=System.currentTimeMillis();System.out.println("for："+(end-start)+"ms");//另一種for循環(huán)遍歷start=System.currentTimeMillis();for(Integeri:linkedList)? ? ? ? ? ? ;? ? ? ? end=System.currentTimeMillis();System.out.println("for2："+(end-start)+"ms");//通過pollFirst()或pollLast()來(lái)遍歷LinkedListLinkedListtemp1=newLinkedList<>();? ? ? ? temp1.addAll(linkedList);? ? ? ? start=System.currentTimeMillis();while(temp1.size()!=0) {? ? ? ? ? ? temp1.pollFirst();? ? ? ? }? ? ? ? end=System.currentTimeMillis();System.out.println("pollFirst()或pollLast()："+(end-start)+"ms");//通過removeFirst()或removeLast()來(lái)遍歷LinkedListLinkedListtemp2=newLinkedList<>();? ? ? ? temp2.addAll(linkedList);? ? ? ? start=System.currentTimeMillis();while(temp2.size()!=0) {? ? ? ? ? ? temp2.removeFirst();? ? ? ? }? ? ? ? end=System.currentTimeMillis();System.out.println("removeFirst()或removeLast()："+(end-start)+"ms");? ? }}
