Adslv ·1. 前言
我們今天要通過(guò)了解鏈表的原理來(lái)掌握鏈表這個(gè)重要的數(shù)據(jù)結(jié)構(gòu)，隨后用我們了解到的鏈表的知識(shí)來(lái)重新認(rèn)識(shí)一下我們每天都要接觸的最常見(jiàn)的鏈表 java.util.LinkedList 類(lèi)。
2. 數(shù)組的缺陷
數(shù)組作為我們最常見(jiàn)的通用數(shù)據(jù)結(jié)構(gòu)，幾乎可以實(shí)現(xiàn)我們常見(jiàn)的所有數(shù)據(jù)結(jié)構(gòu)。然而，數(shù)組的特點(diǎn)決定了它的適用場(chǎng)景必然是有限的，比如占用空間大小固定，空間過(guò)小可能不能滿足數(shù)據(jù)量的要求，空間過(guò)大又會(huì)造成內(nèi)存資源的浪費(fèi)，再比如數(shù)組的插入效率很低等等。
那有沒(méi)有一種插入效率很高，而且不需要頻繁擴(kuò)容的基本數(shù)據(jù)結(jié)構(gòu)呢？答案是肯定的，它就是 —— 鏈表。
3. 什么是鏈表
鏈表是一組鏈?zhǔn)浇Y(jié)構(gòu)的數(shù)據(jù)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都包含保存數(shù)據(jù)的部分，以及用來(lái)指向上一個(gè)或下一個(gè)節(jié)點(diǎn)位置的鏈接信息。鏈表是一種線性表，它可以靈活的根據(jù)數(shù)據(jù)大小來(lái)使用內(nèi)存空間，但是由于它在內(nèi)存中不是連續(xù)存儲(chǔ)的，所以根據(jù)角標(biāo)查詢(xún)的效率很低，同時(shí)由于每一個(gè)節(jié)點(diǎn)上除了數(shù)據(jù)信息還額外存儲(chǔ)了與其他節(jié)點(diǎn)的鏈接信息，所以對(duì)空間的占用也更大一些。
4. 單向鏈表
我們首先通過(guò)最簡(jiǎn)單的鏈表 —— 單向鏈表來(lái)熟悉一下鏈表的結(jié)構(gòu)和存儲(chǔ)原理。
單鏈表的每一個(gè)節(jié)點(diǎn)我們稱(chēng)之為 Node，都包含一個(gè)存儲(chǔ)數(shù)據(jù)的部分我們稱(chēng)為之 data，還有一部分用來(lái)存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址我們稱(chēng)之為 links。鏈表的第一個(gè)節(jié)點(diǎn)我們稱(chēng)之為 head 頭節(jié)點(diǎn)。
5. 雙端鏈表
單向鏈表由于只記錄了自己的下一個(gè)節(jié)點(diǎn)，所以它的訪問(wèn)方向是單向的。如果我想在最后一個(gè)節(jié)點(diǎn)后添加元素，就需要從第一個(gè)節(jié)點(diǎn)開(kāi)始挨個(gè)遍歷，很不方便，于是我們給鏈表的最后一個(gè)節(jié)點(diǎn)標(biāo)示為 tail 尾節(jié)點(diǎn)，便于我們?cè)谧詈笠粋€(gè)節(jié)點(diǎn)插入元素的時(shí)候可以直接引用尾節(jié)點(diǎn)，這就叫做雙端鏈表。
6. 雙向鏈表
前面講的單向鏈表和雙端鏈表其實(shí)主要是讓大家了解鏈表的存儲(chǔ)原理，實(shí)際我們使用最多的是雙向鏈表，雙向鏈表在單向鏈表的基礎(chǔ)上同時(shí)記錄了上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)兩個(gè)指針信息，遍歷更加方便。
Java 中對(duì)于雙向鏈表有現(xiàn)成的實(shí)現(xiàn)，就是我們非常熟悉的 java.util.LinkedList。在源碼中我們可以看到 LinkedList 把節(jié)點(diǎn)定義成三個(gè)部分：元素、上一節(jié)點(diǎn)和下一節(jié)點(diǎn)。
其實(shí)鏈表的最大的魅力就是可以?xún)?yōu)雅高效地插入數(shù)據(jù)，它只需要在要插入的位置修改前后節(jié)點(diǎn)的指針就可以完成，完全不需要移動(dòng)其他的數(shù)據(jù)。LinkedList 源碼中是這樣實(shí)現(xiàn)的：
結(jié)合上圖，我們用動(dòng)圖來(lái)模擬實(shí)現(xiàn)一下 LinkedList 的 add 方法：
動(dòng)圖中的節(jié)點(diǎn)位置我故意擺放得很零散，就是為了突出這些節(jié)點(diǎn)在內(nèi)存中的位置并不是連續(xù)的，這也體現(xiàn)出了鏈表可以對(duì)內(nèi)存里這些零散角落高效利用的特點(diǎn)。
對(duì)于刪除操作，鏈表完全可以根據(jù)插入的逆操作來(lái)高效優(yōu)雅地完成。
7. 鏈表的優(yōu)缺點(diǎn)
鏈表的優(yōu)點(diǎn)是大小可變，插入和刪除的效率很高，缺點(diǎn)是只能通過(guò)順序指針訪問(wèn)，查詢(xún)的效率較低。無(wú)圖無(wú)真相，我們結(jié)合圖片看一下他們分別是如何獲取指定元素的。先來(lái)看下基于數(shù)組的 ArrayList：
再來(lái)看下基于鏈表的 LinkedList:
對(duì)比基于數(shù)組的 ArrayList 和基于鏈表的 LinkedList 的 get (index i) 方法的實(shí)現(xiàn)就會(huì)發(fā)現(xiàn)，鏈表需要遍歷才能返回想要的元素，所以效率才比較低下。知道了鏈表的這些特性，我們今后在使用這一數(shù)據(jù)結(jié)構(gòu)的時(shí)候就知道如何讓它在合適的時(shí)候發(fā)揮它的最大優(yōu)勢(shì)咯。
8. 小結(jié)
這一小節(jié)我們知道了鏈表是一種線性結(jié)構(gòu)的基本數(shù)據(jù)類(lèi)型，可以分為單向鏈表、雙端鏈表、雙向鏈表等，內(nèi)部實(shí)現(xiàn)的原理都是在每一個(gè)節(jié)點(diǎn)上除了記錄數(shù)據(jù)外，還記錄了上一個(gè)或下一個(gè)節(jié)點(diǎn)的位置信息。它的特點(diǎn)是插入和刪除的效率很高，查詢(xún)的效率較低。
2025 imooc.com All Rights Reserved |