当前位置：首页 > PHP

php 实现链表

2026-04-02 22:22:12PHP

PHP 实现链表的基本方法

链表是一种常见的数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。PHP 中可以通过类来实现链表。

定义链表节点类

创建一个 ListNode 类表示链表的节点，包含数据 (data) 和指向下一个节点的指针 (next)。

class ListNode {
    public $data;
    public $next;

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

定义链表类

创建一个 LinkedList 类管理链表的基本操作，如插入、删除和遍历。

class LinkedList {
    public $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->insertAtHead(20);
$list->insertAtTail(30);

// 打印链表
$list->printList(); // 输出: 20 -> 10 -> 30 -> NULL

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

链表的高级操作

链表还可以实现反转、查找中间节点等高级操作。

php 实现链表

反转链表

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 findMiddle() {
    $slow = $this->head;
    $fast = $this->head;
    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }
    return $slow->data;
}