在 PHP 中实现链表

Subodh Poudel 2023年1月30日 2022年7月12日
  1. 使用 SplDoublyLinkedList 类在 PHP 中实现链表
  2. 使用 push() 方法在链表中插入值
  3. 使用 add() 方法在链表中插入值
  4. 使用 pop() 方法删除链表中的元素
  5. 从链接列表中查找顶部和底部值
在 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);

在下面的示例中,我们在一个空链表中附加了元素 1020304040。请注意,元素 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() 方法通过指定位置在链表中插入元素。该方法有两个参数。

第一个参数是要插入项目的索引,第二个参数是要插入的项目。例如,以 450 为参数调用 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
Subodh Poudel avatar Subodh Poudel avatar

Subodh is a proactive software engineer, specialized in fintech industry and a writer who loves to express his software development learnings and set of skills through blogs and articles.

LinkedIn