How to implement a double linked list with only one pointer?
如何实现一个只有一个指针的双链表?
It takes O(1) time to find the prev and next Node.
查找prev和下一个节点需要O(1)时间。
struct Node
{
int val;
Node* p;
};
6 个解决方案
#1
13
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.
您可能可以将两个16位偏移量压缩到单个(假定为32位)指针或其他“聪明的破解”所使用的空间中，但通常这听起来是不可能的。
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).
本文描述了一个基于XOR的技巧:获取指针值，但我认为这是一种技巧(它对指针值进行位运算)。
#2
10
There is a classic hack: store the XOR of the 2 pointers (Prev and Next) and when traveling the list you always have 1 of those at hand (you just came from there) and you can XOR it with the stored value to get the other pointer.
有一个经典的hack:存储两个指针的XOR (Prev和Next)，当你在旅行时，你手边总有1个指针(你刚从那里过来)，你可以用存储值XOR来获取另一个指针。
Needless to say that this won't work in a GC environment.
不用说，这在GC环境中是行不通的。
#4
6
One solution that has already been suggested is the XOR solution.
已经提出的一个解决方案是XOR解决方案。
Another solution is the "flipping sides" solution: If your problem is phrased the following way:
另一个解决方案是“侧翻”解决方案:如果你的问题是这样表述的:
You are given a pointer to the first element, and you would like to:
你被给予指向第一个元素的指针，你想:
- Go forward in the linked list i steps in O(i)
- 在O(i)的链表i中继续
- Go back in the linked list i steps in O(i)
- 回到O(i)中i步进的链表
- Add or remove items at the current location at O(1)
- 在O(1)处添加或删除当前位置的项目
So that there is always only one pointer to the linked list, and there is only one entry point (just going back and forward, like in 1 and 2), you could do the following:
只有一个指向链表的指针，只有一个入口点(就像在1和2中一样)，你可以这样做:
- Save two pointers: p1, p2
- 保存两个指针:p1, p2
- From the first pointer p1 you can go back, from the second pointer p2 you go forward.
- 从第一个指针p1你可以返回，从第二个指针p2你向前。
- The linked list items that are before p1 point backwards, whereas the items after p2 point forward.
- 在p1之前的链表项是向后的，而p2之后的项是向前的。
So your list would look like this:
所以你的列表是这样的:
p1 p2
| |
V V
i1 <- i2 <- i3 <- i4 i5 -> i6 -> i7
p1 points to the current element, p2 points to the next element, i1 ... i7 are the items in the list
p1指向当前元素，p2指向下一个元素，i1…i7是列表中的项。
Going forward is done in O(1), and so is going backward, by flipping pointers:
前进在O(1)中完成，后退在O(1)中完成:
Forward one step:
p1 p2
| |
V V
i1 <- i2 <- i3 <- i4 <- i5 i6 -> i7
Backward one step:
p1 p2
| |
V V
i1 <- i2 <- i3 i4 -> i5 -> i6 -> i7
This solution is better than the XOR solution in its readability and that it is more understandable for humans. The disadvantage is that you can not have several entry points to your linked list.
这个解决方案在可读性上比XOR解决方案要好，而且对人类来说更容易理解。缺点是你的链表不能有几个入口点。
#5
1
If sizeof(int) == sizeof(Node *) then have an intermediate node which contains a back pointer.
如果sizeof(int) = sizeof(Node *)，则有一个中间节点包含一个后指针。
E.g.
如。
(real node) -> (intermediate node) -> (read node) -> (etc)
(真实节点)->(中间节点)->(读取节点)->(等)
where (real node) contains a value and a pointer to the following (intermediate node), and (intermediate node) contains in val a back pointer to the previous intermediate node and in p a forward pointer to the following (read node).
其中(真实节点)包含一个值和一个指向下一个(中间节点)的指针，(中间节点)包含一个指向前一个中间节点的后一个指针，在p中包含指向下一个(读取节点)的前一个指针。
BTW, it's a stupid, stupid question. I can't see it teaches anything of value.
顺便说一句，这是个愚蠢而愚蠢的问题。我看它教不出任何有价值的东西。
#6
1
I recently stumbled on a nice approach to this problem in a book by Niklaus Wirth ("Algorithms + Data Structures = Programs"). It goes like this... You have a node, similar to the one you suggested, except that it does not aggregate a pointer to the next (nor to the previous) Node. Instead, you have a single member link that represents the distance (e.g. in units of sizeof(Node)) from the previous node (pointed to by Node* pPrev) in the chain to the next node (pointed to by Node* pNext) in the chain:
我最近在Niklaus Wirth(《算法+数据结构=程序》)的一本书中偶然发现了一个解决这个问题的好方法。是这样的……您有一个与您建议的节点类似的节点，但它不聚合指向下一个(或上一个)节点的指针。相反，您有一个成员链接，它表示链中从前一个节点(由节点* pPrev指向)到下一个节点(由节点* pNext指向)的距离(以sizeof(节点)为单位):
size_t link = pNext - pPrev;
So the node could look something like this:
所以这个结点可以是这样的
struct Node {
int val;
size_t link;
}
Then, to proceed from the present node, pCurrent, combined with the previous node pPrev, to the next Node* pNext by writing:
然后，将当前节点pCurrent与前一个节点pPrev合并，通过以下方式继续到下一个节点* pNext:
pNext = pPrev + pCurrent->link;
Similarly, you can traverse in the opposite direction by rearranging this equation:
同样，你也可以通过重新排列这个方程来逆行:
pPrev = pNext - pCurrent->link;
However, this approach is somewhat restricted by C/C++ pointer arithmetic because the difference of two pointers is only well defined if both point inside of the same memory block. So essentially, all of your nodes will have to be contained inside one huge array of Nodes.
然而，这种方法在某种程度上受到C/ c++指针算法的限制，因为两个指针的差异只有在同一个内存块内的两个点都能很好地定义。本质上，所有的节点都必须包含在一个巨大的节点数组中。
#1
13
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.
您可能可以将两个16位偏移量压缩到单个(假定为32位)指针或其他“聪明的破解”所使用的空间中，但通常这听起来是不可能的。
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).
本文描述了一个基于XOR的技巧:获取指针值，但我认为这是一种技巧(它对指针值进行位运算)。
#2
10
There is a classic hack: store the XOR of the 2 pointers (Prev and Next) and when traveling the list you always have 1 of those at hand (you just came from there) and you can XOR it with the stored value to get the other pointer.
有一个经典的hack:存储两个指针的XOR (Prev和Next)，当你在旅行时，你手边总有1个指针(你刚从那里过来)，你可以用存储值XOR来获取另一个指针。
Needless to say that this won't work in a GC environment.
不用说，这在GC环境中是行不通的。
#3
#4
6
One solution that has already been suggested is the XOR solution.
已经提出的一个解决方案是XOR解决方案。
Another solution is the "flipping sides" solution: If your problem is phrased the following way:
另一个解决方案是“侧翻”解决方案:如果你的问题是这样表述的:
You are given a pointer to the first element, and you would like to:
你被给予指向第一个元素的指针，你想:
- Go forward in the linked list i steps in O(i)
- 在O(i)的链表i中继续
- Go back in the linked list i steps in O(i)
- 回到O(i)中i步进的链表
- Add or remove items at the current location at O(1)
- 在O(1)处添加或删除当前位置的项目
So that there is always only one pointer to the linked list, and there is only one entry point (just going back and forward, like in 1 and 2), you could do the following:
只有一个指向链表的指针，只有一个入口点(就像在1和2中一样)，你可以这样做:
- Save two pointers: p1, p2
- 保存两个指针:p1, p2
- From the first pointer p1 you can go back, from the second pointer p2 you go forward.
- 从第一个指针p1你可以返回，从第二个指针p2你向前。
- The linked list items that are before p1 point backwards, whereas the items after p2 point forward.
- 在p1之前的链表项是向后的，而p2之后的项是向前的。
So your list would look like this:
所以你的列表是这样的:
p1 p2
| |
V V
i1 <- i2 <- i3 <- i4 i5 -> i6 -> i7
p1 points to the current element, p2 points to the next element, i1 ... i7 are the items in the list
p1指向当前元素，p2指向下一个元素，i1…i7是列表中的项。
Going forward is done in O(1), and so is going backward, by flipping pointers:
前进在O(1)中完成，后退在O(1)中完成:
Forward one step:
p1 p2
| |
V V
i1 <- i2 <- i3 <- i4 <- i5 i6 -> i7
Backward one step:
p1 p2
| |
V V
i1 <- i2 <- i3 i4 -> i5 -> i6 -> i7
This solution is better than the XOR solution in its readability and that it is more understandable for humans. The disadvantage is that you can not have several entry points to your linked list.
这个解决方案在可读性上比XOR解决方案要好，而且对人类来说更容易理解。缺点是你的链表不能有几个入口点。
#5
1
If sizeof(int) == sizeof(Node *) then have an intermediate node which contains a back pointer.
如果sizeof(int) = sizeof(Node *)，则有一个中间节点包含一个后指针。
E.g.
如。
(real node) -> (intermediate node) -> (read node) -> (etc)
(真实节点)->(中间节点)->(读取节点)->(等)
where (real node) contains a value and a pointer to the following (intermediate node), and (intermediate node) contains in val a back pointer to the previous intermediate node and in p a forward pointer to the following (read node).
其中(真实节点)包含一个值和一个指向下一个(中间节点)的指针，(中间节点)包含一个指向前一个中间节点的后一个指针，在p中包含指向下一个(读取节点)的前一个指针。
BTW, it's a stupid, stupid question. I can't see it teaches anything of value.
顺便说一句，这是个愚蠢而愚蠢的问题。我看它教不出任何有价值的东西。
#6
1
I recently stumbled on a nice approach to this problem in a book by Niklaus Wirth ("Algorithms + Data Structures = Programs"). It goes like this... You have a node, similar to the one you suggested, except that it does not aggregate a pointer to the next (nor to the previous) Node. Instead, you have a single member link that represents the distance (e.g. in units of sizeof(Node)) from the previous node (pointed to by Node* pPrev) in the chain to the next node (pointed to by Node* pNext) in the chain:
我最近在Niklaus Wirth(《算法+数据结构=程序》)的一本书中偶然发现了一个解决这个问题的好方法。是这样的……您有一个与您建议的节点类似的节点，但它不聚合指向下一个(或上一个)节点的指针。相反，您有一个成员链接，它表示链中从前一个节点(由节点* pPrev指向)到下一个节点(由节点* pNext指向)的距离(以sizeof(节点)为单位):
size_t link = pNext - pPrev;
So the node could look something like this:
所以这个结点可以是这样的
struct Node {
int val;
size_t link;
}
Then, to proceed from the present node, pCurrent, combined with the previous node pPrev, to the next Node* pNext by writing:
然后，将当前节点pCurrent与前一个节点pPrev合并，通过以下方式继续到下一个节点* pNext:
pNext = pPrev + pCurrent->link;
Similarly, you can traverse in the opposite direction by rearranging this equation:
同样，你也可以通过重新排列这个方程来逆行:
pPrev = pNext - pCurrent->link;
However, this approach is somewhat restricted by C/C++ pointer arithmetic because the difference of two pointers is only well defined if both point inside of the same memory block. So essentially, all of your nodes will have to be contained inside one huge array of Nodes.
然而，这种方法在某种程度上受到C/ c++指针算法的限制，因为两个指针的差异只有在同一个内存块内的两个点都能很好地定义。本质上，所有的节点都必须包含在一个巨大的节点数组中。