This week's book giveaway is in the OCPJP forum.
We're giving away four copies of OCA/OCP Java SE 7 Programmer I & II Study Guide and have Kathy Sierra & Bert Bates on-line!
See this thread for details.
The moose likes Java in General and the fly likes get fifth element from last for a Singly linked list Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCA/OCP Java SE 7 Programmer I & II Study Guide this week in the OCPJP forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "get fifth element from last for a Singly linked list" Watch "get fifth element from last for a Singly linked list" New topic
Author

get fifth element from last for a Singly linked list

Kamal Ahmed
Ranch Hand

Joined: Feb 15, 2005
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,
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
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!


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
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?


"I'm not back." - Bill Harding, Twister
Kamal Ahmed
Ranch Hand

Joined: Feb 15, 2005
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
Sheriff

Joined: Jan 30, 2000
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

Joined: Feb 15, 2005
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:




Complete SinglyLinkedList Class:

Justin Chu
Ranch Hand

Joined: Apr 19, 2002
Posts: 209
    
    1
Assuming your singly linked list is implemented correct, here's an algorithm using some made up API.

Kamal Ahmed
Ranch Hand

Joined: Feb 15, 2005
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

Joined: Apr 19, 2002
Posts: 209
    
    1
Every time you called size() on a linked list, you are iterating thru the linked list.
Kamal Ahmed
Ranch Hand

Joined: Feb 15, 2005
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
Sheriff

Joined: Jan 30, 2000
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
Sheriff

Joined: Jan 30, 2000
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

Joined: Feb 15, 2005
Posts: 91
Jim,
Thanks, Excellent observations
I will take all of them into account.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: get fifth element from last for a Singly linked list