Find the nth element from the end of the node in LinkedList

Supposed that there is a linked list with this content:

  • 5: Rafsan Adam
  • 4: Andre
  • 3: Cindy Patricia
  • 2: Stephen D. Burd
  • 1: Nyoman D. Nata
  • 0: Freddy Aries

When I enter ‘3’ it will return the 3rd element from the end of the list, counted from 0, it returns “Cindy Patricia” which key itself is 3. The thing is, we can’t use key to determine the position as the key may not be integer.

This problem is a little bit tricky. But easy as this: we can set 2 pointer that links to the head/root of the list. The first pointer will go first to dive the linked list from 0..n. So, this pointer can be called explorer, finder, or whatever. When we do that, this finder will point to “Stephen D. Burd”.

Then, we go again but this time the range is from null to not null of the finder. When we first go, the finder will be “Stephen D. Burd” and that another pointer will point to “Rafsan Adam”. As long as the next pointer of finder is not null, we will make both the pointer to dive the list. At the end, the finder will points to null and the real link will stop and point to Cindy Patricia.

The implementation is like this:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package cc_latihan;

/**
 *
 * @author adampbe
 */
public class FindElementToEnd {
    public static void main (String[] args)
    {
    LinkedList ll = new LinkedList();

    ll.insert(0, new String("Freddy Aries"));
    ll.insert(1, new String("Nyoman D. Nata"));
    ll.insert(2, new String("Stephen D. Burd"));
    ll.insert(3, new String("Cindy Patricia"));
    ll.insert(4, new String("Andre"));
    ll.insert(5, new String("Rafsan Adam"));

    System.out.println("The content of linked list: ");
    System.out.println (ll);
    System.out.println("Will get the 3rd element from the end of node");

    //finder will help to get the real
    Node finder = ll.root;
    Node real = ll.root;
    for (int i=0; i<=3; i++)
    {
        if (finder == null)
        {
        return;
        }
        else finder = finder.next;
    }

    //now get the real.
    //if the finder is null, we have to stop
    //and that is the node we want
    while (finder != null)
    {
        System.out.println("Finder: " + finder);
        System.out.println("Real: " + real);
        finder = finder.next;
        real = real.next;
    }

    System.out.println("\nThe node you are looking for: " + real);

    }
}

Here is the program running:

Advertisements

One thought on “Find the nth element from the end of the node in LinkedList

  1. you can see that the finder is going down and down before it stuck with null and make the while loop discontinue itself which result in the exact position the 3rd node (which is: Cindy Patricia) is the node we want to be returned.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s