雙向鏈結串列每個節點同時擁有指向前一個與下一個節點的指標,支援雙向遍歷、高效插入刪除。本文提供完整 PHP 實作,包含節點類別、依編號排序插入、刪除、遍歷列印功能。
class Hero {
public $no;
public $name;
public $next = null;
public $pre = null;
public function __construct($no, $name) {
$this->no = $no;
$this->name = $name;
}
// 靜態方法:依編號升序插入
static public function addHero($head, $hero) {
$cur = $head;
$isExist = false;
// 空鏈表
if ($cur->next == null) {
$cur->next = $hero;
$hero->pre = $cur;
return;
}
// 尋找插入位置
while ($cur->next != null) {
if ($cur->next->no > $hero->no) break;
if ($cur->next->no == $hero->no) {
$isExist = true;
echo "不能新增相同編號\n";
break;
}
$cur = $cur->next;
}
if (!$isExist) {
if ($cur->next != null) {
$hero->next = $cur->next;
$hero->next->pre = $hero;
}
$hero->pre = $cur;
$cur->next = $hero;
}
}
// 遍歷列印
static public function showHero($head) {
$cur = $head;
while ($cur->next != null) {
echo "編號:{$cur->next->no} 名字:{$cur->next->name}\n";
$cur = $cur->next;
}
}
// 依編號刪除
static public function delHero($head, $herono) {
$cur = $head;
$isFind = false;
while ($cur != null) {
if ($cur->no == $herono) {
$isFind = true;
break;
}
$cur = $cur->next;
}
if ($isFind) {
if ($cur->next != null) {
$cur->next->pre = $cur->pre;
}
$cur->pre->next = $cur->next;
} else {
echo "沒有找到目標\n";
}
}
}
$head = new Hero(0, 'head'); // 頭節點(哨兵)
$hero1 = new Hero(1, '1111');
$hero3 = new Hero(3, '3333');
$hero2 = new Hero(2, '2222');
Hero::addHero($head, $hero1);
Hero::addHero($head, $hero3);
Hero::addHero($head, $hero2);
Hero::showHero($head);
// 輸出:
// 編號:1 名字:1111
// 編號:2 名字:2222
// 編號:3 名字:3333
Hero::delHero($head, 2);
Hero::showHero($head);
// 輸出:
// 編號:1 名字:1111
// 編號:3 名字:3333
$head 不存放資料,僅作為鏈表起始標記,簡化邊界判斷。next->no > 新節點no 的位置,調整四個指標(新節點的 pre/next、前後節點的 next/pre)。$head 即操作原物件,無需傳回值。雖然 PHP 陣列功能強大,但理解鏈結串列等基礎資料結構,有助於解決特定效能問題與面試考核。