在 PHP 中实现链表

1. 使用 SplDoublyLinkedList 类在 PHP 中实现链表
2. 使用 push() 方法在链表中插入值
3. 使用 add() 方法在链表中插入值
4. 使用 pop() 方法删除链表中的元素
5. 从链接列表中查找顶部和底部值

本文将介绍 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