php 实现链表
PHP 实现链表的方法
链表是一种线性数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。PHP 中可以通过类和对象来实现链表。
定义链表节点类
创建一个 ListNode 类，用于表示链表的节点。每个节点包含 data 和 next 属性。
class ListNode {
public $data = null;
public $next = null;
public function __construct($data) {
$this->data = $data;
}
}定义链表类
创建一个 LinkedList 类，用于管理链表操作。包含 head 属性表示链表的头部节点。
class LinkedList {
public $head = null;
// 插入节点到链表尾部
public function insert($data) {
$newNode = new ListNode($data);
if ($this->head === null) {
$this->head = $newNode;
} else {
$current = $this->head;
while ($current->next !== null) {
$current = $current->next;
}
$current->next = $newNode;
}
}
// 删除指定数据的节点
public function delete($data) {
if ($this->head === null) {
return;
}
if ($this->head->data === $data) {
$this->head = $this->head->next;
return;
}
$current = $this->head;
while ($current->next !== null) {
if ($current->next->data === $data) {
$current->next = $current->next->next;
return;
}
$current = $current->next;
}
}
// 查找节点
public function search($data) {
$current = $this->head;
while ($current !== null) {
if ($current->data === $data) {
return true;
}
$current = $current->next;
}
return false;
}
// 打印链表
public function display() {
$current = $this->head;
while ($current !== null) {
echo $current->data . " -> ";
$current = $current->next;
}
echo "NULL\n";
}
}使用链表
创建一个链表实例，并执行插入、删除、查找和打印操作。
$list = new LinkedList();
$list->insert(10);
$list->insert(20);
$list->insert(30);
$list->display(); // 输出: 10 -> 20 -> 30 -> NULL
$list->delete(20);
$list->display(); // 输出: 10 -> 30 -> NULL
echo $list->search(30) ? "Found\n" : "Not found\n"; // 输出: Found实现链表反转
在 LinkedList 类中添加反转链表的方法。
public function reverse() {
$prev = null;
$current = $this->head;
while ($current !== null) {
$next = $current->next;
$current->next = $prev;
$prev = $current;
$current = $next;
}
$this->head = $prev;
}调用反转方法后打印链表：
$list->reverse();
$list->display(); // 输出: 30 -> 10 -> NULL链表的时间复杂度
- 插入操作：O(n)（需要遍历到链表尾部）
- 删除操作：O(n)（需要遍历找到目标节点）
- 查找操作：O(n)（需要遍历链表）
- 反转操作：O(n)（需要遍历整个链表）
通过以上方法，可以在 PHP 中实现链表的基本操作。链表适用于动态数据管理，插入和删除操作效率较高。
