在 PHP 中实现链表

本文将介绍 PHP 中链表的实现。

使用 SplDoublyLinkedList 类在 PHP 中实现链表

链表是在许多编程语言中实现的常见数据结构。它是线性的，包含相互链接的节点。

每个节点都包含数据和到相邻节点的链接。因此，链表形成了一个节点链。链表有不同的变体。

1. 单链表：单向。它只在向前的方向上移动。
2. 双链表：是双向的。它向前和向后两个方向遍历。
3. 循环链表：单向循环。
4. 循环双向链表：双向循环。

我们可以在链表中进行各种操作。基本操作如下：

• 遍历
• 插入
• 删除
• 更新
• 搜索

PHP 提供了一个类 SplDoublyLinkedList 用于实现链表。它是一个双向链表。

使用 push() 方法在链表中插入值

push() 方法接受要推送的参数并允许在列表中附加值。该元素将被推到链表的末尾。

例如，创建类 SplDoublyLinkedList 的实例并将其分配给 $list 变量。调用 push() 方法并插入元素。

示例代码：

$list = new SplDoublyLinkedList;

$list->push(10);
$list->push(20);
$list->push(30);
$list->push(40);
$list->push(40);

在下面的示例中，我们在一个空链表中附加了元素 10、20、30、40 和 40。请注意，元素 40 被附加了两次。

我们可以使用下面的函数来显示列表的元素。

function displayList($list){
  for ($list->rewind(); $list->valid(); $list->next()) {
    echo $list->current()."<br>";
  }
}

rewind() 方法从链表的开头回退迭代器。例如，迭代器将移动到列表的第一个元素。

valid() 方法检查链表是否包含更多节点，next() 方法移动到链表的下一项。因此，我们可以在 for 循环中使用上述示例中的这些方法来遍历链表的元素。

在循环内部，current() 方法表示当前元素。因此，将打印当前元素。

当我们需要打印列表元素时，我们可以调用这个函数 displayList()。我们将在文章中多次使用此功能。

以下是我们以 $list 作为参数调用 displayList() 函数时的输出。

输出：

10
20
30
40
40

使用 add() 方法在链表中插入值

我们可以使用 add() 方法通过指定位置在链表中插入元素。该方法有两个参数。

第一个参数是要插入项目的索引，第二个参数是要插入的项目。例如，以 4 和 50 为参数调用 add() 方法并调用 displayList() 方法。

示例代码：

$list->add(4,50);
displayList($list);

上面的代码在我们创建的链表的第四个索引中添加了元素 50。

输出：

10
20
30
40
50
40

结果，元素 50 出现在第四个索引中。之前在第四个索引中的元素 40 被移动到链表的末尾。

使用 pop() 方法删除链表中的元素

我们可以使用 pop() 方法从链表中删除最后一个元素。该方法不接受任何参数。

从上面的最后一个输出开始，该列表包含以下元素。

10
20
30
40
50
40

pop() 方法将从链表中删除最后一个元素（40）。

示例代码：

$list->pop();
displayList($list);

输出：

10
20
30
40
50

从链接列表中查找顶部和底部值

我们可以使用 top() 方法找到链表的顶部值，对于底部值，我们可以使用 bottom() 方法。下面的例子也是上面例子的延续。

该列表包含以下项目。

10
20
30
40
50

我们可以使用 $list 对象调用 top() 和 bottom() 函数，并使用 echo 函数打印它们。

示例代码：

displayList($list);
echo "the top value: ".$list->top()."<br>";
echo "the bottom value: ".$list->bottom()."<br>";

结果，最上面的项目显示为 50，最底部的项目显示为 10。

输出：

10
20
30
40
50
the top value: 50
the bottom value: 10