how to reverse a doubly link list??

[pavitratandon]

How to reverse a doubly link list...?? its not traversing... its reversing the whole list...

plz help

[GaboonViper]

Since it's a doubly linked list, there is no point in reversing it. You can acces it from start to end and from end to start. But if you want to do it anyway all you have to do is swap the head and Tail and swap for every item in the list the Next and Previous.

[humptydumpty]

How to reverse a doubly link list...?? its not traversing... its reversing the whole list...
plz help

Then what's the Problem a Doubly Linked list is Something like
------------- ------------- -------------
| | | | <---+-- | | | <---+-- | | |
| 0 | a | --+---> | | b | --+---> | | c | 0 |
------------- ------------- -------------

So by taking the Pointer of tail you can traverse from tail to head hope this will help you.Here is a Simple Code just Check it out . i didn't check this code.

Example Code :-

#define PTR_XOR(a, b) (void*)( ((int)(a)) ^ ((int)(b)))
struct list_head* reverse(struct list_head* h) 
{
	if(h->next == h->prev)
		return h;

	do {
		h->prev = PTR_XOR(h->prev, h->next);
		h->next = PTR_XOR(h->prev, h->next);
		h->prev = PTR_XOR(h->prev, h->next);
		h = h->next;
	} while (h->next->prev != h);
	return h;
}

[luh@r]

can you explain what exactly the following does

#define PTR_XOR(a, b) (void*)( ((int)(a)) ^ ((int)(b)))

i guess a and b would be addresses

[humptydumpty]

I think u r more clear with Code if we make a doubly List next and prev contain the address of next and previos node . Hope this will help you to understand the code.

Thankyou

[binarybob0001]

luh@r PTR_XOR is a macro. It takes in two values a and b. It type casts a and b to integers and the XOR's them together. It then converts that value back to a pointer of type void*. Macros are nice because they are compact way of generating lots of redundant code, but do not overuse them. Macros are dangerous because they a fully global and not protected by namespaces. Over use of them can make code quite confusing.

[luh@r]

thanks for the explanation but my doubt was why and XOR is done on addresses?

[exterminator]

XOR swap algorithm

[SuperKoko]

humptydumpty : This macro is non-portable since there are a lot of machines where sizeof(int)!=sizeof(void*).
I think that 64 bits x86 machines have often 32 bits int and 64 bits pointers.

Moreover the XOR swap algorithm avoid temporary variables on most platforms, if, and only if, both values are in registers!
And, that's not the case with your program!
Your program will have pretty bad performances, except if the compiler is very very smart!

Once, I had showed the code generated by GCC 4 for the XOR swap algorithm, and, on x86 CPU, it is slow, and would be even much slower with a less good optimizer (the optimizer had been able to understand that the two variables were swaped, and used the XCHG x86 instruction), or with another CPU.

This XOR swap algorithm should only be used if:

• Both values are stored in registers (otherwise, there IS a temporary variable, and a classical "mov" swap is much better).
• The CPU has lacks registers (PowerPC, x86-64, 68000 have many registers).
  The 6502 CPU is a good example of CPU having very few registers.
  But since these registers are not general-purpose registers, I'm pretty sure that no compiler can use register variables on such CPU.
  In fact, all arithmetic operations are done with the A register, and can't be done with another register (the second operand must be memory).
  Thus, it is impossible to XCHG to registers without storing a temporary value in memory...
  There is no XOR X,Y nor XOR X,A nor even XOR A,X
  
  
• The CPU uses the same registers for pointers and for integers.
  68000 does use different registers for pointers and for integers, thus, the XOR swap algorithm requires a temporary integer register anyway...
  Moreover your algorithm assumes that sizeof(int)==sizeof(void*) which statically requires that the CPU have integers of the same size than generic pointers.
• The CPU has no builtin XCHG operation (x86 CPU have this swap operation).

Furthermore, std::swap is a standard algorithm, and compilers are allowed to write specially optimized code for that!
That's why std::swap is a reserved identifier.
So, you can assume that std::swap will be very efficient.

And, a classical swap, using "mov" operations is very likely to be efficiently optimized by the compiler, because such "mov" operations are extremely frequent (and time critical) in common programs.
CPU have also special optimizations for mov operations (avoiding dependencies).
That is:

mov edx,eax
add ecx,edx

May be executed in a single CPU cycle on some modern CPU.

The XOR swap operation should only be used in assembly language, on a CPU with very few general purpose registers, when you exactly know what you do...

[sunnypalsingh]

XOR trick doesn't even work for all the cases. XOR method breaks if you try to swap a variable with itself (same variable, not just same value).

[SuperKoko]

XOR trick doesn't even work for all the cases. XOR method breaks if you try to swap a variable with itself (same variable, not just same value).

Anyway, such scenario cannot happen if the code is REALLY optimized.
I mean that the XOR trick does require a temporary register when swapping memory objects.
Thus, the XOR trick should never ever be used on non-register variables (they should never be used on references).
And, register variables are never implicitly aliased...

Note : I may be wrong... But I think that there are no architecture allowing xor operation between two indirect memory operands without using a temporary register... In fact, RISC processors, usually don't even allow arithmetic operations between registers and memory operands.
Furthermore, I'm pretty sure that, from a ISO standard point-of-view, humptydumpty code does have temporary variables....
a = b ^ c; // the b ^ c expression yields a "temporary" r-value... which may be "optimized" if the compiler is smart enough, and that b and c are stored in appropriate locations

That is, except if the programmer do something like that:

xor eax,eax ; I guess that a programmer may think that it is an "optimized" version of XCHG eax,eax (which is the NOP operation)!
xor eax,eax
xor eax,eax ; But this programmer will notice that his program is buggy (it puts zero in eax).

Or (in C++):

int a;
a^=a;
a^=a;
a^=a;

What I mean, is that the aliasing problem can only happen when the programmer does not know what he does...