如何实现双向链表只有一个指针？ [英] How to implement a double linked list with only one pointer?

问题描述

如何实现只用一个指针双链表？

这需要O（1）时间内找到preV和下一个节点。

 结构节点
{
   INT VAL;
   节点* P;
};
 

解决方案

这听起来好像是不可能的，它说的方式。你可以不执行，一般只使用一个两个指针。

您也许能挤出2个16位偏移到使用单一的空间（假设32位）指针，或其他一些聪明的黑客，但总体上这听起来不可能的。

本文描述了一个把戏基于XOR：荷兰国际集团的指针值，但我认为这是一个黑客（它按位运算的指针值）

。

How to implement a double linked list with only one pointer?

It takes O(1) time to find the prev and next Node.

struct Node
{
   int val;
   Node* p;
};

解决方案

This sounds as if it's impossible, the way it's stated. You can't implement two pointers using only one, in general.

You might be able to squeeze two 16-bit offsets into the space used by the single (assumed 32-bit) pointer, or some other "clever hack", but in general this sounds impossible.

This article describes a trick based on XOR:ing the pointer values, but I would consider that a hack (it does bitwise arithmetic on pointer values).

这篇关于如何实现双向链表只有一个指针？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！