php实现单链表的实例代码

下面是详细的“PHP实现单链表的实例代码”的攻略：

简介

单链表是一种常用的数据结构，它是由节点组成的一系列元素的集合。每个节点包含了指向下一个节点的指针（或者称为链接）。单链表的好处是可以很方便地在任意位置插入或删除元素，但访问节点的时间复杂度是O(n)。

我们使用PHP代码来实现一个单链表类，名为LinkedList，其中包含下列方法：

• __construct()：构造函数。
• add($data)：在链表末尾插入节点。
• insert($data, $position)：在指定位置插入节点。
• delete($position)：删除指定位置的节点。
• display()：打印链表内容。

注意，为了方便，我们将从0开始计数，链表的第一个节点的位置为0。

完整代码

下面是LinkedList类的完整代码，一共包含了上述5个方法：

class LinkedList {
    private $head;
    private $count;

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

    public function add($data) {
        $new_node = new ListNode($data);
        if ($this->head === null) {
            $this->head = &$new_node;
        } else {
            $current = $this->head;
            while ($current->getNext() !== null) {
                $current = $current->getNext();
            }
            $current->setNext($new_node);
        }
        $this->count++;
    }

    public function insert($data, $position) {
        if ($position < 0 || $position > $this->count) {
            return false;
        }
        $new_node = new ListNode($data);
        if ($position === 0) {
            $new_node->setNext($this->head);
            $this->head = &$new_node;
        } else {
            $current = $this->head;
            $index = 0;
            while ($index < ($position - 1)) {
                $current = $current->getNext();
                $index++;
            }
            $new_node->setNext($current->getNext());
            $current->setNext($new_node);
        }
        $this->count++;
        return true;
    }

    public function delete($position) {
        if ($position < 0 || $position >= $this->count) {
            return false;
        }
        if ($position === 0) {
            $this->head = $this->head->getNext();
        } else {
            $current = $this->head;
            $index = 0;
            while ($index < ($position - 1)) {
                $current = $current->getNext();
                $index++;
            }
            $current->setNext($current->getNext()->getNext());
        }
        $this->count--;
        return true;
    }

    public function display() {
        if ($this->head === null) {
            return;
        }
        $current = $this->head;
        while ($current !== null) {
            echo $current->getData() . " ";
            $current = $current->getNext();
        }
    }
}

class ListNode {
    private $data;
    private $next;

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

    public function getData() {
        return $this->data;
    }

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

    public function getNext() {
        return $this->next;
    }

    public function setNext($next) {
        $this->next = $next;
    }
}

在上面的代码中，ListNode类表示一个节点，LinkedList类表示整个单链表。

示例说明

下面是两个示例，说明如何使用LinkedList类。假设要创建一个包含5个元素的单链表。

示例1：添加元素

$ll = new LinkedList();
$ll->add(10);
$ll->add(20);
$ll->add(30);
$ll->add(40);
$ll->add(50);
$ll->display(); // 输出：10 20 30 40 50

在上面的代码中，首先创建一个空的单链表，然后调用add方法5次，在单链表末尾依次插入5个元素，最后调用display方法输出单链表的内容。

示例2：插入元素

$ll = new LinkedList();
$ll->add(10);
$ll->add(20);
$ll->add(30);
$ll->add(50);
$ll->insert(40, 3);
$ll->display(); // 输出：10 20 30 40 50

在上面的代码中，首先创建一个包含4个元素的单链表，然后调用insert方法，在位置3处插入元素40，最后调用display方法输出单链表的内容。

这些示例可能并不代表所有情况，但它们可以帮助您更好地了解如何使用LinkedList类。