PHP面試常考之?dāng)?shù)據(jù)結(jié)構(gòu)——鏈表的概念

dreamans 發(fā)布于2019-07-01 12:35 / 426人閱讀

摘要：一鏈表鏈表是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針。指向整個(gè)列表的指針可以被稱作訪問指針。

你好，是我琉憶，PHP程序員面試筆試系列圖書的作者。

本周（2019.3.18至3.22）的一三五更新的文章如下：

周一：PHP面試常考之?dāng)?shù)據(jù)結(jié)構(gòu)——鏈表的概念
周三：PHP面試常考之?dāng)?shù)據(jù)結(jié)構(gòu)——棧和隊(duì)列
周五：PHP面試常考之?dāng)?shù)據(jù)結(jié)構(gòu)——

自己整理了一篇“PHP如何實(shí)現(xiàn)鏈表？”的文章，關(guān)注公眾號(hào)：“琉憶編程庫”，回復(fù)：“鏈表”，我發(fā)給你。

一、鏈表

鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)。
使用鏈表結(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)的指針域，空間開銷比較大。

鏈表有很三種不同的類型：單向鏈表，雙向鏈表以及循環(huán)鏈表。

二、單向鏈表

單向鏈表包含兩個(gè)域，一個(gè)信息域和一個(gè)指針域。這個(gè)鏈接指向列表中的下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)則指向一個(gè)空值。
如圖：

三、雙向鏈表

每個(gè)節(jié)點(diǎn)有兩個(gè)連接：一個(gè)指向前一個(gè)節(jié)點(diǎn)，（當(dāng)此“連接”為第一個(gè)“連接”時(shí)，指向空值或者空列表）；而另一個(gè)指向下一個(gè)節(jié)點(diǎn)，（當(dāng)此“連接”為最后一個(gè)“連接”時(shí)，指向空值或者空列表）
如圖：

四、循環(huán)鏈表

在一個(gè)循環(huán)鏈表中,首節(jié)點(diǎn)和末節(jié)點(diǎn)被連接在一起。這種方式在單向和雙向鏈表中皆可實(shí)現(xiàn)。要轉(zhuǎn)換一個(gè)循環(huán)鏈表，你開始于任意一個(gè)節(jié)點(diǎn)然后沿著列表的任一方向直到返回開始的節(jié)點(diǎn)。再來看另一種方法，循環(huán)鏈表可以被視為“無頭無尾”。這種列表很利于節(jié)約數(shù)據(jù)存儲(chǔ)緩存，假定你在一個(gè)列表中有一個(gè)對(duì)象并且希望所有其他對(duì)象迭代在一個(gè)非特殊的排列下。指向整個(gè)列表的指針可以被稱作訪問指針。

自己編寫的《PHP程序員面試筆試寶典》和《PHP程序員面試筆試真題解析》書籍，已在各大電商平臺(tái)銷售，兩本可以幫助你更快更好的拿到offer的書。

更多PHP相關(guān)的面試知識(shí)、考題可以關(guān)注公眾號(hào)獲取：琉憶編程庫

對(duì)本文有什么問題或建議都可以進(jìn)行留言，我將不斷完善追求極致，感謝你們的支持。