PHP 双链表(SplDoublyLinkedList)简介和使用实例

首先我们先简单介绍一下PHP双链表(SplDoublyLinkedList)。

PHP双链表(SplDoublyLinkedList)简介

PHP双链表是一种可以双向遍历的线性结构，它能够在元素的前后两个方向上添加和删除元素，并且支持根据索引查询和修改元素。相对于PHP的普通数组来说，双链表在某些情况下会更加高效，尤其是在大量的插入和删除操作时。

PHP双链表的实现是使用了双向链表的数据结构，每个节点除了存储当前节点的值之外，还指向了前一个节点和下一个节点。PHP内置了SplDoublyLinkedList类来实现双链表，使用起来非常方便。

使用实例

接下来我们来看一下如何使用PHP双链表。

创建对象

首先我们需要创建一个SplDoublyLinkedList对象，可以使用如下代码：

$list = new SplDoublyLinkedList();

添加元素

向双链表中添加元素有两种方式：添加到头部和添加到尾部。我们可以使用以下方法来进行添加：

• push：添加到尾部
• unshift：添加到头部

例如，我们想要添加一个整数5到双链表的尾部，可以使用如下代码：

$list->push(5);

如果想要添加一个整数3到双链表的头部，可以使用如下代码：

$list->unshift(3);

删除元素

从双链表中删除元素同样可以使用两种方式：删除头部元素和删除尾部元素。我们可以使用以下方法来进行删除：

• shift：删除头部元素
• pop：删除尾部元素

例如，我们想要删除双链表的头部元素，可以使用如下代码：

$list->shift();

如果想要删除双链表的尾部元素，可以使用如下代码：

$list->pop();

获取元素

获取双链表中某个位置的元素可以使用以下方法：

• current：获取当前位置的元素
• next：将指针向后移动一位，返回移动后的元素
• previous：将指针向前移动一位，返回移动后的元素
• offsetGet：获取指定位置的元素

例如，如果我们想要获取双链表第二个元素的值，可以使用以下代码：

$list->next();
$value = $list->current();

如果我们想要获取双链表第三个元素的值，可以使用以下代码：

$list->next();
$list->next();
$value = $list->current();

如果想要获取双链表第一个元素的值，可以使用以下代码：

$value = $list->offsetGet(0);

修改元素

要修改双链表中某个位置的元素，可以使用以下方法：

• offsetSet：设置指定位置的元素为指定的值

例如，如果我们想要将双链表第二个元素改为8，可以使用以下代码：

$list->next();
$list->offsetSet($list->key(), 8);

示例1

下面是一个使用实例，我们创建一个双链表并向其中添加一些元素：

$list = new SplDoublyLinkedList();
$list->push(5);
$list->push(8);
$list->unshift(3);
$list->push(2);

然后遍历输出双链表中的元素：

for ($list->rewind(); $list->valid(); $list->next()) {
    echo $list->current() . "\n";
}

运行结果如下：

3
5
8
2

示例2

这是一个更加复杂的例子，我们创建一个双链表并模拟一个简单的贪吃蛇游戏。该游戏中蛇头作为双链表的尾部，蛇尾作为双链表的头部，每次移动时都向尾部添加一个新的节点，然后删除头部节点。

$list = new SplDoublyLinkedList();
$list->push(['x' => 5, 'y' => 5]);
$list->push(['x' => 4, 'y' => 5]);
$list->push(['x' => 3, 'y' => 5]);

$dir = 'right';
while(true) {
    // 获取蛇头和蛇尾节点
    $head = $list->top();
    $tail = $list->bottom();

    // 计算下一步蛇头的位置
    if($dir == 'right') {
        $nextHead = ['x' => $head['x'] + 1, 'y' => $head['y']];
    } elseif($dir == 'left') {
        $nextHead = ['x' => $head['x'] - 1, 'y' => $head['y']];
    } elseif($dir == 'up') {
        $nextHead = ['x' => $head['x'], 'y' => $head['y'] - 1];
    } elseif($dir == 'down') {
        $nextHead = ['x' => $head['x'], 'y' => $head['y'] + 1];
    }

    // 添加新的蛇头节点
    $list->push($nextHead);

    // 判断是否撞墙
    if($nextHead['x'] < 0 || $nextHead['x'] >= 10 || $nextHead['y'] < 0 || $nextHead['y'] >= 10) {
        echo "Game Over\n";
        break;
    }

    // 判断是否咬到自己
    $hasOverlap = false;
    for ($list->rewind(); $list->valid(); $list->next()) {
        $node = $list->current();
        if($node != $nextHead && $node['x'] == $nextHead['x'] && $node['y'] == $nextHead['y']) {
            $hasOverlap = true;
            break;
        }
    }
    if($hasOverlap) {
        echo "Game Over\n";
        break;
    }

    // 删除蛇尾节点
    $list->shift();

    // 输出蛇的当前状态
    for ($list->rewind(); $list->valid(); $list->next()) {
        $node = $list->current();
        if($node == $head) {
            echo 'H';
        } elseif($node == $tail) {
            echo 'T';
        } else {
            echo 'O';
        }
    }
    echo "\n";

    // 读取玩家输入，并设置移动方向
    $input = trim(fgets(STDIN));
    if($input == 'w') {
        $dir = 'up';
    } elseif($input == 'a') {
        $dir = 'left';
    } elseif($input == 's') {
        $dir = 'down';
    } elseif($input == 'd') {
        $dir = 'right';
    }
}

这里我们不讨论具体的贪吃蛇算法实现，重点是演示如何使用PHP双链表模拟游戏的过程。运行该代码后，玩家可以通过键盘输入"w"、"a"、"s"、"d"来控制蛇的移动方向，每移动一步都会输出蛇的当前状态，最终当游戏结束时输出"Game Over"。