Author |
Topic: Find nth element from end of a SLL (Read 7457 times) |
|
-D-
Guest
|
 |
Find nth element from end of a SLL
« on: Aug 6th, 2002, 11:00am » |
 Quote  Modify
 Remove
|
How about this:
keep 2 pointers. The first starts at the head and the second starts at the nth element. Then keep traversing with both one element at a time until the second falls of the end.
list_ptr *p1, *p2;
p1 = p2 = list.head
for( i = 0; i < n; ++i )
p2 = p2->next;
while( p2 )
{
p1 = p1->next;
p2 = p2->next;
}
-D-
|
|
 IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Find nth element from end of a SLL
« Reply #1 on: Aug 6th, 2002, 3:39pm » |
Quote Modify
|
This problem could really use some more context. Depending on what we're trying to optimizie we might want to do something like.
pointers A,B,C;
move C n steps into list and A to head of list.
while(1){
B=C
take up to n steps with C
if we hit end then move A forward whatever number of steps we took to hit end. Return.
if we don't hit end then let A=B
}
We could adapt this for small values of n so that we use some window size > n for efficiency in such cases.
|
|
IP Logged |
|
|
|
-D-
Guest
|
|
Re: Find nth element from end of a SLL
« Reply #2 on: Aug 6th, 2002, 3:59pm » |
Quote Modify
Remove
|
I think your solution would take like almost exactly as much time as mine. They practically do the same thing. I think you have to just eat up the time it takes to traverse elements (one memory lookup + one compare + one assignment).
Anyway, so far it's still linear. I don't know how much faster you can make it. I remember something from the linked list loop problem about hopping around 2^n units at a time, that might make it slightly more efficient if it could be utilized.
-D-
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Find nth element from end of a SLL
« Reply #3 on: Aug 6th, 2002, 5:26pm » |
Quote Modify
|
They are both linear just as any solution to this problem would be. Thats why I said the problem should be given better context. I'm imagining that the list is some big structure out in a long term storage that we want to work with, and I'm attempting to reduce accesses while using a constant amount of extra memory. My method only actually walks the length of the list once plus a "window" section a second time. If n is nearly as big as list size (M) then my method isn't any better (its basically identical in those cases), but if n < M/2 then we save over M/2 accesses to the list. So, worst case we get 3M/2 list accesses instead of 2M.
If we increase the number of pointers we're willing to use in the windows we could further improve the maximum number of access at the cost of more time spent messing with pointers. By using a bunch of adjacent windows we could get #accesses < M + n/k where k is the number of window pointers we're willing to use. We'd remain O(M) running time (with a pretty small constant). Clearly we can't beat M accesses since there is no way to do this problem without a list walk, but we can get close to that limit depending on how much memory we can use.
|
| « Last Edit: Aug 6th, 2002, 6:01pm by AlexH » |
IP Logged |
|
|
|
Paul Hsieh
Guest
|
|
Re: Find nth element from end of a SLL
« Reply #4 on: Aug 6th, 2002, 9:16pm » |
Quote Modify
Remove
|
Now suppose the linked list is stored on disk. (I.e., the raw number of accesses is important, and interleaving dijointed accesses can be really really bad.)
If n is small, then in this case, using a ring of size n+1 and just storing in a rotating fashion as you traverse (just once, with one pointer) and once you hit the end, return with the element that you would have overwritten next.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
|
Re: Find nth element from end of a SLL
« Reply #5 on: Aug 7th, 2002, 9:18am » |
Quote Modify
|
Can you describe your solution involving rings of n+1 elements in more detail?
|
|
IP Logged |
|
|
|
-D-
Guest
|
|
Re: Find nth element from end of a SLL
« Reply #6 on: Aug 7th, 2002, 9:43am » |
Quote Modify
Remove
|
He means use a ring buffer or circular queue (or in this case an array of pointers would work too). Assuming the array is stored in short term/medium term storage (aka cache/ram), you just store the last n locations and only need one pass through the list (stored in long term storage). Go until you run off the end of the list then look up the "first" (or next) element in the queue.
I think you would only need a buffer of size n unless you put the end of list token in the buffer also.
-D-
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Find nth element from end of a SLL
« Reply #7 on: Aug 7th, 2002, 10:17am » |
Quote Modify
|
Yes. This is the k=n case of the "multiple windows approach", so each window is size 1. I think you'll be using n+1 total pointers (n window pointers and 1 walking pointer in the terminology I used) either explicitly or implicitly. You want to check if the node->next = null before you put it in the ring if your ring is size n, so in order to avoid extra accesses you'll be storing the node->next somewhere when you compare it so you don't have to fetch it again when you put it in the ring if it turns out not to be null. Equivalently you could just use ring of size n+1 and only check for nul after you put the pointer in the ring.
|
| « Last Edit: Aug 7th, 2002, 10:26am by AlexH » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print