鏈表的相關(guān)邏輯操作 鏈表的操作相對(duì)順序表（數(shù)組）來說就復(fù)雜了許多。因?yàn)?PHP 確實(shí)已經(jīng)為我們解決了很多數(shù)組操作上的問題，所以我們可以很方便的操作數(shù)組，也就不用為數(shù)組定義很多的邏輯操作。比如在 C 中，數(shù)組是有長(zhǎng)度限制的，而在 PHP 中我們就不會(huì)考慮這個(gè)問題。如果是使用 C 的話，這個(gè)長(zhǎng)度限制就是數(shù)組結(jié)構(gòu)的一大劣勢(shì)，而鏈表，不管是在 C 還是在 PHP 中，都不會(huì)受到長(zhǎng)度問題的限制。能夠限制鏈表的只有內(nèi)存的大小。另外，鏈表的鏈?zhǔn)浇Y(jié)構(gòu)也能夠?yàn)槲覀儙硪环N全新的不同于數(shù)組操作的體驗(yàn)，對(duì)某些功能算法來說，鏈表也更有優(yōu)勢(shì)。
話不多說，直接來進(jìn)入今天的內(nèi)容吧！
鏈?zhǔn)浇Y(jié)構(gòu)的定義 首先，在之前的關(guān)于線性表的第一篇文章中我們就說過鏈表的定義，在這里，我們?cè)購(gòu)?fù)習(xí)一下之前的那個(gè)關(guān)于鏈表的圖來更清晰的理解鏈表的概念。
我們將圖中的節(jié)點(diǎn) Node 用類來表示：
/** class LinkedList public $data;public $next;一個(gè)鏈表類就看可以看做是鏈表中的一個(gè)節(jié)點(diǎn)，它包含兩個(gè)內(nèi)容，data 表示數(shù)據(jù)，next 表示下一個(gè)節(jié)點(diǎn)的指針。就像鏈條一樣一環(huán)套一環(huán)，這就是傳說中的鏈表結(jié)構(gòu)。
生成鏈表及初始化操作 /** function createLinkedList () new LinkedList();null ;null ;return $list;/**@param array $data 鏈表中要保存的數(shù)據(jù)，這里以數(shù)組為參考@return LinkedList 鏈表數(shù)據(jù) function Init (array $data) // 初始化 foreach ($data as $key => $value) {new LinkedList();null ;return $list;1 , 10 ));// LinkedList Object // ( // [data] => // [next] => LinkedList Object // ( // [data] => 1 // [next] => LinkedList Object // ( // [data] => 2 // [next] => LinkedList Object // ( // [data] => 3 // [next] => LinkedList Object // ( // [data] => 4 // [next] => LinkedList Object // ( // [data] => 5 // [next] => LinkedList Object // ( // [data] => 6 // [next] => LinkedList Object // ( // [data] => 7 // [next] => LinkedList Object // ( // [data] => 8 // [next] => LinkedList Object // ( // [data] => 9 // [next] => LinkedList Object // ( // [data] => 10 // [next] => // ) // ) // ) // ) // ) // ) // ) // ) // ) // ) // ) 在使用鏈表的時(shí)候，我們一般會(huì)讓第一個(gè)結(jié)點(diǎn)不包含任何數(shù)據(jù)，僅僅是做為一個(gè)空的結(jié)點(diǎn)來指向第一個(gè)有數(shù)據(jù)的結(jié)點(diǎn)。這種結(jié)點(diǎn)我們可以稱之為頭結(jié)點(diǎn)，如果需要判斷鏈表是否為空的話，只需要判斷第一個(gè)結(jié)點(diǎn)的 next 是否為空就可以了。在上面的代碼中，創(chuàng)建鏈表 createLinkedList() 函數(shù)其實(shí)就是生成了這樣一個(gè)頭結(jié)點(diǎn)。
然后，我們通過 Init() 初始化函數(shù)來構(gòu)造這個(gè)鏈表。構(gòu)造過程還是比較簡(jiǎn)單的，這里我們是固定的傳遞進(jìn)來一個(gè)數(shù)組，按照這個(gè)數(shù)組結(jié)構(gòu)來構(gòu)造這個(gè)鏈表，當(dāng)然，在實(shí)際應(yīng)用中，我們可以使用任何數(shù)據(jù)來構(gòu)造鏈表。構(gòu)造過程也并不復(fù)雜，將當(dāng)前結(jié)點(diǎn)賦值給 r 變量，然后創(chuàng)建一個(gè)新結(jié)點(diǎn)，讓 r->next 等于這個(gè)新創(chuàng)建的節(jié)點(diǎn)就可以了。構(gòu)造好的鏈表直接打印出來的結(jié)構(gòu)就是注釋中的形式。
遍歷鏈表 function IteratorLinkedList (LinkedList $link) while (($link = $link->next) != null ) {echo $link->data, ',' ;echo PHP_EOL;鏈表的遍歷是不是非常像某些數(shù)據(jù)庫的游標(biāo)操作，或者像迭代器模式的操作一樣。沒錯(cuò)，其實(shí)游標(biāo)和迭代器的結(jié)構(gòu)就是鏈表的一種表現(xiàn)形式。我們不停的尋找 $next 直到?jīng)]有下一個(gè)結(jié)點(diǎn)為止，這樣就完成了一次鏈表的遍歷?？梢钥闯?，這個(gè)過程的時(shí)間復(fù)雜度是 O(n) 。
插入、刪除 /**@param LinkedList $list 鏈表數(shù)據(jù)@param int $i 位置@param mixed $data 數(shù)據(jù) function Insert (LinkedList &$list, int $i, $data) 0 ;// 遍歷鏈表，找指定位置的前一個(gè)位置 while ($j < $i - 1 ) {// 如果 item 不存在或者 $i > n+1 或者 $i < 0 if ($item == null || $j > $i - 1 ) {return false ;// 創(chuàng)建一個(gè)新節(jié)點(diǎn) new LinkedList();// 新創(chuàng)建節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向原 i-1 節(jié)點(diǎn)的下一跳節(jié)點(diǎn)，也就是當(dāng)前的 i 節(jié)點(diǎn) // 將 i-1 節(jié)點(diǎn)的下一跳節(jié)點(diǎn)指向 s ，完成將 s 插入指定的 i 位置，并讓原來的 i 位置元素變成 i+1 位置 return true ;/**@param LinkedList $list 鏈表數(shù)據(jù)@param int $i 位置 function Delete (LinkedList &$list, int $i) 0 ;// 遍歷鏈表，找指定位置的前一個(gè)位置 while ($j < $i - 1 ) {// 如果 item 不存在或者 $i > n+1 或者 $i < 0 if ($item == null || $j > $i - 1 ) {return false ;// 使用一個(gè)臨時(shí)節(jié)點(diǎn)保存當(dāng)前節(jié)點(diǎn)信息，$item 是第 i-1 個(gè)節(jié)點(diǎn)，所以 $item->next 就是我們要找到的當(dāng)前這個(gè) i 節(jié)點(diǎn) // 讓當(dāng)前節(jié)點(diǎn)，也就是目標(biāo)節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)， i-1 的這個(gè)節(jié)點(diǎn)的下一跳（原來的 i 位置的節(jié)點(diǎn)）變成原來 i 位置節(jié)點(diǎn)的下一跳 next 節(jié)點(diǎn)，讓i位置的節(jié)點(diǎn)脫離鏈條 return true ;// 插入 5 , 55 );// 遍歷鏈表 // 1,2,3,4,55,5,6,7,8,9,10, // 刪除 7 );// 遍歷鏈表 // 1,2,3,4,55,5,7,8,9,10, 鏈表的插入和刪除其實(shí)很類似，都是需要尋找到插入或刪除位置的前一個(gè)元素，也就是第 i-1 這個(gè)位置的元素。然后通過對(duì)這個(gè)元素的 next 指針的操作來實(shí)現(xiàn)鏈表元素的插入刪除操作。它們?cè)诒闅v和位置判斷這兩個(gè)功能中的代碼其實(shí)都是一樣的，不同的是創(chuàng)建時(shí)要新創(chuàng)建一個(gè)結(jié)點(diǎn)，然后讓這個(gè)結(jié)點(diǎn)的 next 指向之前 i-1 位置元素的 next ，再將 i-1 位置元素的 next 指向新創(chuàng)建的這個(gè)結(jié)點(diǎn)。而刪除操作則是保存要?jiǎng)h除這個(gè)位置 i 的結(jié)點(diǎn)到一個(gè)臨時(shí)變量中，然后將 i-1 位置元素的 next 指向刪除位置 i 的 next 。
上面的解釋需要結(jié)合代碼一步一步來看，當(dāng)然，我們也可以結(jié)合下面的這個(gè)圖來學(xué)習(xí)。插入和刪除操作是鏈表操作的核心，也是最復(fù)雜的部分，需要多多理解掌握。
根據(jù)位置查找、根據(jù)數(shù)據(jù)查找 /**@param LinkedList $list 鏈表數(shù)據(jù)@param int $i 位置 function GetElem (LinkedList &$list, int $i) 1 ; // 從第一個(gè)開始查找，0是頭結(jié)點(diǎn) while ($item && $j <= $i) {if (!$item || $j > $i + 1 ) {return false ;return $item->data;/**@param LinkedList $list 鏈表數(shù)據(jù)@param mixed $data 數(shù)據(jù) function LocateElem (LinkedList &$list, $data) 1 ; // 從第一個(gè)開始查找，0是頭結(jié)點(diǎn) while (($item = $item->next)!=null ) {if ($item->data == $data){return $j;return false ;// 獲取指定位置的元素內(nèi)容 5 )); // int(55) // 獲取指定元素所在的位置 55 )); // int(5) 鏈表的查找有兩種形式，一種是給一個(gè)位置，比如要我要第五個(gè)位置的元素內(nèi)容，那么就是根據(jù)指定位置查找元素的值，就像數(shù)組的下標(biāo)一樣。不過需要注意的是，鏈表的下標(biāo)是從 1 開始的，因?yàn)?0 的位置是我們的頭結(jié)點(diǎn)了。當(dāng)然，我們也可以變換代碼忽略掉頭結(jié)點(diǎn)讓它和數(shù)組保持一致，但這樣的話，鏈表的特點(diǎn)就不明顯了，所以這里的測(cè)試代碼我們還是以 1 為起始。
另一種查找就是給定一個(gè)數(shù)據(jù)內(nèi)容，查找它在鏈表的什么位置。其實(shí)這兩種算法都是在遍歷整個(gè)鏈表，本質(zhì)上沒有什么區(qū)別。由于鏈表不像數(shù)組一樣有下標(biāo)的能力，所以它的這些查找操作的時(shí)間復(fù)雜度都是 O(n) 。
總結(jié) 怎么樣，難度上來了吧。鏈表的操作一下就復(fù)雜了很多吧，別急，這只是開胃菜。后面學(xué)習(xí)的內(nèi)容基本上都會(huì)圍繞著順序表（數(shù)組）和鏈表這兩種形式進(jìn)行。而且我們的鏈表學(xué)習(xí)還沒有結(jié)束，下一篇文章，我們將更深入的了解一下鏈表的另外幾種形式：雙向鏈表、循環(huán)鏈表、雙向循環(huán)鏈表。
測(cè)試代碼：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.線性表/source/2.3%20鏈表的相關(guān)邏輯操作.php
參考資料：
《數(shù)據(jù)結(jié)構(gòu)》第二版，嚴(yán)蔚敏
《數(shù)據(jù)結(jié)構(gòu)》第二版，陳越
《數(shù)據(jù)結(jié)構(gòu)高分筆記》2020版，天勤考研
