php链表实现
链表的基本概念
链表是一种线性数据结构，由节点（Node）组成，每个节点包含数据（data）和指向下一个节点的指针（next）。与数组不同，链表在内存中是非连续存储的，动态增删节点更高效。
单链表的PHP实现
定义节点类
链表的基础是节点，需定义一个Node类存储数据和指针：
class Node {
public $data;
public $next;
public function __construct($data) {
$this->data = $data;
$this->next = null;
}
}定义链表类
创建LinkedList类管理节点的增删查操作：
class LinkedList {
private $head;
public function __construct() {
$this->head = null;
}
}插入节点到链表头部
在链表头部插入新节点：
public function insertAtHead($data) {
$newNode = new Node($data);
$newNode->next = $this->head;
$this->head = $newNode;
}插入节点到链表尾部
遍历链表找到末尾节点并插入：
public function insertAtTail($data) {
$newNode = new Node($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";
}双向链表的扩展实现
双向链表的节点包含前驱（prev）和后继（next）指针：
class DoublyNode {
public $data;
public $prev;
public $next;
public function __construct($data) {
$this->data = $data;
$this->prev = null;
$this->next = null;
}
}双向链表的插入与删除
需同时维护prev和next指针，确保逻辑一致。
应用示例
$list = new LinkedList();
$list->insertAtHead(3);
$list->insertAtTail(5);
$list->insertAtHead(1);
$list->printList(); // 输出: 1 -> 3 -> 5 -> NULL
$list->deleteNode(3);
$list->printList(); // 输出: 1 -> 5 -> NULL通过上述实现，可完成链表的创建、插入、删除和遍历操作。实际应用中可根据需求扩展更多功能，如反转链表、检测环等。
