当前位置：首页 > PHP

php单链表实现

2026-02-16 06:50:49PHP

PHP 单链表实现

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

节点类定义

单链表的节点类包含数据（data）和指向下一个节点的指针（next）。

class ListNode {
    public $data;
    public $next;

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

链表类定义

链表类包含头节点（head）和基本操作方法。

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

    // 删除指定数据的节点
    public function delete($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 search($data) {
        $current = $this->head;
        while ($current !== null) {
            if ($current->data === $data) {
                return true;
            }
            $current = $current->next;
        }
        return false;
    }

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

使用示例

$list = new LinkedList();
$list->insertAtHead(10);
$list->insertAtTail(20);
$list->insertAtTail(30);
$list->display(); // 输出: 10 -> 20 -> 30 -> NULL

$list->delete(20);
$list->display(); // 输出: 10 -> 30 -> NULL

echo $list->search(30) ? "Found\n" : "Not Found\n"; // 输出: Found