第八章：第9节 PHP数据结构与算法——双向链表

双向链表——链表的又一种形式，单链表的进化版本，在单链表的结点中增加一个指向其前驱的 pre 指针。

有了单链表，为什么需要双向链表？

1、单链表的节点都只有一个指向下一个结点的指针

2、单链表的数据元素无法直接访问其前驱元素

3、逆序访问单链表中的元素是极其耗时的操作！

4、单链表的节点不能做到自我删除，需要依靠辅助节点。

一个单向链表，光靠cur是不能删除当前节点（紫色的）的，因为光靠cur是无法访问到它的前一个节点（绿色的）的，所以它没办法自我删除。双向链表可以访问前一节点，所以它可以把自己删除掉。

双向链表的优点：

1、双向链表在单链表的基础上增加了指向前驱的指针。

2、功能上双向链表可以完全取代单链表的使用。

3、双向链表的 Next，Pre 和 Current 操作可以高效的遍历链表中的所有元素。

缺点：

同样是代码变复杂了。

双向链表的数据操作设计原理演示：

插入操作：

在普通位置插入节点

$current->next = $node;

$node->next = $next;

$next->pre = $node;

$node->pre = $current;

删除操作：

删除普通节点：

$current->next = $next;

$next->prev = $current;

节点自我删除，那代码是这样：

$ret->prev->next = $ret->next;

$ret->next->prev = $ret->prev;