在 PHP 中实现双向链表

从双链表的定义中我们已经知道，双链表节点将有两个链接：一个指向下一个节点，另一个指向上一个节点。此外，当我们添加一个新节点或删除一个新节点时，我们需要为每个受影响的节点设置下一个和上一个引用。在单链表的实现中，我们看到了一种不同的方法，即不跟踪最后一个节点，因此每次都必须使用迭代器才能到达最后一个节点。这一次，我们将在进行插入和删除操作时跟踪最后一个节点，以确保插入、删除和结束操作的复杂度为 \$O(1)\$。

下面是新节点类的外观，其中包含两个链接指针，以及双链表类的基本结构：

下一节，我们将探讨双链表的不同操作，从而了解单链表和双链表的基本区别。