wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Find nth element from end of a SLL
        
(Message started by: -D- on Aug 6^th, 2002, 11:00am)

Title: Find nth element from end of a SLL
Post by -D- on Aug 6^th, 2002, 11:00am

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-

Title: Re: Find nth element from end of a SLL
Post by AlexH on Aug 6^th, 2002, 3:39pm

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.

Title: Re: Find nth element from end of a SLL
Post by -D- on Aug 6^th, 2002, 3:59pm

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-

Title: Re: Find nth element from end of a SLL
Post by AlexH on Aug 6^th, 2002, 5:26pm

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.

Title: Re: Find nth element from end of a SLL
Post by Paul Hsieh on Aug 6^th, 2002, 9:16pm

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.

Title: Re: Find nth element from end of a SLL
Post by S. Owen on Aug 7^th, 2002, 9:18am

Can you describe your solution involving rings of n+1 elements in more detail?

Title: Re: Find nth element from end of a SLL
Post by -D- on Aug 7^th, 2002, 9:43am

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-

Title: Re: Find nth element from end of a SLL
Post by AlexH on Aug 7^th, 2002, 10:17am

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.