php实现链表
PHP 实现链表的基本方法
链表是一种线性数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。PHP 中可以通过类来实现链表结构。
定义链表节点类
class ListNode {
public $data = null;
public $next = null;
public function __construct($data) {
$this->data = $data;
}
}实现链表类
class LinkedList {
private $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 $current;
}
$current = $current->next;
}
return null;
}
// 打印链表
public function display() {
$current = $this->head;
while ($current !== null) {
echo $current->data . " ";
$current = $current->next;
}
echo "\n";
}
}使用链表
$list = new LinkedList();
$list->insert(10);
$list->insert(20);
$list->insert(30);
$list->display(); // 输出: 10 20 30
$list->delete(20);
$list->display(); // 输出: 10 30
$node = $list->search(30);
if ($node !== null) {
echo "Found: " . $node->data . "\n"; // 输出: Found: 30
}实现双向链表
双向链表节点包含指向前一个和后一个节点的指针：
class DoublyListNode {
public $data = null;
public $prev = null;
public $next = null;
public function __construct($data) {
$this->data = $data;
}
}
class DoublyLinkedList {
private $head = null;
private $tail = null;
// 插入节点到末尾
public function insert($data) {
$newNode = new DoublyListNode($data);
if ($this->head === null) {
$this->head = $newNode;
$this->tail = $newNode;
} else {
$newNode->prev = $this->tail;
$this->tail->next = $newNode;
$this->tail = $newNode;
}
}
// 其他方法类似，需要处理prev指针
}链表操作的时间复杂度
- 插入/删除头节点：O(1)
- 插入/删除尾节点：O(1)（双向链表）或 O(n)（单向链表）
- 查找元素：O(n)
- 访问第n个元素：O(n)
PHP 的数组实际上是有序哈希表，在大多数情况下比链表更高效。链表主要用于需要频繁插入/删除的场景，或者作为更复杂数据结构的基础。
