手撕408|數(shù)據(jù)結(jié)構(gòu)之鏈表(3)
通知：冷月目前提供免費(fèi)408 1對(duì)1輔導(dǎo)，有需要的同學(xué)可以加我微信：lengyue408。
手撕408系列之?dāng)?shù)據(jù)結(jié)構(gòu)之鏈表，冷月出品必是精品，大家好，我是學(xué)長(zhǎng)冷月。
昨天咱們介紹了線性表中順序表（數(shù)組）的相關(guān)知識(shí)，今天我們接著學(xué)習(xí)線性表的另一個(gè)經(jīng)典數(shù)據(jù)結(jié)構(gòu)—鏈表。
定義
除了第一個(gè)元素，其他元素有且只有一個(gè)直接前驅(qū)；除了最后一個(gè)元素，其他元素有且只有一個(gè)直接后繼；并且在邏輯上相鄰，物理上不一定相鄰的線性表。符合這樣的數(shù)據(jù)結(jié)構(gòu)稱為鏈表。如下圖所示：
基礎(chǔ)術(shù)語(yǔ)
鏈表中有幾個(gè)常用到的術(shù)語(yǔ)，大家先了解一下。其實(shí)這類術(shù)語(yǔ)大家切記不要死記硬背。在題目中遇到的時(shí)候，反復(fù)翻看，熟練后自然就可以記住。
首節(jié)點(diǎn)：有效元素的第一個(gè)節(jié)點(diǎn)
尾節(jié)點(diǎn)：有效元素的最后一個(gè)節(jié)點(diǎn)
頭結(jié)點(diǎn)：首節(jié)點(diǎn)前面的節(jié)點(diǎn)
頭指針：指向頭結(jié)點(diǎn)的指針
尾指針：指向尾節(jié)點(diǎn)的指針
分類
單鏈表
最簡(jiǎn)單的鏈表，每個(gè)一個(gè)節(jié)點(diǎn)內(nèi)分為數(shù)據(jù)域和指針域，如下圖所示：
雙鏈表
相對(duì)于單鏈表，雙鏈表有兩個(gè)指針域。一個(gè)指向前驅(qū)，一個(gè)指向后繼，如下圖所示：
循環(huán)鏈表
最后一個(gè)節(jié)點(diǎn)的指針域指向第一個(gè)節(jié)點(diǎn)，如下圖所示：
靜態(tài)鏈表
利用一個(gè)二維數(shù)組，指針域就是數(shù)組的下標(biāo)，如下圖所示：
其特點(diǎn)有：1、預(yù)先分配一塊連續(xù)的內(nèi)存空間；2、插入、刪除無(wú)需移動(dòng)元素。
與順序表之間的關(guān)系
1、存取方式
數(shù)組既可以隨機(jī)存取也可以順序存取，而鏈表只能從前往后順序存取。
2、存儲(chǔ)方式
順序表邏輯上相鄰、物理上也相鄰
鏈表邏輯上相鄰、物理上不一定相鄰
3、查找方式
按值查找：數(shù)組無(wú)序，則都為O(n);數(shù)組有序，可以采用折半查找，O(logn)。
按下標(biāo)查找：數(shù)組可以采用隨機(jī)存取，時(shí)間復(fù)雜度為O(1)；而鏈表從前往后查找，時(shí)間復(fù)雜度O(n)。
明天別忘了來(lái)做題！
關(guān)注下方“學(xué)長(zhǎng)冷月”可獲得更多408答題技巧及資料。
請(qǐng)幫冷月點(diǎn)一下旁邊的在看，再點(diǎn)一個(gè)贊,一鍵三連支持一下！您的每一次點(diǎn)擊都是對(duì)冷月莫大的鼓勵(lì)，謝謝！！
點(diǎn)“在看”給我一朵小黃花
