如何實(shí)現(xiàn)Java中一個(gè)簡(jiǎn)單的LinkedList-創(chuàng)新互聯(lián)

創(chuàng)新互聯(lián)www.cdcxhl.cn八線動(dòng)態(tài)BGP香港云服務(wù)器提供商，新人活動(dòng)買多久送多久，劃算不套路！

成都創(chuàng)新互聯(lián)成立與2013年，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都做網(wǎng)站、網(wǎng)站制作網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元萍鄉(xiāng)做網(wǎng)站,已為上家服務(wù),為萍鄉(xiāng)各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18980820575

LinkedList與ArrayList都是List接口的具體實(shí)現(xiàn)類。LinkedList與ArrayList在功能上也是大體一致，但是因?yàn)閮烧呔唧w的實(shí)現(xiàn)方式不一致，所以在進(jìn)行一些相同操作的時(shí)候，其效率也是有差別的。

對(duì)于抽象的數(shù)據(jù)結(jié)構(gòu)——線性表而言，線性表分為兩種，一種是順序存儲(chǔ)結(jié)構(gòu)的順序表，另一種是通過(guò)指針來(lái)描述其邏輯位置的鏈表。

針對(duì)于具體的Java實(shí)現(xiàn)：

1. 順序存儲(chǔ)的順序表是用數(shù)組來(lái)實(shí)現(xiàn)的，以數(shù)組為基礎(chǔ)進(jìn)行封裝各種操作而形成的List為ArrayList
2. 鏈表是用指針來(lái)描述其邏輯位置，在Java中以雙向鏈表為基礎(chǔ)進(jìn)行封裝各種操作而形成的List為L(zhǎng)inkedList

針對(duì)插入與刪除操作，ArrayList每插入一個(gè)元素，首先需要判斷數(shù)組的空間夠不夠，不夠要進(jìn)行擴(kuò)容，在有足夠的空間的基礎(chǔ)上，在指定的index位置上插入元素，但是該index及以后的元素都要后移。雖然刪除操作不需要判斷空間夠不夠，但同樣需要該index及以后的元素向前移動(dòng)，這些移動(dòng)的操作會(huì)增加時(shí)間的復(fù)雜度。但是對(duì)于LinkedList就不一樣，因?yàn)槭褂弥羔榿?lái)指示其邏輯的位置，所以插入與刪除的操作的時(shí)間復(fù)雜度都是 ** O(1) **

雖然對(duì)于ArrayList而言，插入與刪除的時(shí)間復(fù)雜度很高，但是對(duì)于查找指定位置的元素這種操作而言，就非常的快，因?yàn)榭梢酝ㄟ^(guò)數(shù)組直接得到該下標(biāo)對(duì)應(yīng)的元素。反而，LinkedList而言，無(wú)法直接返回指定位置的元素，需要一個(gè)個(gè)查詢，其時(shí)間的復(fù)雜度就是 ** O(n) **

與如何實(shí)現(xiàn)Java的ArrayList經(jīng)典實(shí)體類一樣，實(shí)現(xiàn)的目的主要在于練手以及掌握官方實(shí)現(xiàn)的原理和一些技巧，因此很多需要與其他類配合的方法和功能，就先不在這里實(shí)現(xiàn)如iterator等

所以，實(shí)現(xiàn)的LinkedList的方法如下：

add方法

get方法

indexOf方法

remove方法

與實(shí)現(xiàn)ArrayList的名字一樣，為SimpleLinkedList。源碼地址，歡迎star,fork

構(gòu)建一個(gè)雙向鏈表

構(gòu)建的代碼如下：

 private static class Node<E>{
 E item;
 Node<E> next;
 Node<E> prev;
 public Node(E item, Node<E> next, Node<E> prev) {
 this.item = item;
 this.next = next;
 this.prev = prev;
 }
 } 

文章題目：如何實(shí)現(xiàn)Java中一個(gè)簡(jiǎn)單的LinkedList-創(chuàng)新互聯(lián)
網(wǎng)站路徑：http://www.jbt999.com/article12/cdegdc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營(yíng)銷推廣、微信公眾號(hào)、建站公司、網(wǎng)站策劃、域名注冊(cè)、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：[email protected]。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)