Realization of “get method” by splitting Linkedlist

I’m just studying Linkedlist topic and trying to implement different functions like remove, add and get.

Here is my implementation of get method to get the value of the element from double linked list. But what i was thinking about is to make the method more efficient by splitting it. What if I’m looking for the value on the 77th element? It must be quicker to go from the end.But how?

Something like “if i>size/2 {}”… But i’m stuck and cannot find any info about it and understand how to implement it.

public T get(int i) {
        if (i < 0 || i > size) {
            throw new IndexOutOfBoundsException();
        }
        Node<T> current = first;
        for (int a = 0; a < i; a++) {
            current = current.next;
        }
        return current.item;
    }

I think maybe i should take this part to a separate method or?

Node<T> current = first;
        for (int a = 0; a < i; a++) {
            current = current.next;

Is is possible? For any ideas and help would be very grateful.

Answer

Yes, in theory you could split the cases for get(i) such that if the index is greater than half the list you start iterating from the back. However, this has 2 pre-requisites in your implementation:

1. Your implementation needs to have a reference to the head as well as the tail (i.e. just like you have first, you also need last)
2. Your list needs to be doubly-linked so that you can traverse it backwards. (i.e you should be able to get the second last element from last)

If you don’t have the above 2 covered in your implementation, I’d recommend doing those first by learning about doubly-linked lists. The above changes will also affect your add() and remove() methods.

But assuming you have these 2 covered, you could modify get(i) to be like this:

public T get(int i) {
    if (i < 0 || i > size) {
        throw new IndexOutOfBoundsException();
    }
    if (i <= this.length()/2) {                       // I assume you have a length method
        Node<T> current = first;
        for (int a = 0; a < i; a++) {
            current = current.next;
        }
        return current.item;
    } else {
        Node<T> current = last;                       // last is the reference to the tail as mentioned above
        for (int a = this.length()-1; a > i; a--) {
            current = current.previous;               // a double-linked list has nodes with references to previous elements as well
        }
        return current.item;
    }
}