php中鏈表的表現(xiàn)形式有哪些

這篇文章主要介紹php中鏈表的表現(xiàn)形式有哪些，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

創(chuàng)新互聯(lián)長期為1000+客戶提供的網(wǎng)站建設(shè)服務(wù)，團隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為花都企業(yè)提供專業(yè)的成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)，花都網(wǎng)站改版等技術(shù)服務(wù)。擁有十余年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

循環(huán)鏈表

就像上文所說的，我們讓最后一個節(jié)點指向第一個節(jié)點，這樣形成的鏈表就是一個循環(huán)鏈表，如下圖所示：

關(guān)于循環(huán)的鏈表的操作我們不做詳細的說明，其實大部分代碼和單向鏈表是一樣的，只是需要注意兩個地方：

1.初始化、插入操作的時候，注意最后一個節(jié)點的指向，最后一個節(jié)點的 next 要指向第一個節(jié)點

2.判斷鏈表遍歷是否完成的條件為 item->next == head ，也就是說，判斷這個節(jié)點的下一個節(jié)點如果是頭節(jié)點的話，鏈表就遍歷完成了。

雙向鏈表

雙向鏈表則是在 LinkedList 這個類里面增加一個屬性來指向上一個節(jié)點。

// 雙向鏈表
class LinkedList
{
    public $data;

    public $prev;
    public $next;
}

php中鏈表的表現(xiàn)形式有哪些

接下來，我們初始化一個雙向鏈表。

/**
 * 生成鏈表
 */
function createLinkedList()
{
    $list = new LinkedList();
    $list->data = null;
    $list->next = null;
    $list->prev = null; // ** 全部都初始化為 null **
    return $list;
}

/**
 * 初始化鏈表
 * @param array $data 鏈表中要保存的數(shù)據(jù)，這里以數(shù)組為參考
 * @return LinkedList 鏈表數(shù)據(jù)
 */
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;
        $link->prev = $r; // ** 增加上級指向 **
        $r = $link;
    }
    return $list;
}

$link = Init(range(1, 10));

var_dump($link);
var_dump($link->next->next->next->next);
// object(LinkedList)#5 (3) {
//     ["data"]=>
//     int(4)
//     ["prev"]=>
//     object(LinkedList)#4 (3) {
//       ["data"]=>
//       int(3)
//       ["prev"]=>
//       object(LinkedList)#3 (3) {
//         ["data"]=>
//         int(2)
//         ["prev"]=>
//         object(LinkedList)#2 (3) {
//           ["data"]=>
//           int(1)
//           ["prev"]=>
//           object(LinkedList)#1 (3) {
//             ["data"]=>
//             NULL
//             ["prev"]=>
//             NULL
//             ["next"]=>
//             *RECURSION*
//           }
//           ["next"]=>
//           *RECURSION*
//         }
//         ["next"]=>
//         *RECURSION*
//       }
//       ["next"]=>
//       *RECURSION*
//     }
//     ["next"]=>
//     object(LinkedList)#6 (3) {
//       ["data"]=>
//       int(5)
//       ["prev"]=>
//       *RECURSION*
//       ["next"]=>
//       object(LinkedList)#7 (3) {
//         ["data"]=>
//         int(6)
//         ["prev"]=>
//         *RECURSION*
//         ["next"]=>
//         object(LinkedList)#8 (3) {
//           ["data"]=>
//           int(7)
//           ["prev"]=>
//           *RECURSION*
//           ["next"]=>
//           object(LinkedList)#9 (3) {
//             ["data"]=>
//             int(8)
//             ["prev"]=>
//             *RECURSION*
//             ["next"]=>
//             object(LinkedList)#10 (3) {
//               ["data"]=>
//               int(9)
//               ["prev"]=>
//               *RECURSION*
//               ["next"]=>
//               object(LinkedList)#11 (3) {
//                 ["data"]=>
//                 int(10)
//                 ["prev"]=>
//                 *RECURSION*
//                 ["next"]=>
//                 NULL
//               }
//             }
//           }
//         }
//       }
//     }
//   }

echo $link->next->next->next->next->data, PHP_EOL; // 4
echo $link->next->next->next->next->prev->data, PHP_EOL; // 3

可以看出，與單向鏈表不同的地方就在于多增加了對于 prev 屬性的操作。這里還是比較好理解的。直接打印鏈表會顯示很多的 *RECURSION* 內(nèi)容，這是 PHP 的一種輸出的保護機制，這個標識說明當(dāng)前這個屬性變量是有遞歸類型的。

/**
 * 鏈表指定位置插入元素
 * @param LinkedList $list 鏈表數(shù)據(jù)
 * @param int $i 位置
 * @param mixed $data 數(shù)據(jù)
 */
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;
    }

    // 創(chuàng)建一個新節(jié)點
    $s = new LinkedList();
    $s->data = $data;

    // 新創(chuàng)建節(jié)點的下一個節(jié)點指向原 i-1 節(jié)點的下一跳節(jié)點，也就是當(dāng)前的 i 節(jié)點
    $s->next = $item->next;

    // ** 增加當(dāng)前新創(chuàng)建的節(jié)點的上級指向 **
    $s->prev = $item;

    // 將 i-1 節(jié)點的下一跳節(jié)點指向 s ，完成將 s 插入指定的 i 位置，并讓原來的 i 位置元素變成 i+1 位置
    $item->next = $s;

    // ** 將下級節(jié)點的 prev 指向新創(chuàng)建的這個節(jié)點 **
    $s->next->prev = $s;

    return true;
}

鏈表的插入其實就是增加了兩行代碼，一個是當(dāng)前新創(chuàng)建的節(jié)點的上級的指向，也就是將這個新節(jié)點的上級指定為 i-1 個節(jié)點。而另一個是將原來 i 位置節(jié)點的上級指向修改為當(dāng)前新創(chuàng)建的這個節(jié)點。

/**
 * 刪除鏈表指定位置元素
 * @param LinkedList $list 鏈表數(shù)據(jù)
 * @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;
    }

    // 使用一個臨時節(jié)點保存當(dāng)前節(jié)點信息，$item 是第 i-1 個節(jié)點，所以 $item->next 就是我們要找到的當(dāng)前這個 i 節(jié)點
    $temp = $item->next;
    // 讓當(dāng)前節(jié)點，也就是目標節(jié)點的上一個節(jié)點， i-1 的這個節(jié)點的下一跳（原來的 i 位置的節(jié)點）變成原來 i 位置節(jié)點的下一跳 next 節(jié)點，讓i位置的節(jié)點脫離鏈條
    $item->next = $temp->next;

    // ** 讓目標下一個節(jié)點的上級指針指向當(dāng)前這個節(jié)點 **
    $temp->next->prev = $item;

    return true;
}

與插入節(jié)點操作類似，刪除節(jié)點操作除了將 i-1 個位置節(jié)點的數(shù)據(jù)的下一個節(jié)點的指向變?yōu)?i 節(jié)點的下一級節(jié)點的指向之外，還要將 i 的下一級節(jié)點的上級節(jié)點指向改為 i-1 節(jié)點。

其實，雙向鏈表的定義和操作相比單向鏈表來說差別并不大，就是多了一個 prev 用來指向上一級節(jié)點而已，本質(zhì)上也只是多了對于 prev 這個屬性的操作而已。那么，多出來的這一個上級指針能帶來什么好處呢？在遍歷鏈表的時候，我們通過 prev ，就多了一種遍歷方式，也就是反向的對鏈表進行遍歷。在查找某個元素的時候，我們可以從兩個方向同時進行查找，效率是不是一下子就提升了一倍。原來 O(n) 的時間復(fù)雜度瞬間可以變成 O(n/2) 的時間復(fù)雜度。

雙向循環(huán)鏈表

最后，我們也簡單的來介紹一下雙向循環(huán)鏈表。顧名思義，它就是在雙向鏈表的基礎(chǔ)上加上循環(huán)鏈表的概念。讓最后一個節(jié)點的 next 指向頭節(jié)點，讓頭節(jié)點的 prev 指向最后一個節(jié)點。說起來容易但實現(xiàn)起來其實要復(fù)雜很多，因為你不僅要關(guān)注最后一個節(jié)點的下級節(jié)點指向問題，而且還要關(guān)注頭節(jié)點的上級指向問題。所以在這里我們就不多做代碼演示了，最主要的就是在插入和刪除頭、尾節(jié)點的時候需要多注意它們上下級節(jié)點的指向。

php中鏈表的表現(xiàn)形式有哪些

以上是“php中鏈表的表現(xiàn)形式有哪些”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

本文題目：php中鏈表的表現(xiàn)形式有哪些
當(dāng)前網(wǎng)址：http://bm7419.com/article40/gipeho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、電子商務(wù)、品牌網(wǎng)站制作、企業(yè)網(wǎng)站制作、企業(yè)建站、服務(wù)器托管

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容