当前位置：首页 > PHP

php 实现单链表

2026-02-13 13:42:55PHP

单链表的基本概念

单链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指向下一个节点的指针域。最后一个节点的指针域通常指向 NULL，表示链表结束。

单链表的节点结构

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

在链表尾部插入节点

public function insertAtTail($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 "NULL\n";
}

示例用法

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

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