什么是链表？

链表是称为节点的对象集合。每个节点都通过链接与下一个节点相连，而链接只不过是一个对象引用。如下图所示，每个方框代表一个节点。箭头表示节点之间的链接。这是单链表的一个例子。最后一个节点包含一个 NULL 的下一个链接，因此它标志着列表的结束：

image 2023 11 07 12 51 57 139

节点是一个对象，这意味着它可以存储任何数据类型，简单的如字符串、整数或浮点数，复杂的如数组、数组的数组、对象或对象数组。我们可以根据需要存储任何内容。

我们还可以对链表执行多种操作，例如以下操作：

  • 检查列表是否为空

  • 显示列表中的所有项目

  • 搜索列表中的项目

  • 获取列表大小

  • 在列表开头或结尾插入新项目

  • 从列表开头或结尾移除项目

  • 在特定位置或项目之前/之后插入新项目

  • 反转列表

这些只是可以在链表上执行的部分操作。

让我们编写一个简单的链表来存储一些名字：

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

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

前面我们提到，链表由节点组成。我们为节点创建了一个简单的类。ListNode 类有两个属性：一个用于存储数据，另一个用于名为 next 的链接。现在，我们将使用 ListNode 类实现一个链表。为了简单起见，我们将只进行两种操作：insert 和 display ：

class LinkedList {
    private $_firstNode = NULL;
    private $_totalNodes = 0;

    public function insert(string $data = NULL) {
        $newNode = new ListNode($data);

        if ($this->_firstNode === NULL) {
            $this->_firstNode = &$newNode;
        } else {
            $currentNode = $this->_firstNode;
            while ($currentNode->next !== NULL) {
                $currentNode = $currentNode->next;
            }
            $currentNode->next = $newNode;
        }
        $this->_totalNode++;
        return TRUE;
    }

    public function display() {
        echo "Total book titles: ".$this->_totalNode."\n";
        $currentNode = $this->_firstNode;
        while ($currentNode !== NULL) {
            echo $currentNode->data . "\n";
            $currentNode = $currentNode->next;
        }
    }
}

前面的代码实际上实现了插入和显示节点的两个基本操作。在 LinkedList 类中，我们有两个私有属性：$_firstNode 和 $_totalNodes。这两个属性的默认值分别是 NULL 和 0。我们需要标记头部节点或第一个节点，这样我们就能知道从哪里开始。我们也可以称其为前节点。无论我们给它起什么名字，它都将主要用于表示链表的起点。现在，让我们来看看插入操作代码。

插入方法需要一个参数，即数据本身。我们将使用 ListNode 类创建一个包含数据的新节点。在链接列表中插入书名之前，我们必须考虑两种可能性：

  • 列表为空，我们正在插入第一个标题

  • 列表不为空，标题将添加到最后

为什么我们需要考虑这两种情况呢？答案很简单。如果我们不知道列表是否为空，我们的操作可能会得到不同的结果。我们还可能在节点之间创建无效链接。因此，我们的想法是，如果列表为空，我们的插入项将是列表的第一个项。这就是代码第一部分要做的事情：

$newNode = new ListNode($data);

if ($this->_firstNode === NULL) {
    $this->_firstNode = &$newNode;
}

从前面的代码段中我们可以看到，我们正在用数据创建一个新节点，并将节点对象命名为 $newNode。然后，它会检查 $_firstNode 是否为空。如果是 NULL，则列表为空。如果为空，则将 $newNode 对象赋值给 $_firstNode 属性。现在，insert 方法的剩余部分代表我们的第二个条件，即列表不为空，我们必须在列表末尾添加新项目：

$currentNode = $this->_firstNode;
while ($currentNode->next !== NULL) {
    $currentNode = $currentNode->next;
}
$currentNode->next = $newNode;

在这里，我们从 $_firstNode 属性获取列表的第一个节点。现在，我们将从第一个节点开始遍历，直到列表结束。我们将通过检查当前节点的下一个链接是否为 NULL 来确保这一点。如果是 NULL，那么我们就到达了列表的末尾。为了确保我们不会一直循环到同一个节点，我们会在迭代过程中将当前节点的下一个节点设置为当前项目。while 循环代码实现了这一逻辑。一旦跳出 while 循环，我们就会将链接列表的最后一个节点设置为 $currentNode。现在，我们必须将当前最后一个节点的下一个链接分配给新创建的名为 $newNode 的节点，因此我们只需将对象放到节点的下一个链接上。这个对象引用将作为两个节点对象之间的链接。最后，我们还会通过后递增 $_totalNode 属性，将节点总数增加 1。

我们本可以很容易地为列表创建另一个属性来跟踪最后一个节点。这样我们就不必在每次插入新节点时循环整个列表了。我们故意忽略了这一选项，以加深对链表的基本理解。本章稍后，我们将实现这一功能，以加快操作速度。

如果我们看一下显示方法，就会发现我们使用了几乎类似的逻辑来遍历每个节点并显示其内容。我们首先获取链表的首项。然后，我们遍历列表，直到列表项为 NULL。在循环内部，我们通过显示 $data 属性来显示节点数据。现在，我们有了一个节点类 ListNode 来为链表创建单个节点，我们有了 LinkedList 类来进行基本的插入和显示操作。让我们编写一小段代码，利用 LinkedList 类创建一个书名链接列表：

$BookTitles = new LinkedList();
$BookTitles->insert("Introduction to Algorithm");
$BookTitles->insert("Introduction to PHP and Data structures");
$BookTitles->insert("Programming Intelligence");
$BookTitles->display();

在这里，我们为 LinkedList 创建一个新对象，并将其命名为 $BookTitles。然后，我们使用 insert 方法插入新书项。我们添加了三本书，然后使用 display 方法显示书名。如果运行前面的代码，我们将看到以下输出：

Total book titles: 3
Introduction to Algorithm
Introduction to PHP and Data structures
Programming Intelligence

我们可以看到，第一行有一个计数器，显示我们有三个书名以及它们的名称。如果我们仔细观察，就会发现书名的显示方式与我们输入书名的方式相同。这说明我们实现的链表实际上保持了顺序。这是因为我们总是将新节点输入列表的末尾。如果我们愿意，也可以采用不同的方法。作为第一个示例，我们已经介绍了很多关于链表和如何构建链表的知识。在接下来的章节中，我们将进一步探讨如何创建不同类型的链表，并举出更复杂的例子。现在，我们将重点讨论不同类型的链表。