Talk:XOR linked list

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

Hoax[edit]

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 83.100.165.91 (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... --80.66.10.152 (talk) 13:48, 14 April 2011 (UTC)
I removed the banner of lacking sources, the data structure is based solely on XOR, its a direct application of XOR properties (commutativity, etc) , its not original research. — Preceding unsigned comment added by 98.248.39.96 (talk) 07:08, 24 November 2013 (UTC)

Diagram and Example[edit]

This page needs a diagram and example. Will add myself if no one else does, eventually. Derrick Coetzee 22:14, 2 Oct 2004 (UTC)

Proposed merge[edit]

See Talk:XOR swap algorithm#Proposed merge of XOR and ADD/SUB article pairs.

XOR links and GC[edit]

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)

Assembly instructions[edit]

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)


Links[edit]

Here's a fairly comprehensive explanation of the technique, including source code: http://rumkin.com/reference/algorithms/linked_list/

And this one is also pretty good: http://www.linuxjournal.com/article/6828 --Parallelized (talk) 13:33, 17 February 2009 (UTC)

Comparison to Singly Linked List[edit]

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.

BWaIdKgIer (talk) 07:26, 26 September 2009 (UTC)

Criticism - Use of register names[edit]

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)

Weasel words[edit]

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”. 78.131.41.49 (talk) 01:06, 17 January 2012 (UTC)

pointer subtraction and C[edit]

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)