get fifth element from last for a Singly linked list

[Kamal Ahmed]

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

// traverse the F_Ptr offset
for(;n!=0;n�,F_Ptr->next);
// now set the S_Ptr to trail the F_Ptr
S_Ptr = F_Ptr;
for(;F_Ptr!=NULL; S_Ptr=F_Ptr; F_Ptr=F_Ptr->next)
 
Now whe F_Ptr = Null, S_Ptr is just trailing behind right! it will be pointing to the n�th element from the last.
 

When F_Ptr reaches end (i.e., F_Ptr is NULL)
S_Ptr points to the 5th element from the last.
 

Thanks,

[Stan James]

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]

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]

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]

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]

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:

public Object getNth(int pos) 

Complete SinglyLinkedList Class:

public class SinglyLinkedList {
// instance vars
private ListNode myHead;
 
private ListNode myTail;
 
private int mySize;
 
/**
 * create an empty list pre: none<br>
 * post: size() = 0 O(1)
 */
public SinglyLinkedList() { // nothing to do since myHead, myTail
// austomatically set to null and
// mySize set to 0
}
 
/**
 * add an item to the end of this list pre: none<br>
 * post: size() = old size() + 1, get(size() - 1) = item<br>
 * O(1)
 * 
 * @param item
 *            the data to be added to the end of this list
 */
public void add(Object item) {
ListNode n = new ListNode(item, null);
if (size() == 0)
myHead = n;
else
myTail.setNext(n);
myTail = n;
mySize++;
}
 
/**
 * add an item at a specified position in the list pre: 0 <= pos <= size()<br>
 * post: size() = old size() + 1, get(pos) = item, all elements of<br>
 * O(N) the list with a positon >= pos have a position = old position + 1
 * 
 * @param item
 *            the data to add to the list
 * @param pos
 *            the position to insert the data at in the list
 */
public void add(Object item, int pos) {
assert 0 <= pos && pos <= size() : "Violation of precondition.";
 
// add at back?
if (pos == size())
add(item);
// add at front?
else if (pos == 0)
addFirst(item);
else {
ListNode n = new ListNode(item, null);
ListNode temp = getTo(pos - 1);
 
// point at node before spot to add
n.setNext(temp.getNext());
temp.setNext(n);
mySize++;
}
}
 
/**
 * change the data at the specified position in the list the old data at
 * that position is returns<br>
 * pre: 0 <= pos < size()<br>
 * post: size() = old size() + 1, get(pos) = item, return the old get(pos)<br>
 * O(N)
 * 
 * @param item
 *            the new item that will overwrite the old item
 * @param pos
 *            the position in the list to overwrite
 * @return the old data at the specified position
 */
public Object set(Object item, int pos) {
assert 0 <= pos && pos < size() : "Violation of precondition.";
 
ListNode temp = getTo(pos);
Object result = temp.getData();
temp.setData(item);
return result;
}
 
/**
 * get an element in the list pre: 0 <= pos < size()<br>
 * post: return the item at pos<br>
 * O(N)
 * 
 * @param pos
 *            specifies which element to get
 * @return the element at the specified position in the list
 */
public Object get(int pos) {
assert 0 <= pos && pos < size() : "Violation of precondition.";
 
if (pos == size() - 1)
return getLast();
ListNode temp = getTo(pos);
return temp.getData();
}
/**
 * Logic:
 * 
 * 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. 
 * @param pos
 * @return
 */
public Object getNth(int pos) {
assert 0 <= pos && pos < size() : "Violation of precondition.";
ListNode temp1 = myHead;
ListNode temp2 = myHead;
//offset = 5 , since the 5th element from the botton should be extracted

//Question: how do i traverse First and Second Pointer after n

return myTail.getData();
}
 
/**
 * remove an element in the list based on position pre: 0 <= pos < size()<br>
 * post: size() = old size() - 1, all elements of list with a positon > pos
 * have a position = old position - 1<br>
 * O(N)
 * 
 * @param pos
 *            the position of the element to remove from the list
 * @return the data at position pos
 */
public Object remove(int pos) {
assert 0 <= pos && pos < size() : "Violation of precondition.";
 
Object result;
if (pos == 0)
result = removeFirst();
else if (pos == size() - 1)
result = removeLast();
else {
ListNode temp = getTo(pos - 1);
result = temp.getNext().getData();
temp.setNext(temp.getNext().getNext());
mySize--;
}
return result;
}
 
/**
 * return the size of this list, the number of elements in it pre: none<br>
 * post: return the number of items in this list<br>
 * O(1)
 * 
 * @return the number of items in this list
 */
public int size() {
return mySize;
}
 
/*
 * private helper method. Get to to specified node in the list based on
 * position pre: 0 <= pos <= size() O(N)
 */
private ListNode getTo(int pos) {
assert 0 <= pos && pos <= size() : "Violation of precondition";
ListNode temp = myHead;
for (int i = 0; i < pos; i++)
temp = temp.getNext();
return temp;
}
 
/**
 * find the position of an element in the list pre: none<br>
 * post: return the index of the first element equal to item or a -1 if item
 * is not present<br>
 * O(N)
 * 
 * @param item
 *            the element to search for in the list
 * @return return the index of the first element equal to item or a -1 if
 *         item is not present
 */
public int indexOf(Object item) {
return indexOf(item, 0);
}
 
/**
 * find the position of an element in the list starting at a specified
 * position pre: 0 <= pos < size() post: return the index of the first
 * element equal to item starting at pos or a -1 if item is not present from
 * position pos onward
 * 
 * @param item
 *            the element to search for in the list
 * @param pos
 *            the position in the list to start searching from
 * @return starting from the specified position return the index of the
 *         first element equal to item or a -1 if item is not present
 *         between pos and the end of the list
 */
public int indexOf(Object item, int pos) {
assert 0 <= pos && pos < size() : "Violation of precondition.";
 
// move to position in list
ListNode temp = getTo(pos);
int index = 0;
boolean found = false;
while (temp != null && !found) {
if (item == null)
found = (temp.getData() == null);
else
found = item.equals(temp.getData());
temp = temp.getNext();
index++;
}
return found ? (index - 1) : -1;
}
 
/**
 * return the list to an empty state pre: none<br>
 * post: size() = 0<br>
 * O(1) when executed, O(N) when garbage collector runs (clean up N nodes)
 */
public void makeEmpty() {
myHead = null;
myTail = null;
mySize = 0;
}
 
/**
 * returns an iterator object for this list pre: none<br>
 * post: return an Iterator object for this List<br>
 * O(1)
 * 
 * @return an iterator object for this list
 */
public Iterator iterator() {
return new LLIteratorWithRemoveSlow();
}
 
/**
 * add item to the front of the list pre: none<br>
 * post: getFront() = item, size() = old size + 1<br>
 * O(1)
 * 
 * @param item
 *            the object to be added to the front of the list
 */
public void addFirst(Object item) {
ListNode n = new ListNode(item, myHead);
if (size() == 0)
myTail = n;
myHead = n;
mySize++;
}
 
/**
 * add item to the back of the list pre: none post: getLast() = item, size() =
 * old size + 1
 * 
 * @param item
 *            the object to be added to the back of the list
 */
public void addLast(Object item) {
add(item);
}
 
/**
 * remove and return the front item of the list pre: size() > 0<br>
 * post: size() = old size - 1<br>
 * O(1)
 * 
 * @return the object that used to be first in the list
 */
public Object removeFirst() {
assert size() > 0 : "Violation of precondition.";
 
Object data = myHead.getData();
myHead = myHead.getNext();
if (size() == 1)
myTail = null;
mySize--;
return data;
}
 
/**
 * remove and return the back item of the list pre: size() > 0 post: size() =
 * old size - 1
 * 
 * @return the object that used to be last in the list
 */
public Object removeLast() {
assert size() > 0 : "Violation of precondition.";
 
if (size() == 1)
return removeFirst();
// get to the second to last node
ListNode temp = getTo(size() - 2);
Object result = myTail.getData();
myTail = temp;
myTail.setNext(null);
mySize--;
return result;
}
 
/**
 * return the first item in the list pre: size() > 0
 * 
 * @return the first item in the list
 */
public Object getFirst() {
assert size() > 0 : "Violation of precondition.";
 
return myHead.getData();
}
 
/**
 * return the last item in the list pre: size() > 0
 * 
 * @return the last item in the list
 */
public Object getLast() {
assert size() > 0 : "Violation of precondition.";
 
return myTail.getData();
}
 
public String toString() {
String result = "[";
ListNode temp = myHead;
for (int i = 1; i < size(); i++) {
result += temp.getData() + ", ";
temp = temp.getNext();
}
result += (size() == 0) ? "]" : (temp.getData() + "]");
return result;
}
 
private class LLIteratorNoRemove implements Iterator {
private ListNode myCursor;
 
public LLIteratorNoRemove() {
myCursor = myHead;
}
 
public boolean hasNext() {
return myCursor != null;
}
 
public Object next() {
Object data = myCursor.getData();
myCursor = myCursor.getNext();
return data;
}
 
public void remove() {
throw new UnsupportedOperationException(
"this version of Iterator does not support remove");
}
}
 
private class LLIteratorWithRemoveSlow implements Iterator {
private ListNode myCursor;
 
private int myLastPosition;
 
public LLIteratorWithRemoveSlow() {
myCursor = myHead;
myLastPosition = -1;
}
 
public boolean hasNext() {
return myCursor != null;
}
 
public Object next() {
Object data = myCursor.getData();
myCursor = myCursor.getNext();
myLastPosition++;
return data;
}
 
// O(N) due to using O(N) remove from singlyLinkedList class
public void remove() {
SinglyLinkedList.this.remove(myLastPosition);
myLastPosition--;
}
 
}
 
}
 

[Justin Chu]

Assuming your singly linked list is implemented correct, here's an algorithm using some made up API.

Node rearPtr = list.head();
Node frontPtr = list.head();
int distance = 0;
while (frontPtr.next() != null){
  frontPtr = frontPtr.next();
  if (distance <5){
    distance++;
  } else {
    rearPtr = rearPtr.next();
  }
}
return distance != 5 ? null : rearPtr;

[Kamal Ahmed]

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.

ListNode f_ptr = myHead;
ListNode s_ptr = myHead;
/**
 * Here we are checking the opposite of the assert condition basically ,
 * the bounbdary conditions
 */
if (n < 0 || n >= size()) {
// error
return null;
}
if (size() < 1) {
// error
return null;
}
 
f_ptr = f_ptr.getNext();
 
for (; n > 0; n--) {
f_ptr = f_ptr.getNext();
}
 
while (f_ptr != null) {
f_ptr = f_ptr.getNext();
s_ptr = s_ptr.getNext();
}
return s_ptr.getData();
 

[Justin Chu]

Every time you called size() on a linked list, you are iterating thru the linked list.

[Kamal Ahmed]

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]

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]

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]

Jim,
Thanks, Excellent observations
I will take all of them into account.