Talk:XOR linked list
|WikiProject Computer science||(Rated Start-class, Mid-importance)|
This is a hoax, the only mention of it is this page and links to this page on programming forums asking to explain it. —Preceding unsigned comment added by 220.127.116.11 (talk) 19:20, 26 October 2009 (UTC)
- A technique that has been used for decades (especially when memory was scarce/expensive) is a hoax?
- I'm using it right now. For a hoax, it works amazingly well... --18.104.22.168 (talk) 13:48, 14 April 2011 (UTC)
Diagram and Example
This page needs a diagram and example. Will add myself if no one else does, eventually. Derrick Coetzee 22:14, 2 Oct 2004 (UTC)
I changed "conservative garbage collection schemes" to "most garbage collection schemes". The problem with so-called conservative collectors in this application is not that they are conservative, but that they are not conservative enough: they fail to over-estimate the set of reachable objects. Less-conservative schemes, namely those that rely on some kind of tagging, won't work any better. Cjoev 05:48, 27 April 2007 (UTC)
I think the given code, currently in S/360 assembly, should be rewritten in a more understandable assembly language, especially since the the S/360 opcodes are so weirdly named. Could be either x86, PPC or even a fake assembly for a non-existing machine, the point is just to replace "X R2,Link ; XR R1,R2" with something more akin to "load r2,link ; xor r1,r2".Habbit (talk) 12:37, 10 January 2008 (UTC)
Here's a fairly comprehensive explanation of the technique, including source code: http://rumkin.com/reference/algorithms/linked_list/
Comparison to Singly Linked List
I think there should be a comparison to Singly Linked Lists.
One of the main advantages of dbly-linked is that you can easily and quickly remove a given element from all the dbly linked lists it is in. With XOR linked list, this is not possible, you need the previous element.
The advantage XOR has over singly linked, is traversing in reverse.
Criticism - Use of register names
In Why does it work? "R1," "R2," etc. are referred to as if the reader can already be expected to know what those terms refer to. Since the reader may have skipped parts of the article, especially a section titled Features (i.e., with a title connoting superfluous information), this is not always the case, and the reader should not be expected to stop reading mid-explanation to find the definition of the terms. In fact, they're liable to ignore the article altogether for its use of jargon. Furthermore, computer science terminology such as register should be eliminated from the article except by mention as a technical term, as commonplace concepts such as a variable are sufficient to cover the material. ᛭ LokiClock (talk) 22:35, 28 July 2010 (UTC)
The article states “XOR of pointers is not defined in some contexts (e.g., the C language), although many languages provide some kind of type conversion between pointers and integers”. Neither part of this sentence is correct. First, I'm yet to see a single language where XOR between pointers is allowed: “not defined in some contexts” is a serious understatement here. Second, AFAIK, the only mainstream languages that have some support for converting pointers to/from integers are C and C++. I don't think it's fair to call these two “many”. 22.214.171.124 (talk) 01:06, 17 January 2012 (UTC)
pointer subtraction and C
The subsection "Note about implementations in C" is simply wrong. It is not legal to subtract two pointers in C (by ANSI or C99 standards) unless they both point to elements, or just past the end, of the same array. More general subtractions might work in practice after suitable casting, but they aren't conforming. Subtraction without casting will fail if the difference between the addresses is not a multiple of the node type. McKay (talk) 05:48, 21 June 2013 (UTC)