要求：

Explain how to implement doubly linked lists using only one pointer value x.np per
item instead of the usual two (next and prev). Assume that all pointer values can be
interpreted as k-bit integers, and define x.np to be x.np = x.next XOR x.prev,
the k-bit “exclusive-or” of x.next and x.prev. (The value NIL is represented by 0.)
Be sure to describe what information you need to access the head of the list. Show
how to implement the SEARCH, INSERT, and DELETE operations on such a list.
Also show how to reverse such a list in O(1) time.

解法：

x.np = x.prev ^ x.next

NIL用0表示

考虑链表第一个元素x.np = NIL ^ x.next = x.next，即链表头存的指针值和普通双向链表的next指针相同

中间所有元素x.np = x.prev ^ x.next

考虑链表最后一个元素x.np = x.prev ^ NIL = x.prev，即链表最后一个元素存的指针和普通双向链表的prev指针相同

我们知道第一个元素的next指针，中间元素的next指针可以通过前一个元素的np和当前元素的np异或计算获得，这就为前序遍历创造了可能

我们知道最后一个元素的prev指针，中间元素的prev指针可以通过当前元素的np和后一个元素的np异或计算获得，这就为后续遍历创造了可能

总之，np = prev ^ next, NIL = 0致使链表头元素和尾元素np值具有了特殊性，这正是此种表示的精妙之处，节省了O(n)的空间开销，但增加了运算开销（位运算），计算机执行位运算具有速度优势。

此种情况下，如果想要翻转链表就变得异常容易，只需要将链表的头尾指针交换即可。

最新文章

1. Daily Scrum Meeting ——FifthDay(Beta)12.13
2. 求第K大数
3. php提示 Notice: Use of undefined constant name - assumed
4. [cocos2d-js]长按按钮事件
5. 面试之SQL（2）--left join, inner join 和 right join的区别
6. POJ 3321 Apple Tree（dfs序树状数组）
7. HTML中的转义字符
8. Android 自定义View (一)
9. 常见MYSQL导入导出数据命令
10. 【Android病毒分析报告】 - ZooTiger “集恶意推广、隐私窃取、恶意吸费于一体”
11. Linux下PHP与普通C程序通信
12. Android5.0特性ToolBar
13. Python-Flask框架之——图书管理系统 , 附详解源码和效果图 !
14. 全文检索-Elasticsearch （三） DSL
15. [Tex学习笔记]小于等于一个常数乘以...
16. python 多线程中子线程和主线程相互通信
17. DOS和批处理基本命令
18. 5、Docker网络配置（单机）
19. binlog2sql的安装及使用
20. RN API备忘

热门文章

1. P5055 【模板】可持久化文艺平衡树 可持久化fhqtreap
2. 洛谷p1967货车运输（kruskal重构树）
3. 前端零基础入门：页面结构层HTML（2）
4. 解决IDEA中maven导入jar包
5. Mybatis的if标签判断空字符串 == 0，参数为0时会自动转为空字符串
6. element UI中的select选择器的change方法需要传递多个值
7. buddo源码分析-transport组件之Netty（一）
8. C++ 函数模板print
9. 011 webpack中使用vue
10. linux 压缩、解压、zip/unzip/jar