php实现双向链表
双向链表的基本概念
双向链表是一种线性数据结构，每个节点包含两个指针：一个指向前驱节点（prev），一个指向后继节点（next）。与单向链表相比，双向链表支持双向遍历，但需要更多内存存储指针。
PHP实现双向链表的步骤
定义节点类
创建一个Node类表示链表节点，包含数据属性（data）和前后指针（prev、next）：
class Node {
public $data;
public $prev;
public $next;
public function __construct($data) {
$this->data = $data;
$this->prev = null;
$this->next = null;
}
}定义双向链表类
实现双向链表的常用操作（插入、删除、遍历等）：
class DoublyLinkedList {
private $head;
private $tail;
public function __construct() {
$this->head = null;
$this->tail = null;
}
// 在链表尾部插入节点
public function append($data) {
$newNode = new Node($data);
if ($this->head === null) {
$this->head = $newNode;
$this->tail = $newNode;
} else {
$newNode->prev = $this->tail;
$this->tail->next = $newNode;
$this->tail = $newNode;
}
}
// 在链表头部插入节点
public function prepend($data) {
$newNode = new Node($data);
if ($this->head === null) {
$this->head = $newNode;
$this->tail = $newNode;
} else {
$newNode->next = $this->head;
$this->head->prev = $newNode;
$this->head = $newNode;
}
}
// 删除指定值的节点
public function delete($data) {
$current = $this->head;
while ($current !== null) {
if ($current->data === $data) {
if ($current->prev !== null) {
$current->prev->next = $current->next;
} else {
$this->head = $current->next;
}
if ($current->next !== null) {
$current->next->prev = $current->prev;
} else {
$this->tail = $current->prev;
}
return true;
}
$current = $current->next;
}
return false;
}
// 正向遍历链表
public function traverseForward() {
$current = $this->head;
while ($current !== null) {
echo $current->data . " ";
$current = $current->next;
}
echo PHP_EOL;
}
// 反向遍历链表
public function traverseBackward() {
$current = $this->tail;
while ($current !== null) {
echo $current->data . " ";
$current = $current->prev;
}
echo PHP_EOL;
}
}使用示例
$dll = new DoublyLinkedList();
$dll->append(10); // 尾部插入
$dll->append(20);
$dll->prepend(5); // 头部插入
$dll->traverseForward(); // 输出: 5 10 20
$dll->traverseBackward(); // 输出: 20 10 5
$dll->delete(10); // 删除节点
$dll->traverseForward(); // 输出: 5 20关键点说明
- 头尾指针：
head和tail分别指向链表的首尾节点，简化插入和删除操作。 - 边界处理：插入或删除节点时需检查是否为头节点或尾节点，避免空指针异常。
- 时间复杂度：
- 插入/删除头部或尾部节点：O(1)
- 删除中间节点：O(n)（需遍历查找）。
通过上述实现，可以灵活操作双向链表，适用于需要频繁双向遍历的场景。
