Author |
Topic: Single-pointer double-linked list. (Read 2440 times) |
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
 |
Single-pointer double-linked list.
« on: May 22nd, 2004, 3:52pm » |
 Quote  Modify
|
Normally you implement a double-linked list by storing a forward and a backward pointer in each item.
I just came uppon a program that does something really weird to implement a double-linked list using only one pointer per item.
The items are allocated individually and you don't need to update any item in the process of traversing the list either way.
|
|
 IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Single-pointer double-linked list.
« Reply #1 on: May 24th, 2004, 3:38pm » |
Quote Modify
|
Must read "using only one pointer-sized data element per item", because it is not, strictly speaking, a pointer.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Single-pointer double-linked list.
« Reply #2 on: May 24th, 2004, 3:59pm » |
Quote Modify
|
Yes. Are you the one from the IOCCC, by chance?
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Single-pointer double-linked list.
« Reply #3 on: May 24th, 2004, 5:46pm » |
Quote Modify
|
on May 24th, 2004, 3:59pm, grimbal wrote:Yes. Are you the one from the IOCCC, by chance?
|
|
Naturally.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Single-pointer double-linked list.
« Reply #4 on: May 24th, 2004, 5:50pm » |
Quote Modify
|
No wonder, then. That's where I saw it.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Single-pointer double-linked list.
« Reply #5 on: May 25th, 2004, 1:49am » |
Quote Modify
|
I suppose you could XOR two pointers together
If you have A <-> B <-> C, and B hold (&A) XOR (&C), then you can get from B to C if you know &A, and from B to A if you know &C.
Of course when you have to start at B and find both ends, you can't get anywhere.. So that's probably not the solution you're looking for..
|
| « Last Edit: May 25th, 2004, 2:57am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Single-pointer double-linked list.
« Reply #6 on: May 25th, 2004, 2:48am » |
Quote Modify
|
on May 25th, 2004, 1:49am, towr wrote:| ...So that's probably not the solution you're looking for.. |
|
What a fiendishly well-obfuscated conclusion, towr. 
|
| « Last Edit: May 25th, 2004, 3:11am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Single-pointer double-linked list.
« Reply #7 on: May 25th, 2004, 3:04pm » |
Quote Modify
|
Yes, towr, you are right. That was it.
To navigate a list, you need to work with a pair of pointers (current,previous). To start at the head, you do (previous,current) = (0,head). To do a next, you do (previous,current) = (current,previous xor current->x). If you want to save a location in the middle of the list, you have to save both pointers. If you want to start from the end, just say (previous,current) = (0,tail). Now the same forward move goes backward. To turn around, you just xor the 'previous' pointer with current->x. Or simpler, swap previous and current.
Of course, C will ask you a lot of casts to make sure you really want to xor 2 pointers.
I found it funny to see a legitimate use for something as crazy as doing a XOR of pointers, which of course doesn't mean anything pointerwise.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print