php实现链表
链表的基本概念
链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表在内存中是非连续存储的，动态增删节点更高效。
单链表实现
PHP中可以通过类实现单链表。节点类包含数据（data）和指向下一个节点的指针（next），链表类提供插入、删除等操作方法。
class ListNode {
public $data;
public $next;
public function __construct($data) {
$this->data = $data;
$this->next = null;
}
}
class LinkedList {
public $head;
public function __construct() {
$this->head = null;
}
// 在链表头部插入节点
public function insertAtHead($data) {
$newNode = new ListNode($data);
$newNode->next = $this->head;
$this->head = $newNode;
}
// 在链表尾部插入节点
public function insertAtTail($data) {
$newNode = new ListNode($data);
if ($this->head === null) {
$this->head = $newNode;
return;
}
$current = $this->head;
while ($current->next !== null) {
$current = $current->next;
}
$current->next = $newNode;
}
// 删除指定值的节点
public function deleteNode($data) {
if ($this->head === null) return;
if ($this->head->data === $data) {
$this->head = $this->head->next;
return;
}
$current = $this->head;
while ($current->next !== null && $current->next->data !== $data) {
$current = $current->next;
}
if ($current->next !== null) {
$current->next = $current->next->next;
}
}
// 打印链表
public function printList() {
$current = $this->head;
while ($current !== null) {
echo $current->data . " -> ";
$current = $current->next;
}
echo "NULL\n";
}
}
// 使用示例
$list = new LinkedList();
$list->insertAtHead(3);
$list->insertAtHead(2);
$list->insertAtHead(1);
$list->insertAtTail(4);
$list->printList(); // 输出: 1 -> 2 -> 3 -> 4 -> NULL
$list->deleteNode(2);
$list->printList(); // 输出: 1 -> 3 -> 4 -> NULL双向链表实现
双向链表的节点包含指向前驱和后继的指针，支持双向遍历。实现时需额外维护prev指针。
class DoublyListNode {
public $data;
public $prev;
public $next;
public function __construct($data) {
$this->data = $data;
$this->prev = null;
$this->next = null;
}
}
class DoublyLinkedList {
public $head;
public function __construct() {
$this->head = null;
}
// 在尾部插入节点
public function insertAtTail($data) {
$newNode = new DoublyListNode($data);
if ($this->head === null) {
$this->head = $newNode;
return;
}
$current = $this->head;
while ($current->next !== null) {
$current = $current->next;
}
$current->next = $newNode;
$newNode->prev = $current;
}
// 打印链表（正向）
public function printForward() {
$current = $this->head;
while ($current !== null) {
echo $current->data . " <-> ";
$current = $current->next;
}
echo "NULL\n";
}
}
// 使用示例
$dll = new DoublyLinkedList();
$dll->insertAtTail(1);
$dll->insertAtTail(2);
$dll->printForward(); // 输出: 1 <-> 2 <-> NULL链表操作注意事项
- 内存管理：PHP自动处理垃圾回收，但需注意避免循环引用（尤其在双向链表中）。
- 边界条件：处理空链表、头节点或尾节点时需特殊判断。
- 时间复杂度：插入/删除头节点为O(1)，而尾部操作需遍历为O(n)。
通过上述实现，可灵活扩展链表功能（如反转、检测环等），适应不同场景需求。
