PHP中的双链接列表和基本操作简介-DEV365 开发者社区

双重链接列表类似于单链接列表
单链接列表具有指向下一个元素的单个链接。双重链接列表有两个链接：一个到下一个元素，一个到上一个元素。

您可以在上一篇文章中阅读有关单链接列表的更多信息：
https://dev.to/matusstafura/introduction-to-singly-linked-list-and-basic-operations-in-php-1d71

关于一个节点

在双重链接列表中，节点是一个基本单元，它存储了一个数据，并在列表中对下一个和上一个节点进行引用。

这是php中的双链接列表中的节点类的示例：

class Node
{
    public $value;
    public $next;
    public $prev;

    public function __construct($value)
    {
        $this->value = $value;
        $this->prev = null;
        $this->next = null;
    }
}

此节点类有三个字段：
1，存储元素值的数据，
2，下一步，是对列表中的下一个节点的引用
3，prev，这是对列表中先前节点的引用

这是如何创建节点并将其链接到另一个节点的示例：

$nodeFirst = new Node(7);
$nodeSecond = new Node(3);

// connect $nodeFirst to nodeSecond with `next`
$nodeFirst->next = $nodeSecond;
// connect $nodeFirst to nodeSecond with `prev` (1)
$nodeSecond->prev = $nodeFirst;
// null<-7<=>3->null

// now you can receive value from second node
$nodeFirst->next->value; // 3
// and get previous value like this
$nodeSecond->prev->value; // 7

注意： 这与单链接列表非常相似，我们仅添加参考prev（1）以使其链接到双重链接。

此代码使用数据值7和3创建两个节点，并通过将nodeFirst的下一个字段设置为nodeSecond和nodeSecond的Prev将它们链接在一起。

双链接列表

构造函数

让我们创建一个代表双重链接列表数据结构的类。

此LinkedList类有三个实例变量：

$head：对列表中的第一个节点的引用，
$tail：对列表中的最后一个节点的引用，
$length：一个数量计算列表中节点数的整数。

注意： 如果列表中只有一个节点，则 head 和 tail 指向同一节点。

class DoublyLinkedList
{
    public $head;
    public $tail;
    public $length;

    public function __construct(public $value)
    {
        $newNode = new Node($value);
        $this->head = $newNode;
        $this->tail = $newNode;
        $this->length = 1;
    }
}

注意＃1： 我们不必初始化构造函数中的新节点，但是对于此解释很方便。
注释2： 在本文中，我将整数用作数据类型作为节点值。

打印所有节点

在转到基本操作之前，让我们创建一个辅助方法来打印双重链接列表中的所有节点。

说明：

在方法printAll()中，我们定义了局部变量$temp，并分配了 $ this-> head的值，这是对列表中的第一个节点的引用。

然后，它进入一个段循环，直到$temp不为空，这意味着没有更多的 next 节点。

呼应值后，该函数分配了$temp $temp->next，的值，将$temp移至列表中的下一个节点 ，以继续循环。

    // add to DoublyLinkedList class
    public function printAll()
    {
        $temp = $this->head;
        while ($temp != null) {
            echo $temp->value;
            $temp = $temp->next;
        }
        echo PHP_EOL;
    }

1.附加

附加节点意味着在双重链接列表的末尾添加新节点。

在左侧，我们有一个带有单个节点的双重链接列表的示例。右边是我们要附加的节点。结果链接列表看起来像图像底部所示的列表。

说明：

我们创建一个具有值的新节点。
如果链接列表为空，我们将头和尾部分配给新节点，因为它是列表中唯一的节点。
否则，我们将新节点与prev属性联系起来。
我们将尾部节点与下一个属性联系起来。
我们将尾部引用更改为新节点。
我们增加了双链接列表的计数（长度）。

// add to DoublyLinkedList class
    public function append($value)
    {
        $newNode = new Node($value);

        if ($this->length == 0) {
            $this->head = $newNode;
            $this->tail = $newNode;
        } else {
            $newNode->prev = $this->tail;
            $this->tail->next = $newNode;
            $this->tail = $newNode;
        }

        $this->length++;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->printAll();
// 2 7 3 9

2.获取

获得节点意味着在双链接列表中的某个索引中检索节点。该方法返回节点对象，而不仅仅是节点的值。

说明：

首先，我们确保索引在双重链接列表的范围内；它应该大于零且小于双链接列表的计数（长度）。
我们将列表的头部分配给临时变量温度，以便我们可以在穿越列表时跟踪我们的位置。
然后我们循环浏览列表，直到达到所需的索引。
该方法在指定的索引处返回节点。

// add to DoublyLinkedList class
    public function getNode($index)
    {
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

        $temp = $this->head;
        for ($i = 0; $i < $index; $i++) {
            $temp = $temp->next;
        }

        return $temp;
    }
$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$node = $dll->getNode(1);
echo $node->value; 
// 7

该脚本看起来像是单个链接列表的一个，并且正常工作。但是我们可以使它变得更好，因为我们也跟踪prev节点。

为什么？

假设我们在列表中有一百万个节点，我们希望获得第999,998个节点（最后一个是一个，因为索引从0开始）。我们可以从几乎整个列表中循环遍历整个列表，而是可以从尾巴上穿越并更快地进行。

我们可以通过多种方法来优化这一点。这是一种方法，我们检查索引是在上半场还是列表的后半部分。

如果是在上半场（从一开始），我们会在上一个示例中遍历我们的操作方式。如果是下半场，我们将从尾巴横穿。我们不使用下一个引用，而是使用上一篇。

这样：

// add to DoublyLinkedList class
    public function getNodeOptimized($index)
    {
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

        if ($index < $this->length / 2) {
            $temp = $this->head;
            for ($i = 0; $i < $index; $i++) {
                $temp = $temp->next;
            }
        } else {
            $temp = $this->tail;
            for ($i = $this->length - 1; $i > $index; $i--) {
                $temp = $temp->prev;
            }
        }

        return $temp;
    }
$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->getNodeOptimized(3)->value; // one loop from tail instead of three loops from head
$dll->printAll();
// 9

3.设置

设置节点是用新值替换某些索引的现有节点的值。

说明：

我们使用现有方法getNode（）在指定索引处找到节点，或者如果索引不在限制范围内。
我们为检索的节点分配了一个新值。

// add to DoublyLinkedList class
    public function setNode($index, $value)
    {
        $temp = $this->getNode($index);
        if ($temp) {
            $temp->value = $value;
        }
    }
$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->setNode(1,54); // replaces value at index 1 with value 54
$dll->printAll();
// 2 54 3 9

4.预登

预处节点意味着在链接列表的开头添加新节点。

在左侧是我们要预先准备的节点，左侧是现有的双重链接列表。结果链接列表看起来像图像底部所示的列表。

说明：

我们创建一个节点。
如果列表中没有节点，我们将头和尾部分配给新节点。
否则，我们首先将新节点链接到头部。
我们将头部与上级属性联系到新节点。
我们将头引用更改为新节点。
我们将双链接列表的计数（长度）增加。

// add to DoublyLinkedList class
    public function prepend($value)
    {
        $newNode = new Node($value);
        if ($this->length == 0) {
            $this->head = $newNode;
            $this->tail = $newNode;
        } else {
            $newNode->next = $this->head;
            $this->head->prev = $newNode;
            $this->head = $newNode;
        }

        $this->length++;
    }
$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->prepend(15); // adds a node with value 15 at the beginning
$dll->printAll();
// 15 2 7 3 9

5.插入

要在双重链接列表中插入一个节点意味着在特定位置添加新的节点，将任何后续节点转移到了为新节点腾出空间的权利。例如，如果我们有一个带有三个节点（2、7、3）的链接列表，并且我们想在7和3之间插入一个新节点（x），则结果链接列表看起来像（2、7，x，3 ）。

说明：

我们检查索引是否在列表的范围内。
如果索引为0，我们不需要穿越列表，并且可以使用现有的预端（$ value）方法将新节点插入列表开头。如果索引是列表中的最后一个位置（索引等于列表的长度），我们可以使用Append（$ value）方法将新节点插入列表末尾。
否则，我们创建一个具有给定值的新节点。
我们需要在要插入新节点的位置之前立即在索引处找到节点。我们将此节点分配给称为“之前”的临时变量。
我们还需要在要插入新节点的索引之后跟踪节点。我们将此节点分配给称为“ After”的临时变量。
我们将新节点与prev属性链接到“前”节点和下一个属性到“ after”节点。
我们将之前的节点链接到新节点（使用下一个属性），然后将后节点链接到新节点（使用prev属性）。
最后，我们将链接列表的计数（长度）增加。

// add to DoublyLinkedList class
    public function insert($index, $value)
    {
        if ($index < 0 || $index > $this->length) {
            return null;
        }

        if ($index == 0) {
            $this->prepend($value);
            return;
        }

        if ($index == $this->length) {
            $this->append($value);
            return;
        }

        $newNode = new Node($value);
        $before = $this->getNode($index - 1);
        $after = $before->next;

        $newNode->prev = $before;
        $newNode->next = $after;
        $before->next = $newNode;
        $after->prev = $newNode;

        $this->length++;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->insert(2, 77); // inserts a node with value 77 at index 2
$dll->printAll();
// 2 7 77 3 9

6.首先弹出

首先要删除链接列表开头的节点。

说明：

我们检查链接列表是否没有空。
如果列表中只有一个节点，我们只是将头部和尾巴重置为null。
否则，我们创建一个称为$ temp的临时变量，并将其分配给头部。
然后，我们将头分配到下一个节点。
我们将头部的前一个属性重置为null。
和通过更改temp->在null旁边的temp-> temp。
我们减少了链接列表的计数（长度）。

// add to DoublyLinkedList class
    public function popFirst()
    {
        if ($this->length == 0) {
            return null;
        }

        $temp = $this->head;
        if ($this->length == 1) {
            $this->head = null;
            $this->tail = null;
        } else {
            $this->head = $this->head->next;
            $this->head->prev = null;
            $temp->next = null;
        }

        $this->length--;
        return $temp;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->popFirst(); // removes first node
$dll->printAll();
// 7 3 9

7. pop last

pop last节点是删除链接列表中的最后一个节点。

比单链接列表中的双重链接列表中删除最后一个节点更快，更容易。我们不需要穿越整个列表即可到达末端；我们使用尾巴的存在和上述参考。

说明：

我们检查链接列表是否没有空。
如果链接列表中只有一个节点，我们将头部和尾巴重置为null。
我们将尾巴分配给先前的节点。
我们将下一个节点与null取消链接。
我们减少了链接列表的计数（长度）。

// add to DoublyLinkedList class
    public function popLast()
    {
        if ($this->length == 0) {
            return null;
        }
        $temp = $this->tail;
        if ($this->length == 1) {
            $this->head = null;
            $this->tail = null;
        } else {
            $this->tail = $this->tail->prev;
            $this->tail->next = null;
            $temp->prev = null;
        }

        $this->length--;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->popLast(); // removes last node
$dll->printAll();
// 2 7 3

8.删除

从链接列表中删除节点意味着将其从某个索引中删除列表中，并更新周围节点的下一个指针以维护列表的完整性。

它与插入相反。

说明：

我们检查索引是否在链接列表的范围内。
如果索引为0，我们可以使用popfirst（）方法来删除列表开头的节点。如果索引是列表中的最后一个位置（索引等于列表的长度），我们可以使用poplast（）方法删除列表末尾的节点。
其他，我们找到了带有现有方法getNode（）的节点。
我们要删除节点之前和之后链接节点。
我们通过将null分配给Prev和下一步。
我们减少了链接列表的计数（长度）。

// add to DoublyLinkedList class
    public function remove($index)
    {
        if ($index < 0 || $index >= $this->length) {
            return null;
        }

        if ($index == 0) {
            return $this->popFirst();
        }

        if ($index == $this->length - 1) {
            return $this->popLast();
        }

        $temp = $this->getNode($index);

        $temp->next->prev = $temp->prev;
        $temp->prev->next = $temp->next;
        $temp->next = null;
        $temp->prev = null;

        $this->length--;
        return $temp;
    }

$dll = new DoublyLinkedList(2);

$dll->append(7);
$dll->append(3);
$dll->append(9);

$dll->remove(2); // removes node at index 2
$dll->printAll();
// 2 7 9

您可以在这里找到完整的脚本：https://gist.github.com/matusstafura/c53bf80421d0b312a9b42193f68ac5ea

时间复杂性

双链接列表上普通操作的时间复杂性如下：

开始插入：o（1）
最后插入：o（1）
给定节点后的插入：O（1）
开头删除：o（1）
最后的删除：o（1）
给定节点的删除：o（1）
搜索：o n）< / li> / li> / li> / li>
访问：o（n）

注意：这些时间复杂性适用于带有头部和尾指针的双重链接列表，这可以在列表的开始和结束时有效地插入和删除。没有这些指针，列表开始和结束时插入和删除的时间复杂性将为o（n）。

目录

关于一个节点

双链接列表

构造函数

打印所有节点

1.附加

2.获取

3.设置

4.预登

5.插入

6.首先弹出

7. pop last

8.删除

时间复杂性