php实现链表
PHP 实现链表的基本方法
链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。以下是 PHP 中实现链表的几种方式。
定义链表节点类
链表的基础是节点类，每个节点包含数据（data）和指向下一个节点的指针（next）。
class ListNode {
public $data;
public $next;
public function __construct($data) {
$this->data = $data;
$this->next = null;
}
}创建链表
可以通过实例化节点并链接它们来创建一个简单的链表。
$node1 = new ListNode(10);
$node2 = new ListNode(20);
$node3 = new ListNode(30);
$node1->next = $node2;
$node2->next = $node3;遍历链表
遍历链表通常从头部开始，依次访问每个节点，直到遇到 null。
function traverseLinkedList($head) {
$current = $head;
while ($current !== null) {
echo $current->data . " ";
$current = $current->next;
}
}
traverseLinkedList($node1); // 输出: 10 20 30插入节点
可以在链表的头部、中间或尾部插入节点。
头部插入
function insertAtHead(&$head, $data) {
$newNode = new ListNode($data);
$newNode->next = $head;
$head = $newNode;
}
insertAtHead($node1, 5);
traverseLinkedList($node1); // 输出: 5 10 20 30尾部插入
function insertAtTail($head, $data) {
$newNode = new ListNode($data);
$current = $head;
while ($current->next !== null) {
$current = $current->next;
}
$current->next = $newNode;
}
insertAtTail($node1, 40);
traverseLinkedList($node1); // 输出: 5 10 20 30 40删除节点
可以根据值或位置删除节点。
删除指定值的节点
function deleteNode(&$head, $value) {
if ($head->data === $value) {
$head = $head->next;
return;
}
$current = $head;
while ($current->next !== null && $current->next->data !== $value) {
$current = $current->next;
}
if ($current->next !== null) {
$current->next = $current->next->next;
}
}
deleteNode($node1, 20);
traverseLinkedList($node1); // 输出: 5 10 30 40反转链表
反转链表可以通过迭代或递归实现。
迭代法反转
function reverseLinkedList($head) {
$prev = null;
$current = $head;
while ($current !== null) {
$next = $current->next;
$current->next = $prev;
$prev = $current;
$current = $next;
}
return $prev;
}
$reversedHead = reverseLinkedList($node1);
traverseLinkedList($reversedHead); // 输出: 40 30 10 5链表的常见操作
其他常见操作包括查找节点、计算链表长度、检测环等。
查找节点
function findNode($head, $value) {
$current = $head;
while ($current !== null) {
if ($current->data === $value) {
return true;
}
$current = $current->next;
}
return false;
}
echo findNode($reversedHead, 30) ? "Found" : "Not found"; // 输出: Found计算链表长度
function getLength($head) {
$count = 0;
$current = $head;
while ($current !== null) {
$count++;
$current = $current->next;
}
return $count;
}
echo getLength($reversedHead); // 输出: 4双向链表的实现
双向链表每个节点包含指向前一个节点和后一个节点的指针。
class DoublyListNode {
public $data;
public $next;
public $prev;
public function __construct($data) {
$this->data = $data;
$this->next = null;
$this->prev = null;
}
}以上方法涵盖了链表的基本操作，可以根据需求进一步扩展功能。
