php实现链表

PHP 实现链表的基本结构

链表是一种线性数据结构，由节点（Node）组成，每个节点包含数据（data）和指向下一个节点的指针（next）。在 PHP 中，可以通过类和对象来实现链表。

class Node {
    public $data;
    public $next;

    public function __construct($data) {
        $this->data = $data;
        $this->next = null;
    }
}

class LinkedList {
    public $head;

    public function __construct() {
        $this->head = null;
    }
}

插入节点到链表

向链表中插入节点可以分为头部插入、尾部插入和中间插入。以下是头部插入和尾部插入的实现。

头部插入：

public function insertAtHead($data) {
    $newNode = new Node($data);
    $newNode->next = $this->head;
    $this->head = $newNode;
}

尾部插入：

public function insertAtTail($data) {
    $newNode = new Node($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 traverse() {
    $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->insertAtTail(1);
$list->insertAtTail(2);
$list->insertAtTail(3);
$list->traverse(); // 输出: 1 2 3

$list->insertAtHead(0);
$list->traverse(); // 输出: 0 1 2 3

$list->deleteNode(2);
$list->traverse(); // 输出: 0 1 3

$list->reverse();
$list->traverse(); // 输出: 3 1 0

通过以上代码，可以实现链表的基本操作，包括插入、删除、遍历、查找和反转。