wu :: forums
« wu :: forums - Find nth element from end of a SLL »

Welcome, Guest. Please Login or Register.
Dec 5th, 2024, 2:18am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: william wu, ThudnBlunder, Icarus, Eigenray, towr, SMQ, Grimbal)
   Find nth element from end of a SLL
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Find nth element from end of a SLL  (Read 7475 times)
-D-
Guest

Email

Find nth element from end of a SLL  
« on: Aug 6th, 2002, 11:00am »
Quote Quote Modify Modify Remove 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
***





   
Email

Posts: 156
Re: Find nth element from end of a SLL  
« Reply #1 on: Aug 6th, 2002, 3:39pm »
Quote Quote Modify 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

Email

Re: Find nth element from end of a SLL  
« Reply #2 on: Aug 6th, 2002, 3:59pm »
Quote Quote Modify Modify Remove 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
***





   
Email

Posts: 156
Re: Find nth element from end of a SLL  
« Reply #3 on: Aug 6th, 2002, 5:26pm »
Quote Quote Modify 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

Email

Re: Find nth element from end of a SLL  
« Reply #4 on: Aug 6th, 2002, 9:16pm »
Quote Quote Modify Modify Remove 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: male
Posts: 221
Re: Find nth element from end of a SLL  
« Reply #5 on: Aug 7th, 2002, 9:18am »
Quote Quote Modify Modify

Can you describe your solution involving rings of n+1 elements in more detail?
IP Logged
-D-
Guest

Email

Re: Find nth element from end of a SLL  
« Reply #6 on: Aug 7th, 2002, 9:43am »
Quote Quote Modify Modify Remove 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
***





   
Email

Posts: 156
Re: Find nth element from end of a SLL  
« Reply #7 on: Aug 7th, 2002, 10:17am »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board