当前位置：首页 > PHP

php 实现链表

2026-02-27 13:33:51PHP

链表的基本概念

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

链表节点的实现

在 PHP 中，链表节点可以通过类（Class）实现。每个节点包含数据属性和指向下一个节点的引用。

class ListNode {
    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 ListNode($data);
        if ($this->head === null) {
            $this->head = $newNode;
        } else {
            $current = $this->head;
            while ($current->next !== null) {
                $current = $current->next;
            }
            $current->next = $newNode;
        }
    }
}

链表的遍历

遍历链表并输出所有节点的数据：

public function display() {
    $current = $this->head;
    while ($current !== null) {
        echo $current->data . " ";
        $current = $current->next;
    }
    echo "\n";
}

链表的删除

删除链表中指定值的节点：

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) {
        if ($current->next->data === $data) {
            $current->next = $current->next->next;
            return;
        }
        $current = $current->next;
    }
}

完整示例代码

以下是一个完整的链表实现示例：

class ListNode {
    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 ListNode($data);
        if ($this->head === null) {
            $this->head = $newNode;
        } else {
            $current = $this->head;
            while ($current->next !== null) {
                $current = $current->next;
            }
            $current->next = $newNode;
        }
    }

    public function display() {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " ";
            $current = $current->next;
        }
        echo "\n";
    }

    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) {
            if ($current->next->data === $data) {
                $current->next = $current->next->next;
                return;
            }
            $current = $current->next;
        }
    }
}

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

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