PHP 單向鏈結串列實作教學：節點操作、插入、刪除、遍歷完整代碼

資料結構基礎

單向鏈結串列由節點組成，每個節點包含 資料 與 指向下一個節點的指標。PHP 雖無原生指標，但物件預設為參考傳遞，可直接模擬指標行為。

節點類別定義

class Node {
    private $id;
    public $name;
    public $next = null;

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

    // 取得私有 id（示範封裝）
    public function getId() { return $this->id; }
}

核心操作靜態方法

採用虛擬頭節點簡化邊界條件：$head 本身不存資料，$head->next 指向第一個真實節點。

遍歷列印

static public function show($head) {
    $cur = $head;
    while ($cur->next) {
        echo $cur->next->id . '###' . $cur->next->name . "
\n";
        $cur = $cur->next;
    }
    echo "
\n";
}

尾插法

static public function push($head, $node) {
    $cur = $head;
    while ($cur->next !== null) {
        $cur = $cur->next;
    }
    $cur->next = $node;
    return $head;
}

依 ID 排序插入

static public function insert($head, $node) {
    $cur = $head;
    while ($cur->next !== null) {
        if ($cur->next->id > $node->id) break;
        $cur = $cur->next;
    }
    $node->next = $cur->next;
    $cur->next = $node;
    return $head;
}

修改節點資料

static public function edit($head, $node) {
    $cur = $head;
    while ($cur->next !== null) {
        if ($cur->next->id == $node->id) break;
        $cur = $cur->next;
    }
    if ($cur->next !== null) {
        $cur->next->name = $node->name;
    }
    return $head;
}

刪除節點

static public function pop($head, $node) {
    $cur = $head;
    while ($cur->next !== null) {
        if ($cur->next === $node) break;
        $cur = $cur->next;
    }
    if ($cur->next !== null) {
        $cur->next = $node->next;
    }
    return $head;
}

實際測試流程

$head = new Node(); // 虛擬頭節點

$n1 = new Node(1, '唐三藏'); Node::push($head, $n1);
$n1->name = '唐僧';          // 物件參考傳遞，直接修改生效
Node::show($head);

$n2 = new Node(2, '孫悟空'); Node::insert($head, $n2);
$n3 = new Node(5, '白龍馬'); Node::push($head, $n3);
$n4 = new Node(3, '豬八戒'); Node::insert($head, $n4);
$n5 = new Node(4, '沙和尚'); Node::insert($head, $n5);

$n4->name = '豬悟能'; // 同樣直接修改
Node::pop($head, $n1); // 刪除第一個節點
Node::show($head);

輸出結果預期

1###唐僧
2###孫悟空
3###豬八戒
4###沙和尚
5###白龍馬
---
2###孫悟空
3###豬悟能
4###沙和尚
5###白龍馬
---

關鍵觀念總結

• 虛擬頭節點：統一插入/刪除邏輯，無需特判第一個節點
• 物件參考傳遞：$n1->name = '新名' 直接影響鏈結串列內節點，無需額外 edit 呼叫
• 記憶體管理：PHP 自動 GC，斷開指標（$cur->next = $node->next）後無引用的節點會被回收
• 擴充性：可加入 findById、reverse、toArray 等工具方法