第八章：第10节 PHP数据结构与算法——双向链表强化学习
更新于：2017-06-29 21:13:52
还是韩顺平的笔记：
用双向链表实现水浒英雄排行榜：
已经有1号英雄和5号英雄，现在要添加3号英雄
此时cur指向了1号英雄，hero指向3号英雄
cur指向1号英雄，发现cur的下一个是5号英雄，大于要添加的3号英雄
分析图
过程：
（1）让3号英雄指向5号英雄，即把这个①号线搭起来
$hero->next=$cur->next;
//$cur指向1号英雄，$cur->next指向5号英雄
（2）然后再搭pre这根线，让3号英雄的pre指向1号英雄，即把这个②号线搭起来
$hero->per=$cur;
（3）然后让5号英雄的pre指向3号英雄，即把这个③号线搭起来
$cur->next->pre=$hero;
//$cur->next指向5号英雄，$cur->next->pre为5号英雄指向1号英雄，即图中⑥号线
//此时⑥号线就断掉了，原来的5号英雄的pre是指向1号英雄的，现在指向了3号英雄
（4）让1号英雄指向3号英雄，即把这个④号线搭起来
$cur->next=$hero;
//此时⑤号线就断掉了，原来的$cur->next是指向5号英雄的，现在指向了3号英雄
定义英雄类：
英雄类的静态方法——添加hero
英雄类的静态方法——显示hero
看看添加结果和显示结果：
此时删除英雄就不需要辅助节点了
分析图：
当要删除的节点在最后的时候，还需要判断下
此时$cur->next本身就是NULL了，所有要加判断了
$cur->pre->next=$cur->next; //这个就相当于把1号节点的next置空了，这个没错
所以要这样：
if( !is_null($cur->next) ){
$cur->next->pre=$cur->pre;
}
$cur->pre->next=$cur->next;
这样执行的话，把上图中的蓝线就去掉了，这样6号英雄就访问不到了，6号英雄出列了，因为我们是从表头开始找的，$cur-next就访问不到6号英雄节点了，6号英雄指向别人是没有用的，★关键★是没有人指向它。
注意：要考虑删除第一个和最后一个，（当你的代码考虑不周全的时候）这是最容易出错的，所以要测试
双向链表的好处：
双向链表可以完成自我删除，效率高一些，而且学明白双向链表后，为你将来，学习二叉树，霍夫曼树等等，打下了良好的基础。