File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

get fifth element from last for a Singly linked list

 
Kamal Ahmed
Ranch Hand
Posts: 91
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
Could anyone help me with a method for a Singly Linked List which gets fifth element from last linked list

I have the logic here:

1) have two ptrs. F_Ptr & S_Ptr.
2) Let the ptrs point to the START.
3) Take n as the offset.
4) Start traversing the S_Ptr after the F_Ptr after n.

suppose you want to find 5 element from the last of the list.

In the above case.

1) n = 5 // 5th element from the last
2) check atleast this many elements are there in the list before beginging


Thanks,
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Google on "Circular buffer". The Wikipedia article looks ok. That's a neat way to keep the last 5. You can make a one-line bit of arithmetic to get from the last index put into the buffer to the oldest index, which will be the 5th from the end. Take a shot at some code and show us what you make!
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This looks like essentially the same problem that was asked about here - if we ignore all the distractions about java.util.LinkedList and just consider the algorithm given by Nitesh and clarified by EFH. Here in this thread, the original poster seems to be doing something much like that... in some other language; I'm not sure what it is. But, what's the question? It looks like you have a good understanding of the problem - what part are you asking about?
 
Kamal Ahmed
Ranch Hand
Posts: 91
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jim,
Thanks for your post. Here is the requirement:

Write a function that would: return the 5th element from the end in a singly linked list of integers, in one pass,

Thanks,
-Kamal.
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OK. And in your post, you give an algorithm which looks to me like it should work. (Except I can't tell what language you're using.) Have you tried it? What happened? What specific part of the problem are you stuck on?
 
Kamal Ahmed
Ranch Hand
Posts: 91
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jim,

I am using Java to implement this: and here is the complete class.
The problem i am facing is how do i code the method:




Complete SinglyLinkedList Class:

 
Justin Chu
Ranch Hand
Posts: 209
1
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Assuming your singly linked list is implemented correct, here's an algorithm using some made up API.

 
Kamal Ahmed
Ranch Hand
Posts: 91
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Chu,
Your idea is right, but it does not work somehow, i get "null" for every key value in the link, but i have solved this, and here is the code for reference.

 
Justin Chu
Ranch Hand
Posts: 209
1
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Every time you called size() on a linked list, you are iterating thru the linked list.
 
Kamal Ahmed
Ranch Hand
Posts: 91
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
true, but this is like a pre processor test, before walking the list with the first and second pointers. How is this called within the iteration? Maybe i am missing something?
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't think he's saying it's called within an iteration. But every time someone calls getNth(), they will loop through the whole list three times - twice with calls to size(), and once in the loop in getNth code. It should be possible to eliminate the first two iterations (in size) and make this considerably faster. If the size() were 0 - wouldn't that mean f_ptr would be null? Couldn't you check that instead? Also, if n were >= size(), wouldn't f_ptr turn to null during the iteration of the first n elements? I think that by adding a couple more checks for null, you can avoid the calls to size() completely.
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A couple more points:

It's not like a pre-processor test if it happens at runtime, and it happens every single time the method is called. It may be similar in some ways, but the point here is to avoid unnecessary work for the processor at runtime.

Also, names like f_ptr and s_ptr look very much like they come from C or some other language. Java doesn't use the term "pointer" at all. If you're programming in Java, it will probably be less confusing to others if you try to avoid C-specific terminology. And what are f and s? First and second, maybe? You could call them something like ref1 and ref2 - "reference" is more Java-like than "pointer". I would probably not even mention that they're references, and concentrate on their roles. Maybe "leader" and "follower" - or "followerN" or "nthFollower", since the role of the latter is to follow N steps after the leader. Just some ideas...
 
Kamal Ahmed
Ranch Hand
Posts: 91
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jim,
Thanks, Excellent observations
I will take all of them into account.
 
Consider Paul's rocket mass heater.
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic