php 链表实现

PHP 链表实现方法

链表是一种线性数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。以下是PHP中实现链表的方法。

定义链表节点类

链表的基本单位是节点，每个节点包含数据和指向下一个节点的指针。

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 isEmpty() {
        return $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->isEmpty()) {
        $this->head = $newNode;
    } else {
        $current = $this->head;
        while ($current->next !== null) {
            $current = $current->next;
        }
        $current->next = $newNode;
    }
}

删除链表中的节点

删除链表中第一个匹配的节点。

public function deleteNode($data) {
    if ($this->isEmpty()) {
        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 display() {
    $current = $this->head;
    while ($current !== null) {
        echo $current->data . " ";
        $current = $current->next;
    }
    echo "\n";
}

查找链表中的节点

检查链表中是否存在某个数据。

public function search($data) {
    $current = $this->head;
    while ($current !== null) {
        if ($current->data === $data) {
            return true;
        }
        $current = $current->next;
    }
    return false;
}

链表反转

反转链表中的所有节点。

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 = new LinkedList();
$list->insertAtHead(10);
$list->insertAtTail(20);
$list->insertAtTail(30);
$list->display(); // 输出: 10 20 30
$list->deleteNode(20);
$list->display(); // 输出: 10 30
$list->reverse();
$list->display(); // 输出: 30 10

以上代码展示了如何在PHP中实现链表的基本操作。可以根据需求扩展更多功能，如插入到指定位置、获取链表长度等。