什么是C中的内存有效的双向链表?

I had come across the term "Memory-Efficient Doubly Linked List" while reading a book on C Data structures. It just had one line saying that a memory-efficient doubly linked list uses less memory than a normal doubly linked list, but does the same job. Nothing more was explained, and no example was given. Just it was given that this has been taken from a journal, and "Sinha" in Brackets.

在阅读一本关于C数据结构的书时，我遇到了“内存效率双链表”这个术语。它只有一行表示一个内存效率高的双链表比一个普通的双链表占用更少的内存，但是做同样的工作。没有更多的解释，也没有给出任何例子。只是假设这是从一本日记中摘录的，括号里有“Sinha”。

After searching on Google, the closest I came to was this. But, I couldn't understand anything.

在谷歌上搜索之后，我最接近的是这个。但是，我什么都不懂。

Can someone explain me what is a Memory-Efficient Doubly Linked List in C? How is it different from a normal Doubly Linked List?

有人能解释一下什么是记忆效率高的双链表吗?它与普通的双链表有何不同?

EDIT: Okay, I made a serious mistake. See the link I had posted above, was the second page of the article. I didn't see that there was a first page, and thought the link given was the first page. The first page of the article actually gives an explanation, but I don't think it is perfect. It only talks of the basics concepts of Memory-Efficient Linked List or XOR Linked List.

编辑:好的，我犯了一个严重的错误。看我上面的链接，是文章的第二页。我没有看到第一页，我认为给出的链接是第一页。文章的第一页实际上给出了一个解释，但我认为它并不完美。它只讨论了内存高效链表或XOR链表的基本概念。

5 个解决方案

#1

I know that this is my second answer, but I think the explanation I provide here might be better, than the last answer. But note that even that answer is correct.

我知道这是我的第二个答案，但我认为我在这里给出的解释可能比最后一个更好。但请注意，即使这个答案是正确的。

---

---

A Memory-Efficient Linked List is more often called a XOR Linked List as this is totally dependent on the XOR Logic Gate and its properties.

一个内存效率高的链表通常被称为XOR链表，因为它完全依赖于XOR逻辑门及其属性。

---

Is it different from a Doubly Linked List?

Yes, it is. It is actually doing nearly the same job as a Doubly Linked List, but it is different.

是的,它是。它实际上做的几乎和双链表一样，但是它是不同的。

A Doubly-Linked List is storing two pointers, which point at the next and the previous node. Basically, if you want to go back, you go to the address pointed by the back pointer. If you want to go forward, you go to the address pointed by the next pointer. It's like:

一个双链表存储两个指针，指向下一个节点和上一个节点。基本上，如果你想要返回，你可以回到返回指针指向的地址。如果你想继续，你可以找到下一个指针指向的地址。这就像:

A Memory-Efficient Linked List, or namely the XOR Linked List is having only one pointer instead of two. This stores the previous address (addr (prev)) XOR (^) the next address (addr (next)). When you want to move to the next node, you do certain calculations, and find the address of the next node. This is the same for going to the previous node.It is like:

一个内存高效的链表，即XOR链表只有一个指针，而不是两个。这个商店前面的地址(addr(上一页))XOR(^)下一个地址(addr(下))。当您想要移动到下一个节点时，您需要进行某些计算，并找到下一个节点的地址。这和之前的节点是一样的。这就像:

---

How does it work?

The XOR Linked List, as you can make out from its name, is highly dependent on the logic gate XOR (^) and it's properties.

异或链表,你可以从它的名字,是高度依赖于逻辑门XOR(^)和它的属性。

It's properties are:

它的属性有:

|-------------|------------|------------|
|    Name     |   Formula  |    Result  |
|-------------|------------|------------|
| Commutative |    A ^ B   |    B ^ A   |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1)    |    A ^ 0   |     A      |
|-------------|------------|------------|
| None (2)    |    A ^ A   |     0      |
|-------------|------------|------------|
| None (3)    | (A ^ B) ^ A|     B      |
|-------------|------------|------------|

Now let's leave this aside, and see what each node stores:

现在让我们把这个放在一边，看看每个节点存储什么:

The first node, or the head, stores 0 ^ addr (next) as there is no previous node or address. It looks like:

第一个节点,或头部,商店0 ^ addr(下)没有前一个节点或地址。它看起来像:

Then the second node stores addr (prev) ^ addr (next). It looks like:

然后第二个节点存储addr(上一页)^ addr(下)。它看起来像:

The picture above shows node B, or the second node. A and C are address's of the third and first node. All the node, except the head and the tail, are like the above one.

上图显示了节点B，或者第二个节点。A和C是第三和第一个节点的地址。所有的节点，除了头和尾，都像上面一样。

The tail of the list, does not have any next node, so it stores addr (prev) ^ 0. It looks like:

列表的尾巴,没有下一个节点,所以商店addr(上一页)^ 0。它看起来像:

Before seeing how we move, let's see the representation of a XOR Linked List again:

在看到我们如何移动之前，让我们再看一下XOR链表的表示:

When you see

当你看到

it clearly means there is one link field, using which you move back and front.

它显然意味着有一个链接字段，你可以使用它前后移动。

Also, to note that when using a XOR Linked List, you need to have a temporary variable (not in the node), which stores the address of the node you were in before. When you move to the next node, you discard the old value, and store the address of the node you were in earlier.

另外，要注意，在使用XOR链表时，需要有一个临时变量(不在节点中)，它存储以前所在节点的地址。当您移动到下一个节点时，您将丢弃旧值，并存储您先前所在节点的地址。

Moving from Head to the next node

从头部移动到下一个节点

Let's say you are now at the first node, or at node A. Now you want to move at node B. This is the formula for doing so:

假设你现在在第一个节点，或者在节点a，现在你想在节点b移动，这是这样做的公式:

Address of Next Node = Address of Previous Node ^ pointer in the current Node

So this would be:

所以这将是:

addr (next) = addr (prev) ^ (0 ^ addr (next))

As this is the head, the previous address would simply be 0, so:

因为这是磁头，所以前面的地址就是0，所以:

addr (next) = 0 ^ (0 ^ addr (next))

We can remove the parentheses:

我们可以去掉括号:

addr (next) = 0 ^ 0 addr (next)

Using the none (2) property, we can say that 0 ^ 0 will always be 0:

使用(2)没有一个属性,我们可以总是会说0 ^ 0 0:

addr (next) = 0 ^ addr (next)

Using the none (1) property, we can simplify it to:

使用none(1)属性，可以化简为:

addr (next) = addr (next)

You got the address of the next node!

您得到了下一个节点的地址!

Moving from a node to the next node

从一个节点移动到下一个节点

Now let's say we are in a middle node, which has a previous and next node.

现在假设我们在一个中间节点，它有一个前节点和下一个节点。

Let's apply the formula:

我们应用公式:

Address of Next Node = Address of Previous Node ^ pointer in the current Node

Now substitute the values:

现在替换的值:

addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))

Remove Parentheses:

删除括号:

addr (next) = addr (prev) ^ addr (prev) ^ addr (next)

Using the none (2) property, we can simplify:

使用none(2)属性，我们可以简化:

addr (next) = 0 ^ addr (next)

Using the none (1) property, we can simplify:

使用none(1)属性，我们可以简化:

addr (next) = addr (next)

And you get it!

你得到它!

Moving from a node to the node you were in earlier

从一个节点移动到前面的节点

If you aren't understanding the title, it basically means that if you were at node X, and have now moved to node Y, you want to go back to the node visited earlier, or basically node X.

如果您不理解这个标题，它基本上意味着如果您在节点X，并且现在已经移动到节点Y，您希望返回到前面访问的节点，或者基本上是节点X。

This isn't a cumbersome task. Remember that I had mentioned above, that you store the address you were at in a temporary variable. So the address of the node you want to visit, is lying in a variable:

这不是一个繁琐的任务。记住，我在上面提到过，将地址存储在一个临时变量中。所以你想要访问的节点的地址在一个变量中:

addr (prev) = temp_addr

Moving from a node to the previous node

从一个节点移动到前一个节点

This isn't the same as mentioned above. I mean to say that, you were at node Z, now you are at node Y, and want to go to node X.

这和上面提到的不一样。我的意思是，你在结点Z，现在你在结点Y，想要去结点X。

This is nearly same as moving from a node to the next node. Just that this is it's vice-versa. When you write a program, you will use the same steps as I had mentioned in the moving from one node to the next node, just that you are finding the earlier element in the list than finding the next element.

这和从一个节点移动到下一个节点几乎是一样的。这是相反的。当您编写一个程序时，您将使用与我在从一个节点移动到下一个节点时所提到的步骤相同的步骤，只是您正在查找列表中较早的元素，而不是查找下一个元素。

I don't think I need to explain this.

我不认为我需要解释这个。

---

Advantages of XOR Linked List

• This uses less memory than a Doubly Linked List. Approximately 33% less.

  这比双链表的内存要少。大约减少了33%。

• It uses only one pointer. This simplifies the structure of the node.

  它只使用一个指针。这简化了节点的结构。

• As doynax said, a sub-section of a XOR can be reversed in constant time.

  正如doynax所说，x的一个子部分可以在恒定时间内反转。

---

Disadvantages of XOR Linked List

• This is a bit tricky to implement. It has higher chances of a failure, and debugging it is quite difficult.

  这有点难以实现。它有更高的失败的机会，并且调试它是相当困难的。

• All conversions (in case of an int) have to take place to / from uintptr_t

  所有转换(如果是int类型)都必须发生到/从uintptr_t

• You cannot just acquire the address of a node, and start traversing (or whatever) from there. You have to always start from the head or tail.

  您不能只获取节点的地址，然后从那里开始遍历(或其他)。你必须从头或尾开始。

• You cannot go jumping, or skipping nodes. You have to go one by one.

  不能跳转或跳过节点。你必须一个一个去。

• Moving requires more operations.

  运动需要更多的操作。

• It is difficult to debug a program which is using a XOR Linked List. It is much easier to debug a Doubly Linked List.

  使用XOR链表的程序很难调试。调试双链接列表要容易得多。

---

References

• http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/

  http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/

• https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/

  https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/

#2

This is an old programming trick that allows you to save memory. I don't think it's used much anymore, since memory is no longer as tight a resource as it was in the old days.

这是一个旧的编程技巧，允许您保存内存。我不认为它已经被大量使用了，因为记忆不再像过去那样是一种紧绷的资源。

The basic idea is this: In a conventional doubly-linked list, you have two pointers to adjacent list elements, a "next" pointer which points to the next element, and a "prev" pointer which points to the previous element. You can therefore traverse the list either forwards or backwards by using the appropriate pointers.

基本思想是这样的:在传统的双链表中，有两个指向相邻列表元素的指针，一个指向下一个元素的“next”指针，以及一个指向前一个元素的“prev”指针。因此，您可以使用适当的指针向前或向后遍历列表。

In the reduced-memory implementation, you replace "next" and "prev" with a single value, which is the bitwise exclusive-OR (bitwise-XOR) of "next" and "prev". You therefore reduce the storage for the adjacent element pointers by one half.

在缩减内存实现中，您将“next”和“prev”替换为单个值，该值是“next”和“prev”的位独占值，即“next”和“prev”的位独占值。因此，可以将相邻元素指针的存储减少一半。

Using this technique, it is still possible to traverse the list in either direction, but you need to know the address of the previous (or next) element to do so. For instance, if you are traversing the list in the forward direction, and you have the address of "prev", then you can get "next" by taking the bitwise-XOR of "prev" with the current combined pointer value, which is "prev" XOR "next". The result is "prev" XOR "prev" XOR "next", which is just "next". The same can be done in the opposite direction.

使用这种技术，仍然可以朝任何方向遍历列表，但是您需要知道前一个(或下一个)元素的地址。例如，如果您正向遍历列表，并且您有“prev”的地址，那么您可以通过使用当前组合指针值“prev”XOR“next”获得“next”。结果是“prev”XOR“prev”XOR“next”，也就是“next”。同样的事情也可以朝相反的方向去做。

The downside is that you can't do things like delete an element, given a pointer to that element, without knowing the address of either the "prev" or "next" element, since you have no context with which to decode the combined pointer value.

缺点是，在不知道“prev”或“next”元素的地址的情况下，不能删除元素(给定一个指向该元素的指针)，因为您没有上下文来解码组合的指针值。

The other downside is that this sort of pointer trick circumvents the normal data type checking mechanism that a compiler may expect.

另一个缺点是，这种指针技巧绕过了编译器可能期望的常规数据类型检查机制。

It's a clever trick, but in all honesty I see very little reason to use it these days.

这是一个聪明的诡计，但老实说，我现在几乎没有理由使用它。

#3

I would recommend seeing my second answer to this question, as it is much clearer. But I am not saying this answer is wrong. This is also correct.

我建议你看看我对这个问题的第二个回答，因为它要清楚得多。但我并不是说这个答案是错误的。这也是正确的。

---

---

A Memory-Efficient Linked List is also called a XOR Linked LIST.

一个内存高效的链表也称为XOR链表。

How Does It Work

A XOR (^) Linked List is a Link List in which instead of storing the next and back pointers, we just use one pointer to do the job of both the next and back pointers. Let's first see the XOR logic gates properties:

XOR(^)链表是一个链接列表中,而不是存储下一个指针,我们只使用一个指针做接下来的工作并返回指针。让我们先看看XOR逻辑门属性:

|-------------|------------|------------|
|    Name     |   Formula  |    Result  |
|-------------|------------|------------|
| Commutative |    A ^ B   |    B ^ A   |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1)    |    A ^ 0   |     A      |
|-------------|------------|------------|
| None (2)    |    A ^ A   |     0      |
|-------------|------------|------------|
| None (3)    | (A ^ B) ^ A|     B      |
|-------------|------------|------------|

Lets now take an example. We have a doubly linked list with four nodes: A, B, C, D. Here's how it looks:

让我们举个例子。我们有一个具有四个节点的双链列表:a、B、C、d。

If you see, each node has two pointers, and 1 variable for storing data. So we're using three variables.

如果您看到，每个节点都有两个指针和一个用于存储数据的变量。我们用了三个变量。

Now if you're have a Doubly Linked List with lot's of nodes, the memory it will be using will be too much. Too make it more efficient, we use a Memory-Efficient Doubly Linked List.

如果你有一个有很多节点的双链链表，它会使用太多内存。也使它更有效率，我们使用记忆效率双链表。

A Memory-Efficient Doubly Linked List is a Linked List in which we use just one pointer to move back and forth using XOR and it's properties.

一个具有内存效率的双链表是一个链表，在这个链表中，我们只用一个指针就可以使用XOR和它的属性来回移动。

Here's a pictorial representation:

这里有一个图示:

How do you move back and forth?

你如何前后移动?

You have a temporary variable (only one, not in the node). Let's say you're traversing the node from left to right. So you start at node A. In the pointer of node A, you store node B's address. You then move to node B. While moving to node B, in the temporary variable, you store node A's address.

您有一个临时变量(只有一个，不在节点中)。假设你从左到右遍历节点。从节点A开始，在节点A的指针中，存储节点B的地址。然后移动到节点B，同时移动到节点B，在临时变量中，存储节点A的地址。

The link (pointer) variable of node B has the address of A ^ C. You would take the previous node’s address (which is A) and XOR it with the current link field , giving you the address of C. Logically, this would look like:

节点B的链接(指针)变量的地址^你将前一节点的地址(A)和XOR它与当前链接,给你的地址c,从逻辑上讲,这样子:

A ^ (A ^ C)

Let's now simplify the equation. We can remove the parentheses and rewrite it because of the Associative property like:

现在我们化简方程。我们可以删除括号并重写它，因为有这样的联想性质:

A ^ A ^ C

We can further simplify this to

我们可以进一步化简为

0 ^ C

because of the second ("None (2)" as stated in the table) property.

因为第二个(如表中所述的“None(2)”)属性。

Because of the first ("None (1)" as stated in the table) property, this is basically

因为第一个(“None(1)”表示在表中)属性，这基本上是。

C

If you can't understand all this, just simply see the third property ("None (3)" as stated in the table).

如果您不能理解所有这些，只需查看表中所述的第三个属性(“None(3)”)。

Now, you got the address of node C. This will be the same process for going back.

现在，你得到了节点c的地址。

Let's say that you were going from node C to node B. You would store the address of node C in the temporary variable, do the process given above again.

假设从节点C到节点b，将节点C的地址存储在临时变量中，再次执行上面给出的过程。

NOTE: Everything like A, B, C are addresses. Thanks to Bathsheba for telling me to make it clear.

注意:A、B、C等都是地址。谢谢芭丝谢芭让我说清楚。

Disadvantages of XOR Linked List

XOR链表的缺点。

• As Lundin mentioned, all the conversions have to be done from/to uintptr_t.

  正如Lundin所提到的，所有的转换都必须由uintptr_t完成。

• As Sami Kuhmonen mentioned, you have to start from a well-defined start point, not just a random node.

  正如Sami Kuhmonen提到的，您必须从定义良好的起点开始，而不仅仅是一个随机的节点。

• You cannot just jump a node. You have to go in order.

  你不能仅仅跳过一个节点。你得按顺序走。

Also note that a XOR Linked List is not better than a doubly-linked list in most cases.

还要注意，在大多数情况下，XOR链接列表并不比双链接列表更好。

References

引用

• https://en.wikipedia.org/wiki/XOR_linked_list
• https://en.wikipedia.org/wiki/XOR_linked_list
• https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/
• https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/
• http://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1/
• http://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1/

#4

OK, so you've seen the XOR linked list, which saves you one pointer per item... but that is an ugly, ugly data structure, and far from the best you can do.

好吧，你已经看过XOR链表了，它为每一项节省了一个指针……但这是一个丑陋、丑陋的数据结构，远非你能做到的最好。

If you're worried about memory, it's almost always better to use a doubly-linked list with more than 1 element per node, like a linked list of arrays.

如果您担心内存的问题，那么最好使用每个节点都有一个以上元素的双链表，比如数组的链表。

For example, while an XOR linked list costs 1 pointer per item, plus the item itself, A doubly-linked list with 16 items per node costs 3 pointers for each 16 items, or 3/16 pointers per item. (the extra pointer is the cost of the integer that records how many items are in the node) That is less than 1.

例如，虽然XOR链表每项花费1个指针，加上项目本身，但每个节点有16个条目的双链表每16个条目花费3个指针，或每项3/16个指针。(额外的指针是记录节点中有多少项的整数的代价)小于1。

In addition to the memory savings, you get advantages in locality because all 16 items in the node are next to each other in memory. Algorithms that iterate through the list will be faster.

除了内存节省之外，您还可以在本地获得优势，因为节点中的所有16项都在内存中相邻。迭代列表的算法会更快。

Note that an XOR-linked list also requires you to allocate or free memory each time you add or delete a node, and that is an expensive operation. With the array-linked list, you can do better than this by allowing nodes to be less than completely full. If you allow 5 empty item slots, for example, then you only have allocate or free memory on every 3rd insert or delete at worst.

请注意，xor链表还要求您每次添加或删除节点时分配或释放内存，这是一项开销很大的操作。使用数组链表，您可以通过允许节点小于完全满来做得更好。例如，如果您允许5个空项目槽，那么最坏的情况是，您每3次插入或删除就只有分配或空闲内存。

There are many possible strategies for determining how and when to allocate or free nodes.

有许多可能的策略来决定如何分配和何时释放节点。

#5

You already got a pretty elaborate explanation of XOR linked list, I'll share a few more ideas on memory optimization.

您已经得到了关于XOR链接列表的详细解释，我将分享更多关于内存优化的想法。

1. Pointers normally take 8 bytes on 64 bit machines. It's necessary to address any point in RAM beyond 4GB addressable with 32 bit pointers.

   指针通常在64位机器上取8个字节。需要用32位指针来寻址内存中超过4GB的任何点。

2. Memory managers typically deal with fixed size blocks, not bytes. E.g. C malloc usually allocates within 16 byte granularity.

   内存管理器通常处理固定大小的块，而不是字节。C malloc通常在16字节的粒度范围内分配。

These two things imply that if your data is 1 byte, corresponding doubly linked list element will take 32 bytes (8+8+1, rounded up to the nearest 16 multiple). With XOR trick you can get it down to 16.

这两点意味着，如果数据是1字节，对应的双链列表元素将占用32字节(8+8+1，四舍五入到最近的16倍)。有了XOR技巧，你可以把它降到16。

However, to optimize even further, you can consider using your own memory manager, that: (a) deals with blocks at lower granuarity, such as 1 byte or maybe even go into bits, (b) has stricter limit on overall size. For example, if you know your list will always fit inside a continuous block of 100 MB, you only need 27 bits to address any byte within that block. Not 32 or 64 bits.

但是，为了进一步优化，您可以考虑使用自己的内存管理器:(a)处理低粒度的块，比如1个字节，或者甚至是比特，(b)对总体大小有更严格的限制。例如，如果您知道您的列表将始终适用于一个100 MB的连续块，那么您只需27位就可以处理该块中的任何字节。不是32或64位。

If you aren't developing a generic list class, but you know specific usage patterns for your application, in many cases implementing such memory manager may be an easy job. For example, if you know you will never allocate more than 1000 elements and each element takes 5 bytes, you can implement memory manager as 5000-byte array with a variable that holds index of the first free byte, and as you allocate extra element, you just take that index and move it forward by the allocated size. In this case your pointers will not be real pointers (like int*) but will be just indexes inside that 5000-byte array.

如果您没有开发泛型列表类，但是您知道应用程序的特定使用模式，那么在许多情况下实现此类内存管理器可能是一项简单的工作。例如,如果你知道你永远不会超过1000个元素,每个元素分配需要5个字节,可以实现内存管理器5000字节数组的变量保存指数第一次*字节,你分配额外的元素,你只需要分配指数和它向前移动的大小。在这种情况下，指针将不是真正的指针(比如int*)，而是5000字节数组中的索引。