当前位置：首页 > PHP

php 实现链表

2026-02-13 14:52:35PHP

链表的基本概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表在内存中不是连续存储的，因此插入和删除操作更高效。

实现链表节点

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

class Node {
    public $data;
    public $next;

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

实现链表类

链表类提供对链表的操作，如插入、删除和遍历。

class LinkedList {
    public $head;

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

    // 在链表末尾插入节点
    public function insert($data) {
        $newNode = new Node($data);
        if ($this->head === null) {
            $this->head = $newNode;
        } else {
            $current = $this->head;
            while ($current->next !== null) {
                $current = $current->next;
            }
            $current->next = $newNode;
        }
    }

    // 删除指定数据的节点
    public function delete($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 display() {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " ";
            $current = $current->next;
        }
        echo "\n";
    }
}

使用链表

创建链表实例并执行插入、删除和显示操作。

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

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

链表的高级操作

反转链表

反转链表可以通过迭代或递归实现。以下是迭代方法：

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

链表的变种

双向链表

双向链表的节点包含指向前一个节点的指针。

class DoublyNode {
    public $data;
    public $next;
    public $prev;

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

循环链表

循环链表的尾节点指向头节点。

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