| 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 object-oriented 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: doubly-linked 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 |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
