萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 實作雙向鏈結串列完整範例

雙向鏈結串列每個節點同時擁有指向前一個與下一個節點的指標,支援雙向遍歷、高效插入刪除。本文提供完整 PHP 實作,包含節點類別、依編號排序插入、刪除、遍歷列印功能。

節點類別 Hero

class Hero {
    public $no;
    public $name;
    public $next = null;
    public $pre = null;

    public function __construct($no, $name) {
        $this->no = $no;
        $this->name = $name;
    }

    // 靜態方法:依編號升序插入
    static public function addHero($head, $hero) {
        $cur = $head;
        $isExist = false;

        // 空鏈表
        if ($cur->next == null) {
            $cur->next = $hero;
            $hero->pre = $cur;
            return;
        }

        // 尋找插入位置
        while ($cur->next != null) {
            if ($cur->next->no > $hero->no) break;
            if ($cur->next->no == $hero->no) {
                $isExist = true;
                echo "不能新增相同編號\n";
                break;
            }
            $cur = $cur->next;
        }

        if (!$isExist) {
            if ($cur->next != null) {
                $hero->next = $cur->next;
                $hero->next->pre = $hero;
            }
            $hero->pre = $cur;
            $cur->next = $hero;
        }
    }

    // 遍歷列印
    static public function showHero($head) {
        $cur = $head;
        while ($cur->next != null) {
            echo "編號:{$cur->next->no} 名字:{$cur->next->name}\n";
            $cur = $cur->next;
        }
    }

    // 依編號刪除
    static public function delHero($head, $herono) {
        $cur = $head;
        $isFind = false;
        while ($cur != null) {
            if ($cur->no == $herono) {
                $isFind = true;
                break;
            }
            $cur = $cur->next;
        }

        if ($isFind) {
            if ($cur->next != null) {
                $cur->next->pre = $cur->pre;
            }
            $cur->pre->next = $cur->next;
        } else {
            echo "沒有找到目標\n";
        }
    }
}

測試程式碼

$head = new Hero(0, 'head'); // 頭節點(哨兵)
$hero1 = new Hero(1, '1111');
$hero3 = new Hero(3, '3333');
$hero2 = new Hero(2, '2222');

Hero::addHero($head, $hero1);
Hero::addHero($head, $hero3);
Hero::addHero($head, $hero2);

Hero::showHero($head);
// 輸出:
// 編號:1 名字:1111
// 編號:2 名字:2222
// 編號:3 名字:3333

Hero::delHero($head, 2);
Hero::showHero($head);
// 輸出:
// 編號:1 名字:1111
// 編號:3 名字:3333

關鍵點解析

  • 哨兵節點:$head 不存放資料,僅作為鏈表起始標記,簡化邊界判斷。
  • 插入邏輯:找到第一個 next->no > 新節點no 的位置,調整四個指標(新節點的 pre/next、前後節點的 next/pre)。
  • 刪除邏輯:找到目標節點,將前節點的 next 指向後節點,後節點的 pre 指向前節點。
  • PHP 物件參考特性:物件預設傳參考,靜態方法操作傳入的 $head 即操作原物件,無需傳回值。

應用場景

  • 瀏覽器歷史記錄(前進/後退)
  • 音樂播放清單(上一首/下一首)
  • LRU 快取淘汰演算法核心資料結構
  • 文字編輯器撤銷/重做堆疊

雖然 PHP 陣列功能強大,但理解鏈結串列等基礎資料結構,有助於解決特定效能問題與面試考核。

copyright © 萬盛學電腦網 all rights reserved