php实现链表操作

PHP 实现链表的基本结构

链表是一种线性数据结构，由节点（Node）组成，每个节点包含数据和指向下一个节点的指针。在 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 insertAtPosition($data, $position) {
    if ($position < 0) {
        throw new Exception("Invalid position");
    }
    $newNode = new Node($data);
    if ($position === 0) {
        $newNode->next = $this->head;
        $this->head = $newNode;
        return;
    }
    $current = $this->head;
    for ($i = 0; $i < $position - 1 && $current !== null; $i++) {
        $current = $current->next;
    }
    if ($current === null) {
        throw new Exception("Position out of bounds");
    }
    $newNode->next = $current->next;
    $current->next = $newNode;
}

删除链表中的节点

删除操作可以根据节点值或位置进行。

根据值删除

public function deleteByValue($value) {
    if ($this->head === null) {
        return;
    }
    if ($this->head->data === $value) {
        $this->head = $this->head->next;
        return;
    }
    $current = $this->head;
    while ($current->next !== null && $current->next->data !== $value) {
        $current = $current->next;
    }
    if ($current->next !== null) {
        $current->next = $current->next->next;
    }
}

根据位置删除

public function deleteByPosition($position) {
    if ($position < 0 || $this->head === null) {
        throw new Exception("Invalid position");
    }
    if ($position === 0) {
        $this->head = $this->head->next;
        return;
    }
    $current = $this->head;
    for ($i = 0; $i < $position - 1 && $current !== null; $i++) {
        $current = $current->next;
    }
    if ($current === null || $current->next === null) {
        throw new Exception("Position out of bounds");
    }
    $current->next = $current->next->next;
}

遍历链表

遍历链表可以打印节点数据或查找特定值。

打印链表

public function printList() {
    $current = $this->head;
    while ($current !== null) {
        echo $current->data . " -> ";
        $current = $current->next;
    }
    echo "NULL\n";
}

查找节点

public function search($value) {
    $current = $this->head;
    while ($current !== null) {
        if ($current->data === $value) {
            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;
}

递归法

public function reverseRecursive($node) {
    if ($node === null || $node->next === null) {
        return $node;
    }
    $rest = $this->reverseRecursive($node->next);
    $node->next->next = $node;
    $node->next = null;
    return $rest;
}

链表长度计算

计算链表的长度可以通过遍历实现。

public function getLength() {
    $count = 0;
    $current = $this->head;
    while ($current !== null) {
        $count++;
        $current = $current->next;
    }
    return $count;
}

示例用法

以下是一个完整的示例，展示如何使用链表类。

$list = new LinkedList();
$list->insertAtTail(10);
$list->insertAtTail(20);
$list->insertAtHead(5);
$list->insertAtPosition(15, 2);
$list->printList(); // 输出: 5 -> 10 -> 15 -> 20 -> NULL

$list->deleteByValue(10);
$list->deleteByPosition(1);
$list->printList(); // 输出: 5 -> 20 -> NULL

$list->reverse();
$list->printList(); // 输出: 20 -> 5 -> NULL

echo "Length: " . $list->getLength(); // 输出: Length: 2