您好,登錄后才能下訂單哦!
如何以武俠形式理解Java LinkedList源碼,很多新手對(duì)此不是很清楚,為了幫助大家解決這個(gè)難題,下面小編將為大家詳細(xì)講解,有這方面需求的人可以來(lái)學(xué)習(xí)下,希望你能有所收獲。
大家好,我是 LinkedList,和 ArrayList 是同門(mén)師兄弟,但我倆練的內(nèi)功卻完全不同。師兄練的是動(dòng)態(tài)數(shù)組,我練的是鏈表。
問(wèn)大家一個(gè)問(wèn)題,知道我為什么要練鏈表這門(mén)內(nèi)功嗎?
舉個(gè)例子來(lái)講吧,假如你們手頭要管理一推票據(jù),可能有一張,也可能有一億張。
該怎么辦呢?
申請(qǐng)一個(gè) 10G 的大數(shù)組等著?那萬(wàn)一票據(jù)只有 100 張呢?
申請(qǐng)一個(gè)默認(rèn)大小的數(shù)組,隨著數(shù)據(jù)量的增大擴(kuò)容?要知道擴(kuò)容是需要重新復(fù)制數(shù)組的,很耗時(shí)間。
關(guān)鍵是,數(shù)組還有一個(gè)弊端就是,假如現(xiàn)在有 500 萬(wàn)張票據(jù),現(xiàn)在要從中間刪除一個(gè)票據(jù),就需要把 250 萬(wàn)張票據(jù)往前移動(dòng)一格。
遇到這種情況的時(shí)候,我?guī)熜謳缀跚榫w崩潰,難受的要命。師父不忍心看到師兄這樣痛苦,于是打我進(jìn)入師門(mén)那一天,就強(qiáng)迫我練鏈表這門(mén)內(nèi)功,一開(kāi)始我很不理解,害怕師父偏心,不把師門(mén)最厲害的內(nèi)功教我。
直到有一天,我親眼目睹師兄差點(diǎn)因?yàn)橐苿?dòng)數(shù)據(jù)而走火入魔,我才明白師父的良苦用心。從此以后,我苦練“鏈表”這門(mén)內(nèi)功,取得了顯著的進(jìn)步,師父和師兄都夸我有天賦。
鏈表這門(mén)內(nèi)功大致分為三個(gè)層次:
第一層叫做“單向鏈表”,我只有一個(gè)后指針,指向下一個(gè)數(shù)據(jù);
第二層叫做“雙向鏈表”,我有兩個(gè)指針,后指針指向下一個(gè)數(shù)據(jù),前指針指向上一個(gè)數(shù)據(jù)。
第三層叫做“二叉樹(shù)”,把后指針去掉,換成左右指針。
但我現(xiàn)在的功力還達(dá)不到第三層,不過(guò)師父說(shuō)我有這個(gè)潛力,練成神功是早晚的事。
先贊后看:《Java 程序員進(jìn)階之路》專欄在 GitHub 上已經(jīng)開(kāi)源了,有 GitHub 賬號(hào)的小伙伴,來(lái)安排一波 star 呀!看能不能沖一波 trending 榜單,求求各位了。
GitHub 地址:https://github.com/itwanger/toBeBetterJavaer
好了,經(jīng)過(guò)我這么樣的一個(gè)剖白后,大家對(duì)我應(yīng)該已經(jīng)不陌生了。那么接下來(lái),我給大家展示一下我的內(nèi)功心法。
我的內(nèi)功心法主要是一個(gè)私有的靜態(tài)內(nèi)部類(lèi),叫 Node,也就是節(jié)點(diǎn)。
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
它由三部分組成:
節(jié)點(diǎn)上的元素
下一個(gè)節(jié)點(diǎn)
上一個(gè)節(jié)點(diǎn)
我畫(huà)幅圖給你們展示下吧。
對(duì)于第一個(gè)節(jié)點(diǎn)來(lái)說(shuō),prev 為 null;
對(duì)于最后一個(gè)節(jié)點(diǎn)來(lái)說(shuō),next 為 null;
其余的節(jié)點(diǎn)呢,prev 指向前一個(gè),next 指向后一個(gè)。
我的內(nèi)功心法就這么簡(jiǎn)單,其實(shí)我早已經(jīng)牢記在心了。但師父叮囑我,每天早上醒來(lái)的時(shí)候,每天晚上睡覺(jué)的時(shí)候,一定要默默地背誦一遍。雖然我有些厭煩,但我對(duì)師父的教誨從來(lái)都是言聽(tīng)計(jì)從。
和師兄 ArrayList 一樣,我的招式也無(wú)外乎“增刪改查”這 4 種。在此之前,我們都必須得初始化。
LinkedList<String> list = new LinkedList();
師兄在初始化的時(shí)候,默認(rèn)大小為 10,也可以指定大小,依據(jù)要存儲(chǔ)的元素?cái)?shù)量來(lái)。我就不需要。
可以調(diào)用 add 方法添加元素:
list.add("沉默王二"); list.add("沉默王三"); list.add("沉默王四");
add 方法內(nèi)部其實(shí)調(diào)用的是 linkLast 方法:
public boolean add(E e) { linkLast(e); return true; }
linkLast,顧名思義,就是在鏈表的尾部鏈接:
void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
添加第一個(gè)元素的時(shí)候,first 和 last 都為 null。
然后新建一個(gè)節(jié)點(diǎn) newNode,它的 prev 和 next 也為 null。
然后把 last 和 first 都賦值為 newNode。
此時(shí)還不能稱之為鏈表,因?yàn)榍昂蠊?jié)點(diǎn)都是斷裂的。
添加第二個(gè)元素的時(shí)候,first 和 last 都指向的是第一個(gè)節(jié)點(diǎn)。
然后新建一個(gè)節(jié)點(diǎn) newNode,它的 prev 指向的是第一個(gè)節(jié)點(diǎn),next 為 null。
然后把第一個(gè)節(jié)點(diǎn)的 next 賦值為 newNode。
此時(shí)的鏈表還不完整。
添加第三個(gè)元素的時(shí)候,first 指向的是第一個(gè)節(jié)點(diǎn),last 指向的是最后一個(gè)節(jié)點(diǎn)。
然后新建一個(gè)節(jié)點(diǎn) newNode,它的 prev 指向的是第二個(gè)節(jié)點(diǎn),next 為 null。
然后把第二個(gè)節(jié)點(diǎn)的 next 賦值為 newNode。
此時(shí)的鏈表已經(jīng)完整了。
我這個(gè)增的招式,還可以演化成另外兩個(gè):
addFirst()
方法將元素添加到第一位;
addLast()
方法將元素添加到末尾。
addFirst 內(nèi)部其實(shí)調(diào)用的是 linkFirst:
public void addFirst(E e) { linkFirst(e); }
linkFirst 負(fù)責(zé)把新的節(jié)點(diǎn)設(shè)為 first,并將新的 first 的 next 更新為之前的 first。
private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }
addLast 的內(nèi)核其實(shí)和 addFirst 差不多,就交給大家自行理解了。
我這個(gè)刪的招式還挺多的:
remove()
:刪除第一個(gè)節(jié)點(diǎn)
remove(int)
:刪除指定位置的節(jié)點(diǎn)
remove(Object)
:刪除指定元素的節(jié)點(diǎn)
removeFirst()
:刪除第一個(gè)節(jié)點(diǎn)
removeLast()
:刪除最后一個(gè)節(jié)點(diǎn)
remove 內(nèi)部調(diào)用的是 removeFirst,所以這兩個(gè)招式的功效一樣。
remove(int)
內(nèi)部其實(shí)調(diào)用的是 unlink 方法。
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }
unlink 方法其實(shí)很好理解,就是更新當(dāng)前節(jié)點(diǎn)的 next 和 prev,然后把當(dāng)前節(jié)點(diǎn)上的元素設(shè)為 null。
E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }
remove(Object) 內(nèi)部也調(diào)用了 unlink 方法,只不過(guò)在此之前要先找到元素所在的節(jié)點(diǎn):
public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
這內(nèi)部就分為兩種,一種是元素為 null 的時(shí)候,必須使用 == 來(lái)判斷;一種是元素為非 null 的時(shí)候,要使用 equals 來(lái)判斷。equals 是不能用來(lái)判 null 的,會(huì)拋出 NPE 錯(cuò)誤。
removeFirst 內(nèi)部調(diào)用的是 unlinkFirst 方法:
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }
unlinkFirst 負(fù)責(zé)的就是把第一個(gè)節(jié)點(diǎn)毀尸滅跡,并且捎帶把后一個(gè)節(jié)點(diǎn)的 prev 設(shè)為 null。
private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; }
可以調(diào)用 set()
方法來(lái)更新元素:
list.set(0, "沉默王五");
來(lái)看一下 set()
方法:
public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; }
首先對(duì)指定的下標(biāo)進(jìn)行檢查,看是否越界;然后根據(jù)下標(biāo)查找原有的節(jié)點(diǎn):
Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
size >> 1
:也就是右移一位,相當(dāng)于除以 2。對(duì)于計(jì)算機(jī)來(lái)說(shuō),移位比除法運(yùn)算效率更高,因?yàn)閿?shù)據(jù)在計(jì)算機(jī)內(nèi)部都是二進(jìn)制存儲(chǔ)的。
換句話說(shuō),node 方法會(huì)對(duì)下標(biāo)進(jìn)行一個(gè)初步判斷,如果靠近前半截,就從下標(biāo) 0 開(kāi)始遍歷;如果靠近后半截,就從末尾開(kāi)始遍歷。
找到指定下標(biāo)的節(jié)點(diǎn)就簡(jiǎn)單了,直接把原有節(jié)點(diǎn)的元素替換成新的節(jié)點(diǎn)就 OK 了,prev 和 next 都不用改動(dòng)。
我這個(gè)查的招式可以分為兩種:
indexOf(Object):查找某個(gè)元素所在的位置
get(int):查找某個(gè)位置上的元素
indexOf 的內(nèi)部分為兩種,一種是元素為 null 的時(shí)候,必須使用 == 來(lái)判斷;一種是元素為非 null 的時(shí)候,要使用 equals 來(lái)判斷。因?yàn)?equals 是不能用來(lái)判 null 的,會(huì)拋出 NPE 錯(cuò)誤。
public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }
get 方法的內(nèi)核其實(shí)還是 node 方法,這個(gè)之前已經(jīng)說(shuō)明過(guò)了,這里略過(guò)。
public E get(int index) { checkElementIndex(index); return node(index).item; }
其實(shí),查這個(gè)招式還可以演化為其他的一些,比如說(shuō):
getFirst()
方法用于獲取第一個(gè)元素;
getLast()
方法用于獲取最后一個(gè)元素;
poll()
和 pollFirst()
方法用于刪除并返回第一個(gè)元素(兩個(gè)方法盡管名字不同,但方法體是完全相同的);
pollLast()
方法用于刪除并返回最后一個(gè)元素;
peekFirst()
方法用于返回但不刪除第一個(gè)元素。
說(shuō)句實(shí)在話,我不是很喜歡和師兄 ArrayList 拿來(lái)比較,因?yàn)槲覀兏髯孕逕挼膬?nèi)功不同,沒(méi)有孰高孰低。
雖然師兄經(jīng)常喊我一聲師弟,但我們之間其實(shí)挺和諧的。但我知道,在外人眼里,同門(mén)師兄弟,總要一較高下的。
比如說(shuō),我們倆在增刪改查時(shí)候的時(shí)間復(fù)雜度。
也許這就是命運(yùn)吧,從我進(jìn)入師門(mén)的那天起,這種爭(zhēng)論就一直沒(méi)有停息過(guò)。
無(wú)論外人怎么看待我們,在我眼里,師兄永遠(yuǎn)都是一哥,我敬重他,他也愿意保護(hù)我。
好了,LinkedList 這篇就到這了。
看完上述內(nèi)容是否對(duì)您有幫助呢?如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章,請(qǐng)關(guān)注億速云行業(yè)資訊頻道,感謝您對(duì)億速云的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。