SPL数据结构之双向链表SplDoublyLinkedList

[复制链接]
frankphper 发表于 2019-10-8 21:17:28 | 显示全部楼层 |阅读模式
后端技术文章分享公众号

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 frankphper 于 2019-10-9 14:48 编辑

SPL数据结构之双向链表SplDoublyLinkedList最先添加到链表中的节点叫做Bottom节点(底部),也叫Head节点,最后加入到链表中的节点叫做Top节点(头部),链表指针指向的节点叫做当前节点,链表指针是当前节点的一个标识,可以指向任意节点。任意一个节点都包含节点名称(key或offset)和节点数据(value)。
  1. <?php
  2. // 实例化双向链表
  3. $obj = new SplDoublyLinkedList();
  4. // 把新的节点数据添加到链表的顶部(Top)
  5. $obj->push(1);
  6. $obj->push(2);
  7. $obj->push(3);
  8. // 把新的节点数据添加到链表的底部(Bottom)
  9. $obj->unshift(10);
  10. print_r($obj);
  11. // 把节点指针指向Bottom所在的节点
  12. $obj->rewind();
  13. // 获取节点指针指向的节点(当前节点),一般需要和rewind配合使用
  14. echo 'Current:' . $obj->current() . "\r\n";
  15. // 使指针指向下一个节点(靠近top方向)
  16. $obj->next();
  17. echo 'Next node:' . $obj->current() . "\r\n";
  18. // 使指针指向上一个节点(靠近Bottom方向)
  19. $obj->prev();
  20. echo 'Next node:' . $obj->current() . "\r\n";
  21. $obj->next();
  22. $obj->next();
  23. $obj->next();
  24. $obj->next();
  25. echo 'Next node:' . $obj->current() . "\r\n";
  26. // 判断当前节点是否有效
  27. if ($obj->current()) {
  28.     echo "Current node valid\r\n";
  29. } else {
  30.     echo "Current node invalid\r\n";
  31. }
  32. // 如果当前节点有效,valid()返回true
  33. if ($obj->valid()) {
  34.     echo "valid list\r\n";
  35. } else {
  36.     echo "invalid list\r\n";
  37. }
  38. $obj->rewind();
  39. echo "Pop value:" . $obj->pop() . "\r\n";
  40. print_r($obj);
  41. echo "Current node:" . $obj->current() . "\r\n";
  42. $obj->next();
  43. $obj->next(); // 2 (top位置)
  44. // 把top位置的节点从链表中删除,并返回。如果current正好指向top位置,那么调用pop之后,current会失效。
  45. $obj->pop();
  46. echo 'next node:' . $obj->current() . "\r\n";
  47. // 把Bottom位置的节点从链表中删除,并返回。
  48. $obj->shift();
  49. print_r($obj);
复制代码
总结:
  • rewind使链表的当前指针指向链表的底部Bottom(头部)
  • push向链表的顶部Top(尾部)插入一个节点
  • pop获取链表中的顶部Top(尾部)节点,并且从链表中删除这个节点,该操作不改变指针的指向位置。
  • current指向链表当前节点的指针,必须在调用之前先调用rewind。当指向的节点被删除之后,将指向一个空节点。
  • next让链表当前节点的指针指向下一个节点,current的返回值随之改变。
  • unshift向链表的底部Bottom(头部)插入一个节点。
  • shift删除一个链表底部Bottom(头部)的节点。
  • bottom获取链表底部Bottom(头部)元素,当前指针位置不变。
  • top获取链表顶部Top(尾部)元素,当前指针位置不变。


本帖被以下淘专辑推荐:

*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则