節點類設計
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 緩存)。