What is an efficient dual-memory list in C?

Question

When reading a book on C data structures, I came across the term "Efficient memory duplicated list." It just had one line, which said that a doubly linked list with memory had less memory than a regular doubly linked list, but it did the same job. Nothing more was explained, and not a single example was given. It was just given that it was taken from the magazine and "Sinha" in brackets.

After searching Google the closest I came to this . But I couldn’t understand anything.

Can someone explain to me what a dual memory efficient list in C is? How is it different from a regular double linked list?

EDIT: Well, I made a serious mistake. See The link I posted above was the second page of the article. I did not see that there was a first page, and thought that this link was the first. The first page of the article does provide an explanation, but I don’t think it is perfect. This is just the basics of the concepts of the Memory-Efficient Linked List or XOR Linked List.

Answer 1

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

---

---

A efficient memory-related list is most often called the XOR Linked List , since it is completely dependent on the logical Gate XOR and its properties.

---

Is it different from a doubly linked list?

Yes it is. It actually does almost the same job as the Doubly Linked List, but it is different.

A Doubly-Linked List stores two pointers that point to the next and previous node. Basically, if you want to return, you will go to the address indicated by the back pointer. If you want to go forward, you go to the address indicated by the next pointer. Like it:

A memory-linked list of links , namely the XOR linked list has 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 perform certain calculations and find the address of the next node. This is the same for going to the previous node. It looks like:

---

How it works?

The linked XOR list , as you can see from its name, is highly dependent on the XOR (^) logic element and its properties.

Its properties:

 |-------------|------------|------------| | 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 leave that aside and see what each node stores:

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

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

The figure above shows node B, or the second node. A and C are the address of the third and first node. All node except the head and tail, like the previous ones.

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

Before we see how we are moving, we will again see a view of the linked XOR list:

When you see

this clearly means that there is one link field with which you move back and forth.

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

Going from chapter to next node

Say you are now on the first node or in node A. Now you want to switch to node B. This is the formula for this:

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

So this will be:

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

Since this is the head, the previous address would be just 0, therefore:

 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:

 addr (next) = 0 ^ addr (next) 

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

 addr (next) = addr (next) 

You have received the address of the next node!

Going from node to next node

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

We apply the formula:

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

Now replace 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:

 addr (next) = 0 ^ addr (next) 

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

 addr (next) = addr (next) 

And get it!

Moving from node to node, you were in the previous

If you don’t understand the title, it basically means that if you were in node X and now moved to node Y, you want to return to the node you visited earlier, or basically node X.

This is not a cumbersome task. Remember that I mentioned above that you are storing the address at which you were in the temporary variable. So the node address you want to visit lies in the variable:

 addr (prev) = temp_addr 

Go from node to previous node

This is not the same as above. I want to say that you were in node Z, now you are in node Y and want to go to node X.

This is almost the same as moving from node to next node. It's just the opposite. When you write a program, you will use the same steps that I mentioned when moving from one node to the next node, just so that you find an earlier item in the list than searching for the next item.

I don’t think I need to explain this.

---

Benefits of XOR Linked List

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

• Only one pointer is used. This simplifies the structure of the node.

• As doinax said, the XOR submode can be reversed in time.

---

Disadvantages of XOR Linked List

• This is a little difficult to implement. It has a higher chance of failure, and debugging is rather complicated.

• All conversions (in case of int) should be performed in / from uintptr_t

• You cannot just get the node address and start moving (or something else) from there. You should always start with the head or tail.

• You cannot jump or skip nodes. You have to go one by one.

• More operations are required to move.

• It is difficult to debug a program using a linked XOR list. It is much easier to debug a double list.

---

References

• 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/

Answer 2

This is an old software trick that allows you to save memory. I do not think that he used much more, since memory is no longer as resource-intensive as in the old days.

The basic idea is this: in a regular doubly linked list, you have two pointers to adjacent elements of the list, a “next” pointer that points to the next element, and a “prev” pointer that points to the previous element, so you can move the list forward or back with the appropriate pointers.

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

Using this method, you can still move the list in any direction, but for this you need to know the address of the previous (or next) element. For example, if you move the list in the forward direction and you have the address "prev", you can get the "next" by taking the bit-XOR "prev" with the current combined pointer value, which is "prev" XOR "next". The result is "prev" XOR "prev" XOR "next", which is simply "next". The same can be done in the opposite direction.

The disadvantage is that you cannot do such things as deleting an element by pointing to that element without knowing the address of the "prev" or "next" element, since you do not have the context to decode the combined value of the pointer.

Another drawback is that this pointer trick bypasses the usual data type checking mechanism that the compiler can expect.

This is a smart trick, but to be honest, I see very few reasons to use it these days.

Answer 3

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

---

---

A efficient memory-related list is also called XOR Linked LIST .

How it works

A XOR (^) A linked list is a list of links in which, instead of storing the next and back pointers, we simply use the one pointer to do the next and back pointers. First, consider the properties of the logical gate 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 | |-------------|------------|------------| 

Now let's take an example. We have a double list with four nodes: A, B, C, D. Here's what it looks like:

If you see, each node has two pointers and 1 variable for storing data. Therefore, we use three variables.

Now, if you have a Doubly Linked List with many nodes, the memory it will use will be too large. To make it more efficient, we use Efficient Bidirectional List with memory .

A Efficient memory bi-directional list is a linked list in which we use only one pointer to move forward and backward using the XOR properties and its properties.

Here's a pictorial representation:

How do you move back and forth?

You have a temporary variable (only one, not node). Say you cross node from left to right. So, you start with node A. In the node A pointer, you store the address of node B. Then go to node B. Moving to node B, in the temporary variable, you store node address A.

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

 A ^ (A ^ C) 

Now simplify the equation. We can remove the parentheses and rewrite them due to the associative property:

 A ^ A ^ C 

We can simplify this for

 0 ^ C 

because of the second (property "No (2)" as indicated in the table ".

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

 C 

If you cannot understand all this, just look at the third property ("None (3)", as indicated in the table).

You have now received the address of node C. This will be the same process for returning.

Say you switched from node C to node B. You would save the address of node C in a temporary variable, repeat the process described above.

NOTE. All, like A , B , C , are addresses. Thanks to Batsheva for telling me to make it clear.

Disadvantages of XOR Linked List

• As Lundin mentioned, all conversions must be performed from / to uintptr_t .

• As Sami Kuhmon said, you should start from a well-defined starting point, and not just from an arbitrary node.

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

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

References

• https://en.wikipedia.org/wiki/XOR_linked_list
• 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/

Answer 4

OK, so you saw a linked XOR list that stores one pointer to an element ... but this is an ugly, ugly data structure and not all that you can do.

If you are worried about memory, it is almost always better to use a doubly linked list with more than 1 element per node, as a linked list of arrays.

For example, while a linked XOR list costs 1 pointer to an element, plus the element itself, a doubly linked list with 16 elements per node costs 3 pointers for every 16 elements or 3/16 pointers to an element. (an extra pointer is the value of an integer that records how many elements are in the node). It is less than 1.

In addition to saving memory, you get advantages in locality, since all 16 elements in a node are next to each other in memory. Algorithms going through the list will be faster.

Note that the XOR-related list also requires you to allocate or free memory each time you add or remove a node, and this is an expensive operation. With an array-linked list, you can do this better if the nodes are smaller than fully populated. For example, if you allow 5 slots with empty cells, then you only have to allocate or free memory on every third insert or delete in the worst case.

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

Answer 5

You already have a fairly detailed explanation of the linked XOR list, I will share a few more ideas on memory optimization.

• Pointers usually accept 8 bytes on 64-bit machines. You must access any point in RAM that exceeds 4 GB with 32-bit pointers.

• Memory managers usually deal with fixed-size blocks, rather than bytes. For example. C malloc typically allocates within 16 bytes of granularity.

These two things mean that if your data is 1 byte, the corresponding double-connected element will accept 32 bytes (8 + 8 + 1, rounded to the nearest 16 multiple). With the XOR stunt, you can get it up to 16.

However, to further optimize the work, you can use your own memory manager, which: (a) deals with blocks with less granularity, for example, 1 byte, or maybe even goes into bits, (b) has more stringent restrictions to total size. For example, if you know that your list will always be in a continuous block of 100 MB in size, you only need 27 bits to access any byte inside this block. Not 32 or 64 bit.

If you are not developing a general list class, but know specific usage patterns for your application, in many cases implementing such a memory manager can be an easy task. For example, if you know that you will never allocate more than 1000 elements, and each element occupies 5 bytes, you can implement the memory manager as a 5000-byte array with a variable that contains the index of the first free byte, and since you allocate an additional element, you just take this index and move it forward in the selected size. In this case, your pointers will not be valid pointers (e.g. int *), but will only be indexes inside this 5000 byte array.