PHP小教程之实现链表

PHP小教程之实现链表

什么是链表

链表是一种常见的线性结构，在计算机科学中有着广泛的应用。链表由若干个节点构成，每个节点都包含一个数据元素和一个指向下一个节点的引用。通俗的说，链表就像一条链子，链子上有很多环节，每个环节都有一些信息，同时也知道下一个环节在哪里。

链表的实现

链表可以使用 PHP 数组，但是我们也可以通过代码实现自己的链表类。下面是链表的核心部分代码。

<?php

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

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

class LinkedList {
    private $firstNode = NULL;
    private $lastNode = NULL;
    private $nodeCount = 0;

    public function append($data) {
        $newNode = new ListNode($data);

        if ($this->firstNode === NULL) {
            $this->firstNode = &$newNode;
            $this->lastNode = $newNode;
        } else {
            $this->lastNode->next = $newNode;
            $this->lastNode = $newNode;
        }

        $this->nodeCount++;
        return TRUE;
    }

    public function delete($pos) {
        if ($this->nodeCount === 0 || $pos < 1 || $pos > $this->nodeCount) {
            return FALSE;
        }

        $current = $this->firstNode;
        if ($this->nodeCount === 1) {
            $this->firstNode = NULL;
            $this->lastNode = NULL;
            $this->nodeCount = 0;
            return TRUE;
        } elseif ($pos === 1) {
            $this->firstNode = $this->firstNode->next;
            $this->nodeCount--;
            return TRUE;
        } else {
            $previous = NULL;
            $count = 1;

            while ($count < $pos) {
                $previous = $current;
                $current = $current->next;
                $count++;
            }

            $previous->next = $current->next;
            $this->nodeCount--;

            if ($this->lastNode === $current) {
                $this->lastNode = $previous;
            }

            return TRUE;
        }
    }

    public function display() {
        echo "Total nodes: " . $this->nodeCount . "\n";
        $current = $this->firstNode;
        while ($current !== NULL) {
            echo $current->data . "\n";
            $current = $current->next;
        }
    }
}

这段代码定义了 ListNode 类和 LinkedList 类，其中 ListNode 类是每个节点的数据结构，LinkedList 类则是链表本身的实现。

ListNode 类

ListNode 类包含了两个成员变量：$data 和 $next。其中，$data 是每个节点的数据，$next 是指向链表下一个节点的指针。ListNode 类定义的是如何表达单个节点的结构。

LinkedList 类

LinkedList 类定义了几个成员变量：$firstNode 和 $lastNode 定义链表的首节点和尾节点；$nodeCount 表示链表中包含的节点个数。

类中的三个方法：

• append(): 往链表的最后一个节点追加新节点
• delete(): 删除链表中指定位置的节点
• display(): 显示链表的详细信息

示例1

$list = new LinkedList();
$list->append('PHP');
$list->append('Java');
$list->append('Python');
$list->delete(2);
$list->display();

运行以上代码，输出如下：

Total nodes: 2
PHP
Python

首先创建了一个 LinkedList 的实例，并添加了三个节点，分别是 “PHP”、”Java“、”Python“。然后，删除了第二个元素”Java“。最后，调用 display() 方法，展示链表中剩余的节点信息。

示例2

$list = new LinkedList();
$list->append(1);
$list->append(2);
$list->append(3);
$list->delete(2);
$list->append(4);
$list->display();

运行以上代码，输出如下：

Total nodes: 3
1
3
4

这个示例的过程和示例 1 的过程基本一致，在链表中添加了四个元素 1、2、3、4。其中，删除第二个元素”2“，然后，在链表的最后面添加了新元素”4“。最后，调用 display() 方法，展示链表中剩余的节点信息。

总结

本文通过 PHP 实现链表类，介绍了链表和其基本实现以及一些由此引发的操作。链表是计算机科学中常用的数据结构，掌握链表对于开发者来说是相对比较容易的。