PHP 實現雙向鏈表：從數據結構原理到面向對象封裝的完整教程

雙向鏈表核心概念

雙向鏈表每個節點包含三域：

• data：數據域
• prev：指向前驅節點的指针（引用）
• next：指向後繼節點的指针

特點：

• 雙向遍歷：正向 next、反向 prev
• 插入/刪除 O(1)（已知節點引用），無需移動數組元素
• 內存非連續，動態分配，無容量上限（受限於記憶體）
• 額外空間開銷：每節點 2 個引用（64 位系統 16 字節）

節點類封裝

<?php
class DoublyListNode {
    public mixed $data;
    public ?DoublyListNode $prev = null;
    public ?DoublyListNode $next = null;

    public function __construct(mixed $data = null) {
        $this->data = $data;
    }

    // 斷開自身引用，協助 GC
    public function detach(): void {
        $this->prev = $this->next = null;
    }
}

鏈表類核心操作

class DoublyLinkedList {
    private DoublyListNode $head; // 哨兵節點（哑節點），不存儲數據
    private int $count = 0;

    public function __construct() {
        $this->head = new DoublyListNode();
        $this->head->prev = $this->head->next = $this->head; // 空表自我循環
    }

    // 獲取長度 O(1)
    public function count(): int {
        return $this->count;
    }

    // 判空
    public function isEmpty(): bool {
        return $this->count === 0;
    }

    // 尾部插入 O(1)
    public function push(mixed $data): self {
        return $this->insertBefore($this->head, $data);
    }

    // 頭部插入 O(1)
    public function unshift(mixed $data): self {
        return $this->insertAfter($this->head, $data);
    }

    // 任意節點前插入 O(1)
    public function insertBefore(DoublyListNode $target, mixed $data): self {
        $node = new DoublyListNode($data);
        $prev = $target->prev;
        $node->prev = $prev;
        $node->next = $target;
        $prev->next = $node;
        $target->prev = $node;
        $this->count++;
        return $this;
    }

    // 任意節點後插入 O(1)
    public function insertAfter(DoublyListNode $target, mixed $data): self {
        $node = new DoublyListNode($data);
        $next = $target->next;
        $node->next = $next;
        $node->prev = $target;
        $target->next = $node;
        $next->prev = $node;
        $this->count++;
        return $this;
    }

    // 刪除指定節點 O(1)
    public function remove(DoublyListNode $node): mixed {
        if ($node === $this->head) throw new InvalidArgumentException('Cannot remove sentinel');
        $prev = $node->prev;
        $next = $node->next;
        $prev->next = $next;
        $next->prev = $prev;
        $data = $node->data;
        $node->detach();
        $this->count--;
        return $data;
    }

    // 彈出尾部 O(1)
    public function pop(): mixed|null {
        if ($this->isEmpty()) return null;
        return $this->remove($this->head->prev);
    }

    // 彈出頭部 O(1)
    public function shift(): mixed|null {
        if ($this->isEmpty()) return null;
        return $this->remove($this->head->next);
    }

    // 正向迭代器
    public function getIterator(): Iterator {
        $current = $this->head->next;
        while ($current !== $this->head) {
            yield $current->data;
            $current = $current->next;
        }
    }

    // 反向迭代器
    public function getReverseIterator(): Iterator {
        $current = $this->head->prev;
        while ($current !== $this->head) {
            yield $current->data;
            $current = $current->prev;
        }
    }

    // 查找首個匹配節點 O(n)
    public function find(callable $predicate): ?DoublyListNode {
        $current = $this->head->next;
        while ($current !== $this->head) {
            if ($predicate($current->data)) return $current;
            $current = $current->next;
        }
        return null;
    }

    // 轉數組（調試用）
    public function toArray(): array {
        return iterator_to_array($this->getIterator());
    }
}

有序插入示例：按編號排序

原文代碼邏輯：遍歷找到第一個 next->no > hero->no 的位置插入。使用封裝後：

$list = new DoublyLinkedList();

// 定義英雄數據類
class Hero {
    public int $no;
    public string $name;
    public function __construct(int $no, string $name) {
        $this->no = $no;
        $this->name = $name;
    }
}

// 有序插入邏輯
function insertHeroSorted(DoublyLinkedList $list, Hero $hero): void {
    $current = $list->getHead()->next; // 需暴露 head 或提供遍歷鉤子
    // 為了演示，假設 DoublyLinkedList 暴露 head 屬性或提供 findInsertPosition
    // 這裡簡化：轉數組排序後重建（教學用），實際應直接操作節點
    $arr = $list->toArray();
    $arr[] = $hero;
    usort($arr, fn($a, $b) => $a->no <=> $b->no);
    $list->clear();
    foreach ($arr as $h) $list->push($h);
}

// 更優雅：在 DoublyLinkedList 中添加有序插入方法
public function insertSorted(mixed $data, callable $compare): self {
    $current = $this->head->next;
    while ($current !== $this->head) {
        if ($compare($data, $current->data) < 0) {
            return $this->insertBefore($current, $data);
        }
        $current = $current->next;
    }
    return $this->push($data); // 最大，插尾部
}

// 使用
$list->insertSorted(new Hero(1, '1111'), fn($a, $b) => $a->no <=> $b->no);
$list->insertSorted(new Hero(3, '3333'), fn($a, $b) => $a->no <=> $b->no);
$list->insertSorted(new Hero(2, '2222'), fn($a, $b) => $a->no <=> $b->no);

foreach ($list->getIterator() as $hero) {
    echo "編號：{$hero->no} 名字：{$hero->name}\n";
}
// 輸出：1-1111, 2-2222, 3-3333

刪除操作演示

// 刪除編號為 2 的節點
$node = $list->find(fn($hero) => $hero->no === 2);
if ($node) {
    $list->remove($node);
    echo "刪除成功\n";
} else {
    echo "未找到\n";
}

foreach ($list->getIterator() as $hero) {
    echo "編號：{$hero->no} 名字：{$hero->name}\n";
}
// 輸出：1-1111, 3-3333

內存管理與 GC 考量

• PHP 使用引用計數 + 週期檢測 GC。雙向鏈表形成循環引用（prev ↔ next），**必須在刪除節點時手動斷開引用**（$node->detach()），否則孤立子圖需等待週期 GC 回收，造成內存洩漏假象。
• 哨兵節點 $head 自我循環，屬於有意循環，不影響。
• 大量節點頻繁增刪場景，建議定期 gc_collect_cycles() 或升級 PHP 8.1+（增量 GC 改進）。

性能對比：鏈表 vs 數組

實際應用場景

1. LRU 緩存淘汰：get 移至頭部，put 滿容量刪尾部，O(1) 所有操作。
2. 瀏覽器歷史前進/後退：雙向遍歷天然契合。
3. 文本編輯器撤銷/重做：雙棧或雙向鏈表維護狀態序列。
4. 事件總線訂閱者列表：頻繁增刪訂閱，遍歷分發。
5. 大數據分頁游標：雙向鏈表維護當前頁前後鄰居，避免 OFFSET 深分頁。

現代 PHP 替代方案

• SplDoublyLinkedList：PHP 5.3+ 內建 C 實現，支援 Iterator、ArrayAccess、Countable、push/pop/shift/unshift/add/remove，性能遠超用戶態實現，**生產環境首選**。
• Ds\Deque：pecl install ds，雙端佇列，底層連續內存塊，隨機訪問 O(1)，記憶體效率高。

// SplDoublyLinkedList 使用示例
$list = new SplDoublyLinkedList();
$list->push('a');
$list->push('b');
$list->unshift('c'); // c, a, b
$list->add(1, 'x');  // c, x, a, b
echo $list->count(); // 4
foreach ($list as $v) echo $v . ' '; // c x a b
$list->rewind(); // 重置指針
while ($list->valid()) {
    echo $list->current();
    $list->next();
}

理解雙向鏈表原理是計算機科學基礎功，手寫實現能深化對指针、引用、內存管理、迭代器模式的認知。但**生產代碼請直接使用 SplDoublyLinkedList 或 Ds\Deque**，它們經過嚴格測試、C 級性能、標準介面、無需維護。將手寫版作為教學、面試、遞歸/指针思維訓練的載體，而非復制粘貼進項目。