PHP 實現單向鏈表：節點類、順序插入、有序插入、刪除與更新

節點類設計

class Hero {
    public $no;      // 排名
    public $name;    // 名字
    public $next = null; // 指向下一個節點

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

    /** 遍歷輸出 */
    static public function showList($head) {
        $cur = $head;
        while ($cur->next !== null) {
            echo "排名：{$cur->next->no}，名字：{$cur->next->name}<br>";
            $cur = $cur->next;
        }
    }

    /** 尾部插入 */
    static public function addHero($head, $hero) {
        $cur = $head;
        while ($cur->next !== null) $cur = $cur->next;
        $cur->next = $hero;
    }

    /** 有序插入（按 no 升序） */
    static public function addHeroSorted($head, $hero) {
        $cur = $head;
        while ($cur->next !== null && $cur->next->no <= $hero->no) {
            $cur = $cur->next;
        }
        $hero->next = $cur->next;
        $cur->next = $hero;
    }

    /** 按 no 刪除 */
    static public function deleteHero($head, $no) {
        $cur = $head;
        while ($cur->next !== null && $cur->next->no != $no) {
            $cur = $cur->next;
        }
        if ($cur->next !== null) {
            $cur->next = $cur->next->next;
            echo "刪除成功<br>";
        } else {
            echo "未找到節點<br>";
        }
    }

    /** 按 no 更新 */
    static public function updateHero($head, $hero) {
        $cur = $head;
        while ($cur->next !== null && $cur->next->no != $hero->no) {
            $cur = $cur->next;
        }
        if ($cur->next !== null) {
            $hero->next = $cur->next->next;
            $cur->next = $hero;
            echo "更新成功<br>";
        } else {
            echo "未找到節點<br>";
        }
    }
}

使用演示

// 建立頭節點（不存數據）
$head = new Hero();

// 手動掛載第一個
$hero1 = new Hero(1, '111');
$head->next = $hero1;

// 尾部插入
$hero2 = new Hero(3, '333');
Hero::addHero($head, $hero2);

// 有序插入（插到 1 和 3 之間）
$hero3 = new Hero(2, '222');
Hero::addHeroSorted($head, $hero3);

Hero::showList($head);
// 排名：1，名字：111
// 排名：2，名字：222
// 排名：3，名字：333

// 刪除不存在
Hero::deleteHero($head, 4); // 未找到節點

// 更新排名 2 的名字
$hero4 = new Hero(2, 'xxx');
Hero::updateHero($head, $hero4);

Hero::showList($head);
// 排名：1，名字：111
// 排名：2，名字：xxx
// 排名：3，名字：333

鏈表核心概念回顧

• 頭節點：不存業務數據，統一入口，簡化邊界判斷
• 順序插入：O(n) 遍歷到尾部
• 有序插入：O(n) 遍歷找位置，調整指針
• 刪除/更新：O(n) 定位前驅節點，重鏈指針
• PHP 物件引用特性天然適合實現指針結構

擴展方向

• 雙向鏈表（添加 $prev）
• 循環鏈表（尾節點 next 指向頭）
• 泛型節點類（利用 PHP 8.1+ readonly、類型聲明）
• 實現 Iterator 接口，支持 foreach 遍歷

數據結構在 PHP 業務開發中雖少直接用，但理解其原理有助於設計高性能緩存、隊列、樹形菜單等底層組件。