刨根問(wèn)底之鏈表數(shù)據(jù)結(jié)構(gòu)
[導(dǎo)讀] 為啥取這么個(gè)題目,刨根問(wèn)底?本文也未必刨到根了,也未必探到了底!但是筆者想要傳達(dá)一個(gè)觀點(diǎn),一個(gè)態(tài)度!作為攻城獅而言,如果對(duì)某一個(gè)點(diǎn)感興趣應(yīng)盡量深入再深入,忌淺嘗輒止!刨根問(wèn)底有百利而無(wú)一害。另外撰寫刨根問(wèn)底學(xué)算法系列文章,也是因?yàn)楣P者非計(jì)算機(jī)專業(yè)計(jì)算機(jī)學(xué)的非常膚淺,讀書時(shí)老師講課感覺(jué)更多是學(xué)以致考,而非學(xué)以致用。故梳理學(xué)習(xí)以記之。
如果讀到本文的你剛好是在校學(xué)子,不妨擴(kuò)散給你的同學(xué)們,希望能在讀書的時(shí)候,不光學(xué)會(huì)會(huì)考,也盡量嘗試學(xué)著去用!
啥是鏈表?
鏈表是計(jì)算機(jī)科學(xué)中一種鏈?zhǔn)?/span>線性表,數(shù)據(jù)域為節(jié)點(diǎn)的一部分,每個(gè)節(jié)點(diǎn)都指向下一個(gè)節(jié)點(diǎn),從而在邏輯上形成一個(gè)鏈。
線性表 vs 非線性表
什么樣的表是線性表?什么樣的表又是非線性表呢?既然有線性表就必然有非線性表!
線性表:
-
邏輯存儲(chǔ)角度:這里線性是指邏輯上的線性,除了首位元素,其他元素從邏輯上是一對(duì)一邏輯上連起來(lái)的 -
訪問(wèn)遍歷角度:訪問(wèn)元素是朝著邏輯上一個(gè)方向即可遍歷訪問(wèn)所有元素
那么概括起來(lái)說(shuō)就是一種數(shù)據(jù)元素按順序或線性排列的數(shù)據(jù)結(jié)構(gòu),其中元素與它的上一個(gè)和下一個(gè)相鄰,稱為線性數(shù)據(jù)結(jié)構(gòu)。在線性數(shù)據(jù)結(jié)構(gòu)中,只涉及單層數(shù)據(jù)。因此,只能在一次運(yùn)行中遍歷所有元素。由于計(jì)算機(jī)內(nèi)存以線性方式排列,因此線性數(shù)據(jù)結(jié)構(gòu)易于實(shí)現(xiàn)。那么滿足上面這樣特性的,常見(jiàn)的數(shù)組、隊(duì)列、棧、鏈表即是線性表。
非線性表:
數(shù)據(jù)元素不是按邏輯順序或線性排列的數(shù)據(jù)結(jié)構(gòu)稱為非線性數(shù)據(jù)結(jié)構(gòu)。在非線性數(shù)據(jù)結(jié)構(gòu)中,不涉及單個(gè)級(jí)別。因此不能在朝一個(gè)邏輯方向遍歷所有元素。與線性數(shù)據(jù)結(jié)構(gòu)相比,非線性數(shù)據(jù)結(jié)構(gòu)不容易實(shí)現(xiàn)。與線性數(shù)據(jù)結(jié)構(gòu)相比,它能有效地利用計(jì)算機(jī)內(nèi)存,在邏輯上一對(duì)多或者多對(duì)多的關(guān)系,比如樹、圖。
線性數(shù)據(jù)結(jié)構(gòu) | 非線性數(shù)據(jù)結(jié)構(gòu) |
---|---|
各元素都與它的上一個(gè)和下一個(gè)元素邏輯相連 | 數(shù)據(jù)元素是分層邏輯相連 |
僅單層結(jié)構(gòu) | 多層結(jié)構(gòu) |
易于實(shí)現(xiàn) | 實(shí)現(xiàn)相對(duì)復(fù)雜 |
單循環(huán)遍歷所有元素 | 單循環(huán)無(wú)法遍歷所有元素 |
內(nèi)存利用率較低 | 內(nèi)存利用率較高 |
如數(shù)組、隊(duì)列、棧、鏈表 | 如樹、圖 |
應(yīng)用主要集中在應(yīng)用軟件開發(fā)方面 | 人工智能和圖像處理方面有廣泛的應(yīng)用。 |
如何鏈?
Linked list(鏈表),從語(yǔ)義上理解,首先這玩意兒是一個(gè)表(list),是怎樣的一個(gè)表呢?數(shù)據(jù)節(jié)點(diǎn)鏈接(Linked)起來(lái)的表!
怎么鏈起來(lái)的呢?
邏輯上鏈起來(lái)的,這里有兩種辦法:
-
動(dòng)態(tài)存儲(chǔ)方法:動(dòng)態(tài)申請(qǐng)節(jié)點(diǎn)內(nèi)存,然后利用節(jié)點(diǎn)中的指針指向下一個(gè)節(jié)點(diǎn),實(shí)現(xiàn)鏈。優(yōu)點(diǎn)是存儲(chǔ)節(jié)點(diǎn)數(shù)理論上無(wú)限制,不需要提前分配內(nèi)存,僅受限于物理可用內(nèi)存。但不易于調(diào)試。 -
靜態(tài)存儲(chǔ)方法:比如用數(shù)組實(shí)現(xiàn)。這種方法比較易于調(diào)試,缺點(diǎn)是不能動(dòng)態(tài)分配節(jié)點(diǎn),需要提前分配內(nèi)存,存儲(chǔ)節(jié)點(diǎn)有限。
對(duì)于動(dòng)態(tài)存儲(chǔ)方法而言,易于理解,一想到鏈表很多盆友都立馬想到,設(shè)計(jì)一個(gè)節(jié)點(diǎn),沒(méi)增加一個(gè)鏈節(jié)點(diǎn),動(dòng)態(tài)申請(qǐng)節(jié)點(diǎn)大小內(nèi)存,再把節(jié)點(diǎn)插入進(jìn)鏈表即可。對(duì)于靜態(tài)方法,可能常常覺(jué)得并沒(méi)啥用。事實(shí)上呢卻不然。比如前面我寫過(guò)一篇RT-Thread的小堆管理器的實(shí)現(xiàn),即是采用了靜態(tài)存儲(chǔ)方法實(shí)現(xiàn)了鏈表。
可參閱:
實(shí)用算法解讀之RT-Thread鏈表堆管理器
為啥要鏈表?
探究計(jì)算機(jī)先輩為啥要發(fā)明這樣一種數(shù)據(jù)結(jié)構(gòu)呢?不妨拿最為普通的數(shù)組與鏈表做些對(duì)比,數(shù)組在存儲(chǔ)信息的角度與鏈表從作用角度最為類型的一種線性數(shù)據(jù),但是數(shù)組具有以下限制:
-
數(shù)組的大小是固定的:因此必須提前知道元素?cái)?shù)量的上限。過(guò)小則應(yīng)用時(shí)可能不夠,過(guò)大則易浪費(fèi)。 -
數(shù)組中插入新元素非常昂貴,因?yàn)楸仨殲樾略貏?chuàng)建空間,并且必須移動(dòng)現(xiàn)有所有元素。CPU忙忙碌碌干了一堆無(wú)聊的搬運(yùn)工工作。
而動(dòng)態(tài)存儲(chǔ)實(shí)現(xiàn)的鏈表則很好解決了這些缺陷:
-
動(dòng)態(tài)申請(qǐng)、動(dòng)態(tài)刪除,高效利用內(nèi)存,不易浪費(fèi) -
非常易于插入刪除某一個(gè)元素
任何事物都具有兩面性,不可能全是優(yōu)點(diǎn)而無(wú)缺點(diǎn),鏈表也一樣:
-
不允許隨機(jī)訪問(wèn)。必須從第一個(gè)節(jié)點(diǎn)開始順序訪問(wèn)元素。因此無(wú)法使用其默認(rèn)實(shí)現(xiàn)對(duì)鏈接列表進(jìn)行有效的二進(jìn)制搜索。 -
鏈表的每個(gè)節(jié)點(diǎn)都需要指向下一節(jié)點(diǎn)的指針的額外存儲(chǔ)空間開銷。 -
不適合緩存。由于數(shù)組元素是連續(xù)的位置,因此存在引用位置,可以實(shí)現(xiàn)緩存。而動(dòng)態(tài)存儲(chǔ)形式鏈表則地址是不連續(xù)的。
對(duì)于應(yīng)用而言,必然是根據(jù)待解決的問(wèn)題的特點(diǎn)進(jìn)而選擇合適的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)方式,不是說(shuō)鏈表就高大上,從而鄙視最為普通的數(shù)組!
談?wù)劰?jié)點(diǎn)
實(shí)際應(yīng)用中的數(shù)據(jù)節(jié)點(diǎn),可能是一個(gè)基本類型數(shù)據(jù),也可能是一個(gè)結(jié)構(gòu)體,泛言之是一個(gè)廣義抽象數(shù)據(jù)類型,比如:
typedef struct _T_ELEMENT{
int cmd;
float value;
int status;
}T_ELEMENT;
struct Node {
T_ELEMENT data;
struct Node* next;
};
如果你剛好在學(xué)習(xí)鏈表,準(zhǔn)備用C語(yǔ)言擼一遍代碼,建議用typedef定義一下抽象數(shù)據(jù)結(jié)構(gòu)為節(jié)點(diǎn)數(shù)據(jù)域,這樣代碼將很容易變成一個(gè)可實(shí)用的輪子。
有哪些鏈表形式?
單向鏈表
單鏈表包含兩個(gè)域:
-
數(shù)據(jù)信息域,存儲(chǔ)有用信息。 -
next指針域,“next”字段指向節(jié)點(diǎn)行中的下一個(gè)節(jié)點(diǎn)。
鏈表最基本的結(jié)構(gòu)是在每個(gè)節(jié)點(diǎn)保存有用數(shù)據(jù)及下一個(gè)節(jié)點(diǎn)的地址,在最后一個(gè)節(jié)點(diǎn)保存一個(gè)特殊的結(jié)束標(biāo)記,另外在一個(gè)固定的位置保存指向首節(jié)點(diǎn)的指針,應(yīng)用中有時(shí)候也會(huì)儲(chǔ)存指向最后一個(gè)節(jié)點(diǎn)的指針。一般查找一個(gè)節(jié)點(diǎn)的時(shí)候需要從第一個(gè)節(jié)點(diǎn)開始每次訪問(wèn)下一個(gè)節(jié)點(diǎn),一直訪問(wèn)到需要的位置。但是也可以提前把一個(gè)節(jié)點(diǎn)的位置另外保存起來(lái),然后直接訪問(wèn)??梢栽趩捂湵砩蠄?zhí)行的操作包括插入、刪除和遍歷。
雙向鏈表
與單向鏈表相比,雙向鏈表多了一個(gè)指向前一節(jié)點(diǎn)的指針:
雙向鏈表也叫雙鏈表。雙向鏈表中不僅有指向后一個(gè)節(jié)點(diǎn)的指針,還有指向前一個(gè)節(jié)點(diǎn)的指針。這樣可以從任何一個(gè)節(jié)點(diǎn)訪問(wèn)前一個(gè)節(jié)點(diǎn),當(dāng)然也可以訪問(wèn)后一個(gè)節(jié)點(diǎn),以至整個(gè)鏈表。一般是在需要大批量的另外儲(chǔ)存數(shù)據(jù)在鏈表中的位置的時(shí)候用。雙向鏈表也可以配合下面的其他鏈表的擴(kuò)展使用。這樣做好處顯而易見(jiàn),可以從任意節(jié)點(diǎn)遍歷整個(gè)鏈表,但是需要額外為每個(gè)節(jié)點(diǎn)申請(qǐng)一個(gè)指針的存儲(chǔ)空間開銷。
循環(huán)鏈表
循環(huán)鏈表中, 首節(jié)點(diǎn)和末節(jié)點(diǎn)被鏈接在一起。這種數(shù)據(jù)結(jié)構(gòu)在單向和雙向鏈表中都可以實(shí)現(xiàn)。要遍歷一個(gè)循環(huán)鏈表,可以從任意一個(gè)節(jié)點(diǎn)沿著列表的任一方向直到返回開始的節(jié)點(diǎn)。循環(huán)鏈表可以被視為“無(wú)頭無(wú)尾”。這種結(jié)構(gòu)利于節(jié)約內(nèi)存空間。
單向循環(huán)鏈表:
雙向循環(huán)鏈表:
循環(huán)鏈表中第一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)就是最后一個(gè)節(jié)點(diǎn),反之亦然。循環(huán)鏈表的無(wú)邊界
使得在這樣的鏈表設(shè)計(jì)算法方面會(huì)比普通鏈表具有更大的自由度,帶來(lái)更多的便利性。
總結(jié)一下
單向之優(yōu)勢(shì):雖然雙向鏈表和循環(huán)鏈表相比單鏈表具有一些優(yōu)點(diǎn),但是單向鏈表也有一些優(yōu)點(diǎn),在某些情況下更受歡迎。單向鏈表是一種遞歸數(shù)據(jù)結(jié)構(gòu),因?yàn)樗粋€(gè)指向同一類型的較小對(duì)象的指針。由于這個(gè)原因,對(duì)單向鏈表的許多操作(比如合并兩個(gè)列表,或者以相反的順序枚舉元素)通常具有非常簡(jiǎn)單的遞歸算法,比使用迭代命令的解決方案都要簡(jiǎn)單。雖然這些遞歸解決方案可以適用于雙重鏈表和循環(huán)鏈表,但這些過(guò)程通常需要額外的參數(shù)和更復(fù)雜的基本操作。
雙向vs單向:雙向鏈表每個(gè)節(jié)點(diǎn)需要額外的指針存儲(chǔ)空間,而且其基本操作開銷更大,所以這種易用性是有代價(jià)的,易用性體現(xiàn)在允許從兩個(gè)方向?qū)α斜磉M(jìn)行快速而簡(jiǎn)單的順序訪問(wèn)。在雙鏈表中,只要給定一個(gè)節(jié)點(diǎn)的地址,就可以在簡(jiǎn)單幾步操作中插入或刪除該節(jié)點(diǎn)。要在單鏈表中執(zhí)行同樣的操作,必須從首節(jié)點(diǎn)先遍歷找到該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。
應(yīng)用而言:在Linux內(nèi)核以及RTOS的任務(wù)調(diào)度管理中鏈表都有應(yīng)用,實(shí)際編程中什么時(shí)候用,只需要明白數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢(shì)及劣勢(shì)即可做出靈活的取舍。
本文辛苦原創(chuàng)總結(jié),如果覺(jué)得有價(jià)值也請(qǐng)幫忙點(diǎn)贊/在看/轉(zhuǎn)發(fā)支持,不勝感激!
—END—
免責(zé)聲明:本文內(nèi)容由21ic獲得授權(quán)后發(fā)布,版權(quán)歸原作者所有,本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn),不代表本平臺(tái)立場(chǎng),如有問(wèn)題,請(qǐng)聯(lián)系我們,謝謝!