詳解php中的鍊錶

鍊錶的操作相對順序表來說就複雜了許多。因為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影片教學

#

以上是詳解php中的鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章！