站長資訊網鏈表的操作相對順序表來說就復雜了許多。因為PHP確實已經為我們解決了很多數組操作上的問題，所以我們可以很方便的操作數組，也就不用為數組定義很多的邏輯操作。比如在C中，數組是有長度限制的，而在PHP中我們就不會考慮這個問題。
鏈式結構的定義
首先，在之前的關于線性表的第一篇文章中我們就說過鏈表的定義，在這里，我們再復習一下之前的那個關于鏈表的圖來更清晰的理解鏈表的概念。
我們將圖中的節點 Node 用類來表示：
/** * 鏈表結構 */ class LinkedList { public $data; public $next; }
一個鏈表類就看可以看做是鏈表中的一個節點，它包含兩個內容，data 表示數據，next 表示下一個節點的指針。就像鏈條一樣一環套一環，這就是傳說中的鏈表結構。
生成鏈表及初始化操作
/** * 生成鏈表 */ function createLinkedList() { $list = new LinkedList(); $list->data = null; $list->next = null; return $list; } /** * 初始化鏈表 * @param array $data 鏈表中要保存的數據，這里以數組為參考 * @return LinkedList 鏈表數據 */ function Init(array $data) { // 初始化 $list = createLinkedList(); $r = $list; foreach ($data as $key => $value) { $link = new LinkedList(); $link->data = $value; $link->next = null; $r->next = $link; $r = $link; } return $list; } $link = Init(range(1, 10)); print_r($link); // 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] => // ) // ) // ) // ) // ) // ) // ) // ) // ) // ) // )
在使用鏈表的時候，我們一般會讓第一個結點不包含任何數據，僅僅是做為一個空的結點來指向第一個有數據的結點。這種結點我們可以稱之為頭結點，如果需要判斷鏈表是否為空的話，只需要判斷第一個結點的 next 是否為空就可以了。在上面的代碼中，創建鏈表 createLinkedList() 函數其實就是生成了這樣一個頭結點。
然后，我們通過 Init() 初始化函數來構造這個鏈表。構造過程還是比較簡單的，這里我們是固定的傳遞進來一個數組，按照這個數組結構來構造這個鏈表，當然，在實際應用中，我們可以使用任何數據來構造鏈表。構造過程也并不復雜，將當前結點賦值給 r 變量，然后創建一個新結點，讓 r->next 等于這個新創建的節點就可以了。構造好的鏈表直接打印出來的結構就是注釋中的形式。
遍歷鏈表
function IteratorLinkedList(LinkedList $link) { while (($link = $link->next) != null) { echo $link->data, ','; } echo PHP_EOL; }
鏈表的遍歷是不是非常像某些數據庫的游標操作，或者像迭代器模式的操作一樣。沒錯，其實游標和迭代器的結構就是鏈表的一種表現形式。我們不停的尋找 $next 直到沒有下一個結點為止，這樣就完成了一次鏈表的遍歷。可以看出，這個過程的時間復雜度是 O(n) 。
插入、刪除
/** * 鏈表指定位置插入元素 * @param LinkedList $list 鏈表數據 * @param int $i 位置 * @param mixed $data 數據 */ function Insert(LinkedList &$list, int $i, $data) { $j = 0; $item = $list; // 遍歷鏈表，找指定位置的前一個位置 while ($j < $i - 1) { $item = $item->next; $j++; } // 如果 item 不存在或者 $i > n+1 或者 $i < 0 if ($item == null || $j > $i - 1) { return false; } // 創建一個新節點 $s = new LinkedList(); $s->data = $data; // 新創建節點的下一個節點指向原 i-1 節點的下一跳節點，也就是當前的 i 節點 $s->next = $item->next; // 將 i-1 節點的下一跳節點指向 s ，完成將 s 插入指定的 i 位置，并讓原來的 i 位置元素變成 i+1 位置 $item->next = $s; return true; } /** * 刪除鏈表指定位置元素 * @param LinkedList $list 鏈表數據 * @param int $i 位置 */ function Delete(LinkedList &$list, int $i) { $j = 0; $item = $list; // 遍歷鏈表，找指定位置的前一個位置 while ($j < $i - 1) { $item = $item->next; $j++; } // 如果 item 不存在或者 $i > n+1 或者 $i < 0 if ($item == null || $j > $i - 1) { return false; } // 使用一個臨時節點保存當前節點信息，$item 是第 i-1 個節點，所以 $item->next 就是我們要找到的當前這個 i 節點 $temp = $item->next; // 讓當前節點，也就是目標節點的上一個節點， i-1 的這個節點的下一跳（原來的 i 位置的節點）變成原來 i 位置節點的下一跳 next 節點，讓i位置的節點脫離鏈條 $item->next = $temp->next; return true; } // 插入 Insert($link, 5, 55); // 遍歷鏈表 IteratorLinkedList($link); // 1,2,3,4,55,5,6,7,8,9,10, // 刪除 Delete($link, 7); // 遍歷鏈表 IteratorLinkedList($link); // 1,2,3,4,55,5,7,8,9,10,
鏈表的插入和刪除其實很類似，都是需要尋找到插入或刪除位置的前一個元素，也就是第 i-1 這個位置的元素。然后通過對這個元素的 next 指針的操作來實現鏈表元素的插入刪除操作。
它們在遍歷和位置判斷這兩個功能中的代碼其實都是一樣的，不同的是創建時要新創建一個結點，然后讓這個結點的 next 指向之前 i-1 位置元素的 next ，再將 i-1 位置元素的 next 指向新創建的這個結點。而刪除操作則是保存要刪除這個位置 i 的結點到一個臨時變量中，然后將 i-1 位置元素的 next 指向刪除位置 i 的 next 。
上面的解釋需要結合代碼一步一步來看，當然，我們也可以結合下面的這個圖來學習。插入和刪除操作是鏈表操作的核心，也是最復雜的部分，需要多多理解掌握。
根據位置查找、根據數據查找
/** * 根據位置查找元素位置 * @param LinkedList $list 鏈表數據 * @param int $i 位置 */ function GetElem(LinkedList &$list, int $i) { $item = $list; $j = 1; // 從第一個開始查找，0是頭結點 while ($item && $j <= $i) { $item = $item->next; $j++; } if (!$item || $j > $i + 1) { return false; } return $item->data; } /** * 根據數據查找數據元素所在位置 * @param LinkedList $list 鏈表數據 * @param mixed $data 數據 */ function LocateElem(LinkedList &$list, $data) { $item = $list; $j = 1; // 從第一個開始查找，0是頭結點 while (($item = $item->next)!=null) { if($item->data == $data){ return $j; } $j++; } return false; } // 獲取指定位置的元素內容 var_dump(GetElem($link, 5)); // int(55) // 獲取指定元素所在的位置 var_dump(LocateElem($link, 55)); // int(5)
鏈表的查找有兩種形式，一種是給一個位置，比如要我要第五個位置的元素內容，那么就是根據指定位置查找元素的值，就像數組的下標一樣。不過需要注意的是，鏈表的下標是從 1 開始的，因為 0 的位置是我們的頭結點了。當然，我們也可以變換代碼忽略掉頭結點讓它和數組保持一致，但這樣的話，鏈表的特點就不明顯了，所以這里的測試代碼我們還是以 1 為起始。
另一種查找就是給定一個數據內容，查找它在鏈表的什么位置。其實這兩種算法都是在遍歷整個鏈表，本質上沒有什么區別。由于鏈表不像數組一樣有下標的能力，所以它的這些查找操作的時間復雜度都是 O(n) 。
總結
怎么樣，難度上來了吧。鏈表的操作一下就復雜了很多吧，別急，這只是開胃菜。后面學習的內容基本上都會圍繞著順序表（數組）和鏈表這兩種形式進行。而且我們的鏈表學習還沒有結束，下一篇文章，我們將更深入的了解一下鏈表的另外幾種形式：雙向鏈表、循環鏈表、雙向循環鏈表。
測試代碼：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.線性表/source/2.3%20鏈表的相關邏輯操作.php
推薦學習：php視頻教程
