programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Liutauras Vilda
• Tim Cooke
• Jeanne Boyarsky
• Bear Bibeault
Sheriffs:
• Knute Snortum
• paul wheaton
• Devaka Cooray
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Ron McLeod
• Piet Souris
• Ganesh Patekar
Bartenders:
• Tim Holloway
• Carey Brown
• salvin francis

# get fifth element from last for a Singly linked list

Ranch Hand
Posts: 91
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,

(instanceof Sidekick)
Posts: 8791
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!

Wanderer
Posts: 18671
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
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
Posts: 18671
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
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:

Ranch Hand
Posts: 209
1

Kamal Ahmed
Ranch Hand
Posts: 91
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
Every time you called size() on a linked list, you are iterating thru the linked list.

Kamal Ahmed
Ranch Hand
Posts: 91
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
Posts: 18671
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
Posts: 18671
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
Jim,
Thanks, Excellent observations
I will take all of them into account.

 A berm makes a great wind break. And Iwe all like to break wind once in a while. Like this tiny ad: Enterprise-grade Excel API for Java https://products.aspose.com/cells/java