java中LinkedList怎么用

這篇文章主要為大家展示了“java中LinkedList怎么用”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“java中LinkedList怎么用”這篇文章吧。

與ArrayList一樣，我們同樣先從LinkedList的構(gòu)造器分析，LinkedList只有兩個(gè)構(gòu)造器，下面我們開(kāi)始上源碼分析。

public LinkedList()

源碼如下：

從源碼可以看出，LinkedList的默認(rèn)構(gòu)造器相當(dāng)簡(jiǎn)單，什么都沒(méi)有做。

public LinkedList(Collection<? extends E> c)

這個(gè)構(gòu)造器的源碼如下：

可以看出這個(gè)構(gòu)造器調(diào)用了一下默認(rèn)構(gòu)造器，然后調(diào)用了addAll方法，也是相當(dāng)簡(jiǎn)單的實(shí)現(xiàn)。

下面開(kāi)始分析LinkedList的實(shí)現(xiàn)，而LinkedList作為經(jīng)典的鏈表實(shí)現(xiàn)，我們先簡(jiǎn)單介紹一下鏈表。

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱(chēng)為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。 相比于線性表順序結(jié)構(gòu)（ArrayList屬于線性表順序結(jié)構(gòu)），操作復(fù)雜。由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間，而線性表順序結(jié)構(gòu)相應(yīng)的時(shí)間復(fù)雜度則是O(1)。

使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開(kāi)銷(xiāo)比較大。鏈表最明顯的好處就是，常規(guī)數(shù)組排列關(guān)聯(lián)項(xiàng)目的方式可能不同于這些數(shù)據(jù)項(xiàng)目在記憶體或磁盤(pán)上順序，數(shù)據(jù)的存取往往要在不同的排列順序中轉(zhuǎn)換。鏈表允許插入和移除表上任意位置上的節(jié)點(diǎn)，但是不允許隨機(jī)存取。鏈表有很多種不同的類(lèi)型：?jiǎn)蜗蜴湵恚p向鏈表以及循環(huán)鏈表。

關(guān)于鏈表的介紹完畢（偷了個(gè)懶，百度百科copy的），下面正式開(kāi)始介紹LinkedList。

private static class Node<E> 

首先是介紹一個(gè)Node<E>類(lèi)，Node作為L(zhǎng)inkedList里邊存儲(chǔ)的基本元素（節(jié)點(diǎn)），本身結(jié)構(gòu)很簡(jiǎn)單，Node的定義如下：

其中有三個(gè)變量，一個(gè)是item，存儲(chǔ)實(shí)際節(jié)點(diǎn)數(shù)據(jù)，一個(gè)是next，存儲(chǔ)當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，一個(gè)prev，存儲(chǔ)當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，由該Node很容易可以看出來(lái)，LinkedList是一個(gè)鏈狀的表（這不廢話嘛~）。Node只提供一種構(gòu)造器，接收參數(shù)分別為該Node的前一個(gè)Node，該Node實(shí)際存放的數(shù)據(jù)，該Node的下一個(gè)Node。

public boolean add(E e)

這是List基本的方法之一，LinkedList該方法的源碼如下：

可以看到該方法調(diào)用了一下linkLast方法，然后固定返回了一個(gè)true，非常簡(jiǎn)單，linkLast方法稍后會(huì)介紹。

public boolean remove(Object o)

該方法也是List基本方法之一，從鏈表中刪除。源碼如下：

可以看到跟ArrayList一樣，首先判斷o是不是null，然后遍歷，查出來(lái)指定節(jié)點(diǎn)后調(diào)用unlink方法刪除，同樣很簡(jiǎn)單，unlink方法會(huì)在稍后介紹。

void linkLast(E e)

該方法在調(diào)用add方法時(shí)被調(diào)用了，下面開(kāi)始介紹該方法。源碼如下：

首先聲明一個(gè)Node l等于last，該last定義在LinkedList中，表示當(dāng)前鏈表的最后一個(gè)元素，然后new出來(lái)一個(gè)新的Node，其中該Node的前一個(gè)Node指定為原鏈表的最后一個(gè)，同時(shí)該Node的下一個(gè)Node為null（因?yàn)樵揘ode是添加到了鏈表的末尾，后邊已經(jīng)沒(méi)有元素了）。然后將鏈表自己維護(hù)的最后一個(gè)節(jié)點(diǎn)last更新為新加入的節(jié)點(diǎn)，判斷原來(lái)的最后一個(gè)節(jié)點(diǎn)是否為null：

1、如果為null說(shuō)明添加該節(jié)點(diǎn)時(shí)原鏈表為空鏈表（只有空鏈表才會(huì)沒(méi)有first和last），上邊已經(jīng)將該鏈表的最后一個(gè)元素更新為新節(jié)點(diǎn)，下一行將該鏈表的第一個(gè)元素也更新為這個(gè)新節(jié)點(diǎn)，

2、如果不為null說(shuō)明原鏈表不為空，只需將原鏈表的最后一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn)即可。

最后更新size和modCount（該值很多地方都有用，不過(guò)可以暫時(shí)不用關(guān)注）。

E unlink(Node<E> x)

該方法在remove（Object o）的時(shí)候用到了，下面說(shuō)說(shuō)這個(gè)方法的實(shí)現(xiàn)，源碼如下：

其中第一行獲取element，同時(shí)還驗(yàn)證了x為非空（如果為空會(huì)拋出空指針異常NullPointException），然后取出要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的指針prev和后一個(gè)節(jié)點(diǎn)的指針next，然后判斷前一個(gè)節(jié)點(diǎn)是否為null：

1、如果為null說(shuō)明要?jiǎng)h除的節(jié)點(diǎn)是鏈表的第一個(gè)節(jié)點(diǎn)，刪除后需要將第二個(gè)節(jié)點(diǎn)也就是該節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)next設(shè)置為首節(jié)點(diǎn)first；

2、如果不為null那么將該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)prev的下一個(gè)節(jié)點(diǎn)更新為該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)next，同時(shí)將該節(jié)點(diǎn)對(duì)prev的引用刪除（設(shè)置為null）。

判斷完prev后對(duì)next也需要判斷，邏輯與prev差不多，就不再多說(shuō)了。

以上是“java中LinkedList怎么用”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！