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

问题描述

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

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

需要O（1）时间才能找到上一个和下一个节点。

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.

您可能可以将两个16位偏移量压缩到单个空间使用的空间（假设32 -bit）指针或其他一些聪明的黑客，但是一般来说这听起来是不可能的。

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.

本文描述了一个基于XOR的技巧：指针值，但我会考虑这是一个黑客（它对指针值进行按位运算）。

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屋！