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

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

成都創(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)目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元萍鄉(xiāng)做網(wǎng)站,已為上家服務(wù),為萍鄉(xiāng)各地企業(yè)和個人服務(wù),聯(lián)系電話:18980820575

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

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

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

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

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

雖然對于ArrayList而言，插入與刪除的時間復(fù)雜度很高，但是對于查找指定位置的元素這種操作而言，就非常的快，因?yàn)榭梢酝ㄟ^數(shù)組直接得到該下標(biāo)對應(yīng)的元素。反而，LinkedList而言，無法直接返回指定位置的元素，需要一個個查詢，其時間的復(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ò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中一個簡單的LinkedList-創(chuàng)新互聯(lián)
網(wǎng)站路徑：http://bm7419.com/article12/cdegdc.html

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

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

猜你還喜歡下面的內(nèi)容