View previous topic :: View next topic 
Author 
Message 
 furtivefelon
 Joined: 25 Dec 2006  Posts: 5  :   Items 

Posted: Mon Dec 25, 2006 3:45 am Post subject: some help with DLX and knuth's paper 


hello, i have a question regarding doubly linked list, i understand in a general sense what is a doubly linked list, its a list where each element is linked to the previous and next element in that same list.
However, in knuth's paper, he used the following notation in the beginning:
L[R[x]] < L[x], R[L[x]] < R[x] removes the x from the list
Now i don't quite understand what does he mean by the error, does he mean insert R[x] into R[L[x]] and vise versa? If he does, can someone please explain exactly how, since i didn't quite get it, thanks alot! 

Back to top 


 Ruud Site Admin
 Joined: 17 Sep 2005  Posts: 708  :  Location: Netherlands  Items 

Posted: Mon Dec 25, 2006 1:04 pm Post subject: 


Hi,
your interpretation is correct. "<" must be read as "=" or ":=" depending on the programming language you use.
For a more objectoriented version, read: http://www.sudopedia.org/wiki/Dancing_Links
Ruud 

Back to top 


 furtivefelon
 Joined: 25 Dec 2006  Posts: 5  :   Items 

Posted: Tue Dec 26, 2006 3:44 am Post subject: 


nice page! thanks alot for the link 

Back to top 


 furtivefelon
 Joined: 25 Dec 2006  Posts: 5  :   Items 

Posted: Tue Dec 26, 2006 3:57 am Post subject: 


mmm.. just wondering, why would it be L[R[x]] instead of just x (afterall, the element to the left of the right element of x is just x right?)
I'm pretty confused about that..
Thanks again! 

Back to top 


 Pat
 Joined: 06 Sep 2006  Posts: 128  :   Items 

Posted: Thu Dec 28, 2006 2:50 pm Post subject: re: doublylinked list 


furtivefelon wrote:  mmm.. just wondering, why would it be L[R[x]] instead of just x (afterall, the element to the left of the right element of x is just x right?)
I'm pretty confused about that..
Thanks again! 
hi furtivefelon,
instead of this 
Quote: 
to remove x from the list 
Code: 
L [ R [x] ] := L [x]
R [ L [x] ] := R [x]


 try using intermediate variables for better understanding 
Quote: 
to remove x from the list 
Code: 
my_Right := R [x] ; L [ my_Right ] := L [x]
my_Left := L [x] ; R [ my_Left ] := R [x]


does this make more sense ?


Back to top 


 MCondron
 Joined: 17 Jul 2006  Posts: 35  :  Location: Houston, TX  Items 

Posted: Fri Dec 29, 2006 3:57 pm Post subject: 


This may also help clear it up...
I think the L[] R[] notation is confusing. They look like function calls or operators or something like that, but they actually are meant to represent data structure members, like this (using the C notation '>' for a structure pointer)
Code:  x>right>left = x>left
x>left>right = x>right 
In words, the first assignment makes "left" pointer of the object to x's right point to the object to x's left. The second assignment does similarly for the right. Together, these two assignments remove x from the linked list without destroying x's sense of where in the list it belongs since it's own left and right pointers still point to the correct place. That makes it really easy to put x back into the list:
Code:  x>right>left = x
x>left>right = x 
It can be a little confusing at first. Try drawing out the pointers on paper and it will become clear.
Mike 

Back to top 


