php 实现单链表
单链表的基本概念
单链表是一种线性数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表的第一个节点称为头节点，最后一个节点的指针指向NULL。
单链表的节点定义
在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)，因为需要为每个节点分配内存。
- 链表适合频繁的插入和删除操作，但随机访问效率较低。
