php 实现单链表
单链表的基本概念
单链表是一种线性数据结构，由节点组成，每个节点包含数据域和指向下一个节点的指针域。链表的头节点是访问整个链表的入口。
单链表的节点类实现
在PHP中，可以通过类来定义链表节点。每个节点包含数据（data）和指向下一个节点的指针（next）。
class ListNode {
public $data;
public $next;
public function __construct($data) {
$this->data = $data;
$this->next = null;
}
}单链表的操作类实现
单链表的操作包括插入、删除、遍历等。以下是一个单链表操作类的实现示例：
class LinkedList {
private $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(10);
$list->insertAtHead(20);
$list->insertAtTail(30);
$list->printList(); // 输出: 20 -> 10 -> 30 -> NULL
$list->deleteNode(10);
$list->printList(); // 输出: 20 -> 30 -> NULL注意事项
- 链表的操作需要注意空指针问题，尤其是在删除和插入节点时。
- 链表的时间复杂度：插入和删除操作在头部为O(1)，在尾部为O(n)；查找操作为O(n)。
- 链表适用于频繁插入和删除的场景，但随机访问效率较低。
通过上述实现，可以完成单链表的基本操作。根据实际需求，可以进一步扩展功能，如反转链表、检测环等。
