当前位置：首页 > PHP

php如何实现链表

2026-02-14 00:32:51PHP

PHP实现链表的方法

在PHP中实现链表可以通过类和对象的方式完成。链表由节点组成，每个节点包含数据和指向下一个节点的引用。以下是单向链表和双向链表的实现示例。

单向链表的实现

单向链表每个节点只有一个指向下一个节点的指针。

class ListNode {
    public $data = null;
    public $next = null;

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

class LinkedList {
    private $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;
        }
    }
}

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

双向链表的实现

双向链表每个节点有两个指针，分别指向前一个和后一个节点。

class DoublyListNode {
    public $data = null;
    public $prev = null;
    public $next = null;

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

class DoublyLinkedList {
    private $head = null;
    private $tail = null;

    public function insert($data) {
        $newNode = new DoublyListNode($data);
        if ($this->head === null) {
            $this->head = $newNode;
            $this->tail = $newNode;
        } else {
            $newNode->prev = $this->tail;
            $this->tail->next = $newNode;
            $this->tail = $newNode;
        }
    }

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

    public function displayBackward() {
        $current = $this->tail;
        while ($current !== null) {
            echo $current->data . " ";
            $current = $current->prev;
        }
    }
}

$dList = new DoublyLinkedList();
$dList->insert(10);
$dList->insert(20);
$dList->insert(30);
$dList->displayForward(); // 输出: 10 20 30
$dList->displayBackward(); // 输出: 30 20 10

链表操作的常见方法

链表支持多种操作，如插入、删除、查找等。以下是几种常见操作的实现。

在链表头部插入节点

public function insertAtHead($data) {
    $newNode = new ListNode($data);
    $newNode->next = $this->head;
    $this->head = $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) {
        if ($current->next->data === $data) {
            $current->next = $current->next->next;
            return;
        }
        $current = $current->next;
    }
}

查找节点是否存在

php如何实现链表

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