PHP面試常考之資料結構——連結串列的概念
你好,是我琉憶,PHP程式設計師面試筆試系列圖書的作者。
本週(2019.3.18至3.22)的一三五更新的文章如下:
週一:PHP面試常考之資料結構——連結串列的概念
週三:PHP面試常考之資料結構——棧和佇列
週五:PHP面試常考之資料結構——
自己整理了一篇“ PHP如何實現連結串列? ”的文章,關注公眾號:“ 琉憶程式設計庫 ”,回覆:“ 連結串列 ”,我發給你。
一、連結串列
連結串列(Linked list)是一種常見的基礎資料結構,是一種線性表,但是並不會按線性的順序儲存資料,而是在每一個節點裡存到下一個節點的指標(Pointer)。
使用連結串列結構可以克服陣列連結串列需要預先知道資料大小的缺點,連結串列結構可以充分利用計算機記憶體空間,實現靈活的記憶體動態管理。但是連結串列失去了陣列隨機讀取的優點,同時連結串列由於增加了結點的指標域,空間開銷比較大。
連結串列有很三種不同的型別:單向連結串列,雙向連結串列以及迴圈連結串列。
二、單向連結串列
單向連結串列包含兩個域,一個資訊域和一個指標域。這個連結指向列表中的下一個節點,而最後一個節點則指向一個空值。
如圖:
三、雙向連結串列
每個節點有兩個連線:一個指向前一個節點,(當此“連線”為第一個“連線”時,指向空值或者空列表);而另一個指向下一個節點,(當此“連線”為最後一個“連線”時,指向空值或者空列表)
如圖:
四、迴圈連結串列
在一個迴圈連結串列中,首節點和末節點被連線在一起。這種方式在單向和雙向連結串列中皆可實現。要轉換一個迴圈連結串列,你開始於任意一個節點然後沿著列表的任一方向直到返回開始的節點。再來看另一種方法,迴圈連結串列可以被視為“無頭無尾”。這種列表很利於節約資料儲存快取,假定你在一個列表中有一個物件並且希望所有其他物件迭代在一個非特殊的排列下。指向整個列表的指標可以被稱作訪問指標。
自己編寫的 《PHP程式設計師面試筆試寶典》 和 《PHP程式設計師面試筆試真題解析》 書籍,已在各大電商平臺銷售,兩本可以幫助你更快更好的拿到offer的書。
更多PHP相關的面試知識、考題可以關注公眾號獲取: 琉憶程式設計庫