javalinkedlist工作原理及實現(xiàn)-java開發(fā)java經(jīng)驗技巧

《javalinkedlist工作原理及實現(xiàn)-java開發(fā)java經(jīng)驗技巧》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、JavaLinkcdListIE作原理及實現(xiàn)-編程開發(fā)技術(shù)JavaLinkedList工作原理及實現(xiàn)原文出處：Yikun1.概述以雙向鏈表實現(xiàn)。鏈表無容量限制，但XX向鏈表本身使用了更多空間，也需要額外的鏈表指針操作。按下標訪問元素一get(i)/set(i,e)要悲劇的遍歷鏈表將指針移動到位(如果i>數(shù)組大小的一半，會從末尾移起)。插入、刪除元素時修改前后節(jié)點的指針即可，但還是要遍歷部分鏈表的指針才能移動到下標所指的位置，只冇在鏈表兩頭的操作—add(),addFirst(),removeLast()iterator()remove()能省掉指針的

2、移動。LinkedList是一個簡單的數(shù)據(jù)結(jié)構(gòu)，與ArrayList不同的是，他是基于鏈表實現(xiàn)的。Doubly-linkedlistimplementationoftheListandDequeinterfaces.Implementsalloptionallistoperations,andpermitsallelements(includingnull).LinkedList1ist二newLinkedList();list,addC語文：1〃);list,add(z，數(shù)學(xué):2〃);list,add(〃英語:3〃)

3、;firstlastlistLinkedList(▲firstLinkedListSNodet>▲item?語文V(id=35)t>▲nextLinkedListSNodc▲prevnull▲lastLinkedListSNodet>■item?英語:3°(id=41)▲nextnull>▲prevLinkedListSNodeOmodCount3▲size3[語文：1,數(shù)學(xué)；2,英語：3]2.set和get函數(shù)publicEset(intindex,Eelement){checkElementIndex(index);Nodcx二nod

4、e(index);EoldVal=x.item;x.item=element;returnoldVal;}publicEget(intindex){checkElementlndex(index);returnnode(index).item;}這兩個函數(shù)都調(diào)用了node函數(shù)，該函數(shù)會以0(n/2)的性能去獲取一個節(jié)點，貝體實現(xiàn)如下所示：Nodenode(intindex){//assertisElementTndex(index);if(index<(size>>1))Nodex=first;for(inti=0;i

5、)x二x.next;returnx;}else{Nodex=last;for(inti=size-1;i>index;i--)x二x.prev;returnx;就是判斷index是在前半?yún)^(qū)間還是后半?yún)^(qū)間，如果在前半?yún)^(qū)間就從head搜索，而在后半?yún)^(qū)間就從怡il搜索。而不是一宜從頭到尾的搜索。如此設(shè)計，將節(jié)點訪問的復(fù)雜度由0(n)變?yōu)?(n/2)。參考資料LinkedList(JavaPlatformSE8)