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 insertAtBeginning($data) {
        $newNode = new ListNode($data);
        $newNode->next = $this->head;
        $this->head = $newNode;
    }

    // 在链表尾部插入节点
    public function insertAtEnd($data) {
        $newNode = new ListNode($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 printList() {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " ";
            $current = $current->next;
        }
        echo "\n";
    }
}

使用链表类

创建链表实例并进行操作。

$list = new LinkedList();
$list->insertAtEnd(10);
$list->insertAtEnd(20);
$list->insertAtBeginning(5);
$list->printList(); // 输出: 5 10 20

$list->deleteNode(10);
$list->printList(); // 输出: 5 20

双向链表的实现

双向链表每个节点包含指向前一个和后一个节点的指针。

class DoublyListNode {
    public $data;
    public $next;
    public $prev;

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

class DoublyLinkedList {
    private $head;
    private $tail;

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

    // 在头部插入节点
    public function insertAtBeginning($data) {
        $newNode = new DoublyListNode($data);
        if ($this->head === null) {
            $this->head = $newNode;
            $this->tail = $newNode;
        } else {
            $newNode->next = $this->head;
            $this->head->prev = $newNode;
            $this->head = $newNode;
        }
    }

    // 在尾部插入节点
    public function insertAtEnd($data) {
        $newNode = new DoublyListNode($data);
        if ($this->tail === null) {
            $this->head = $newNode;
            $this->tail = $newNode;
        } else {
            $newNode->prev = $this->tail;
            $this->tail->next = $newNode;
            $this->tail = $newNode;
        }
    }

    // 打印链表数据
    public function printList() {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " ";
            $current = $current->next;
        }
        echo "\n";
    }
}

链表的高级操作

链表可以支持更复杂的操作，如反转链表或检测环。

// 反转链表
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 hasCycle() {
    if ($this->head === null) {
        return false;
    }
    $slow = $this->head;
    $fast = $this->head;
    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
        if ($slow === $fast) {
            return true;
        }
    }
    return false;
}

通过以上方法，可以在 PHP 中实现基本的链表操作，包括单向链表和双向链表。链表适用于动态数据管理和频繁插入删除的场景。