PHP 實現單向鏈表：節點類別、尾插、有序插入、修改、刪除、遍歷完整範例

前言

PHP 陣列本質是有序映射，非傳統連續記憶體陣列。理解鏈表結構有助於掌握指標/引用操作、資料結構原理。本文實現單向鏈表核心操作。

節點類別設計

<?php
class ListNode
{
    public $id;
    public $name;
    public $next = null;

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

鏈表操作靜態類別

<?php
class LinkedList
{
    /** 建立頭節點（哨兵節點，不存資料） */
    public static function createHead()
    {
        return new ListNode();
    }

    /** 尾插法：O(n) */
    public static function push(ListNode $head, ListNode $node)
    {
        $cur = $head;
        while ($cur->next !== null) {
            $cur = $cur->next;
        }
        $cur->next = $node;
        return $head;
    }

    /** 有序插入（依 id 升序）：O(n) */
    public static function insertSorted(ListNode $head, ListNode $node)
    {
        $cur = $head;
        while ($cur->next !== null && $cur->next->id < $node->id) {
            $cur = $cur->next;
        }
        $node->next = $cur->next;
        $cur->next = $node;
        return $head;
    }

    /** 修改節點資料：O(n) */
    public static function update(ListNode $head, $id, $newName)
    {
        $cur = $head->next;
        while ($cur !== null) {
            if ($cur->id == $id) {
                $cur->name = $newName;
                return true;
            }
            $cur = $cur->next;
        }
        return false;
    }

    /** 刪除節點：O(n) */
    public static function delete(ListNode $head, $id)
    {
        $cur = $head;
        while ($cur->next !== null) {
            if ($cur->next->id == $id) {
                $cur->next = $cur->next->next;
                return true;
            }
            $cur = $cur->next;
        }
        return false;
    }

    /** 遍歷輸出 */
    public static function traverse(ListNode $head)
    {
        $cur = $head->next;
        while ($cur !== null) {
            echo "ID: {$cur->id}, Name: {$cur->name}\n";
            $cur = $cur->next;
        }
        echo "---\n";
    }

    /** 取得長度 */
    public static function length(ListNode $head)
    {
        $count = 0;
        $cur = $head->next;
        while ($cur !== null) {
            $count++;
            $cur = $cur->next;
        }
        return $count;
    }

    /** 查找節點 */
    public static function find(ListNode $head, $id)
    {
        $cur = $head->next;
        while ($cur !== null) {
            if ($cur->id == $id) return $cur;
            $cur = $cur->next;
        }
        return null;
    }
}

使用範例

<?php
require 'ListNode.php';
require 'LinkedList.php';

$head = LinkedList::createHead();

// 尾插
LinkedList::push($head, new ListNode(1, '唐三藏'));
LinkedList::push($head, new ListNode(5, '白龍馬'));

// 有序插入
LinkedList::insertSorted($head, new ListNode(2, '孫悟空'));
LinkedList::insertSorted($head, new ListNode(3, '豬八戒'));
LinkedList::insertSorted($head, new ListNode(4, '沙和尚'));

echo "初始列表:\n";
LinkedList::traverse($head);

// 修改
LinkedList::update($head, 3, '豬悟能');
echo "修改 ID=3 後:\n";
LinkedList::traverse($head);

// 刪除
LinkedList::delete($head, 1);
echo "刪除 ID=1 後:\n";
LinkedList::traverse($head);

// 查找
$node = LinkedList::find($head, 4);
echo "查找 ID=4: " . ($node ? $node->name : '不存在') . "\n";

echo "長度: " . LinkedList::length($head) . "\n";

執行結果

初始列表:
ID: 1, Name: 唐三藏
ID: 2, Name: 孫悟空
ID: 3, Name: 豬八戒
ID: 4, Name: 沙和尚
ID: 5, Name: 白龍馬
---
修改 ID=3 後:
ID: 1, Name: 唐三藏
ID: 2, Name: 孫悟空
ID: 3, Name: 豬悟能
ID: 4, Name: 沙和尚
ID: 5, Name: 白龍馬
---
刪除 ID=1 後:
ID: 2, Name: 孫悟空
ID: 3, Name: 豬悟能
ID: 4, Name: 沙和尚
ID: 5, Name: 白龍馬
---
查找 ID=4: 沙和尚
長度: 4

複雜度與 PHP 實現注意事項

擴展方向

• 雙向鏈表：新增 $prev 指標，支援反向遍歷、O(1) 刪除已知節點。
• 循環鏈表：尾節點 next 指向頭節點，適用於輪詢排程。
• 跳表：多層索引加速查找至 O(log n)，Redis 有序集合底層結構。
• 佇列/棧：鏈表實現 enqueue/dequeue、push/pop。

總結

PHP 實現鏈表雖非實務常見（陣列效能更優），但能深化對**引用語意、記憶體模型、演算法複雜度**的理解。哨兵頭節點統一邊界條件，物件引用特性簡化指標操作，是教學與面試常考核心。