萬盛學電腦網

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

PHP 實現雙向鏈表數據結構完整教程

節點類設計

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

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

鏈表操作類(靜態方法)

class DoubleLinkedList {
    /** 尾部追加(按 no 升序插入) */
    public static function addHero($head, Hero $hero) {
        $cur = $head;
        if ($cur->next === null) { // 空鏈表
            $cur->next = $hero;
            $hero->prev = $cur;
            return;
        }

        // 尋找插入位置
        while ($cur->next !== null) {
            if ($cur->next->no > $hero->no) break;
            if ($cur->next->no === $hero->no) {
                echo "編號 {$hero->no} 已存在\n";
                return;
            }
            $cur = $cur->next;
        }

        // 插入節點
        $hero->next = $cur->next;
        $hero->prev = $cur;
        if ($cur->next !== null) {
            $cur->next->prev = $hero;
        }
        $cur->next = $hero;
    }

    /** 刪除節點 */
    public static function deleteHero($head, $no) {
        $cur = $head->next;
        while ($cur !== null) {
            if ($cur->no === $no) {
                $cur->prev->next = $cur->next;
                if ($cur->next !== null) {
                    $cur->next->prev = $cur->prev;
                }
                unset($cur);
                return true;
            }
            $cur = $cur->next;
        }
        return false;
    }

    /** 正向遍歷輸出 */
    public static function showHero($head) {
        $cur = $head->next;
        while ($cur !== null) {
            echo "No: {$cur->no}, Name: {$cur->name}\n";
            $cur = $cur->next;
        }
    }

    /** 反向遍歷輸出 */
    public static function showHeroReverse($head) {
        // 先走到尾節點
        $cur = $head;
        while ($cur->next !== null) $cur = $cur->next;
        // 反向走
        while ($cur !== $head) {
            echo "No: {$cur->no}, Name: {$cur->name}\n";
            $cur = $cur->prev;
        }
    }
}

使用示例

$head = new Hero(); // 頭節點,不存數據

DoubleLinkedList::addHero($head, new Hero(3, '張三'));
DoubleLinkedList::addHero($head, new Hero(1, '李四'));
DoubleLinkedList::addHero($head, new Hero(2, '王五'));

echo "正向:\n";
DoubleLinkedList::showHero($head);
// No: 1, Name: 李四
// No: 2, Name: 王五
// No: 3, Name: 張三

echo "反向:\n";
DoubleLinkedList::showHeroReverse($head);
// No: 3, Name: 張三
// No: 2, Name: 王五
// No: 1, Name: 李四

DoubleLinkedList::deleteHero($head, 2);
DoubleLinkedList::showHero($head);
// No: 1, Name: 李四
// No: 3, Name: 張三

教學意義

  • 理解指鏈表指針操作:prev、next 相互維護。
  • 頭節點哨兵模式簡化邊界判斷(無需單獨處理頭插/尾刪)。
  • PHP 對象引用天然模擬指針,適合演示數據結構。
  • 實際項目中大量數據請使用數組或資料庫,鏈表僅供教學/特定場景(如 LRU 緩存)。
copyright © 萬盛學電腦網 all rights reserved