当前位置：首页 > PHP

php 链表实现

2026-01-15 12:20:44PHP

在 PHP 中实现链表可以通过类来模拟链表节点（Node）和链表（LinkedList）结构。以下是链表的完整实现示例，包含基础操作如插入、删除、遍历等。

链表节点类（Node）

链表的基本单元是节点，每个节点包含数据（data）和指向下一个节点的指针（next）。

class Node {
    public $data;
    public $next;

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

链表类（LinkedList）

链表类管理节点的增删查改操作，并维护头节点（head）。

class LinkedList {
    private $head;

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

    // 在链表头部插入节点
    public function insertAtHead($data) {
        $newNode = new Node($data);
        $newNode->next = $this->head;
        $this->head = $newNode;
    }

    // 在链表尾部插入节点
    public function insertAtTail($data) {
        $newNode = new Node($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(3);     // 链表: 3 -> NULL
$list->insertAtHead(2);     // 链表: 2 -> 3 -> NULL
$list->insertAtTail(4);     // 链表: 2 -> 3 -> 4 -> NULL
$list->deleteNode(3);       // 链表: 2 -> 4 -> NULL
$list->printList();         // 输出: 2 -> 4 -> NULL

扩展操作

查找节点是否存在

public function search($data) {
 $current = $this->head;
 while ($current !== null) {
     if ($current->data === $data) {
         return true;
     }
     $current = $current->next;
 }
 return false;
}

反转链表

public function reverse() {
 $prev = null;
 $current = $this->head;
 while ($current !== null) {
     $next = $current->next;
     $current->next = $prev;
     $prev = $current;
     $current = $next;
 }
 $this->head = $prev;
}