当前位置：首页 > PHP

php 链表实现

2026-04-02 22:20:33PHP

PHP 链表实现方法

链表是一种线性数据结构，通过节点之间的指针连接实现动态存储。在PHP中可以通过类（Class）和对象（Object）模拟链表结构。

链表节点类定义

链表的基础是节点（Node），每个节点包含数据和指向下一个节点的指针：

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 "NULL\n";
    }
}

链表使用示例

$list = new LinkedList();

// 插入节点
$list->insertAtEnd(10);
$list->insertAtEnd(20);
$list->insertAtBeginning(5);

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

// 删除节点
$list->deleteNode(10);

// 打印链表: 5 -> 20 -> NULL
$list->printList();

链表反转实现

链表反转是常见操作，可以通过迭代或递归实现：

// 在LinkedList类中添加反转方法
public function reverse() {
    $prev = null;
    $current = $this->head;

    while ($current !== null) {
        $next = $current->next;
        $current->next = $prev;
        $prev = $current;
        $current = $next;
    }

    $this->head = $prev;
}

双向链表实现

双向链表每个节点包含指向前后节点的指针：

php 链表实现

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;
    }

    // 实现双向链表的插入、删除等方法
}