LinkedList Get method

Question

I have a get method for my singly linked list and they work fine but my instructor told me that he wants me to cut down on the code because I have too many special cases. Problem being is that when I try to cut out some parts of my code, the code no longer works as it's supposed to.

The code written from me:

public E get(int index) {
    Node<E> f = first;

    // If index is bigger / smaller than Linked List size throw IndexOutOfBounds
    if (index > size || index < 0){
        throw new IndexOutOfBoundsException();
    }


    // Index Less than size and is not the first or last node.
    if (index < size && index > 0) {
        for (int i = 0; i < index; i++) {
            f = f.next;
        }
        return f.getValue();
    }

    // If the Linked List is empty + Index = 0 return null
    if (first == null && index == 0) {
        return null;
    }

    // If Linked List is not empty and index = 0 return first value
    if (index == 0) {
        return first.getValue();
    }

    // If index = end of list
    if (index == size) {
        return last.getValue();
    }


    // Return null if not found.
    return null;

}

So he tells me that I'm putting too much thought into it and there are only two cases needed, if the index is valid or not valid; which I agree with him on, so I try to shorten my code to this:

Node<E> f = first;

// If index is bigger / smaller than Linked List size throw IndexOutOfBounds
if (index > size || index < 0){
    throw new IndexOutOfBoundsException();
}


// Index Less than size and is not the first or last node.
if (index <= size && index >= 0) {
    for (int i = 0; i < index; i++) {
        f = f.next;
    }
}
return f.getValue();

and for my test cases I'm using a Linked List with these values:

[Frank, George, Josh, Jim, Marry, Susie, John, Jim, Dakota, Levi, Jackson, Jeff, Walt, Matt]

and my test cases are as follows in my test class:

System.out.println("Get Method Test ----------------------------");
System.out.println("First Index: " + ll.get(0));
System.out.println("Last Index: " + ll.get(ll.size()));
System.out.println("'Middle' Index: " + ll.get(5));
System.out.println("Empty list with index of 0: " + llempty.get(0));

Which throws a NullPointerException at the second test case of trying to get the last index:

Output:

First Index: Frank
Exception in thread "main" java.lang.NullPointerException

I need to be able to demonstrate the following:

Test cases: index of zero, index at end of list, index in “middle” of list, empty list with index 0, index too big, index too small

So I'm stuck here guys / gals, any help would be appreciated!

Your last index isn't `ll.size()` it's `ll.size() - 1` – Hovercraft Full Of Eels Apr 23 '16 at 12:45 — Hovercraft Full Of Eels, Apr 23 '16 at 12:45

score 1 · Answer 1 · answered Apr 23 '16 at 12:46

I would just make your code even more simple (the second if around your loop isn't needed):

//assume 0 based index
int current = 0;

//loop until we hit the requested index
while (current != index) {
 f = f.next;
 current++;
}

//return the right node
return f;

Assuming your initial check for index out of bounds is correct, this should never give you an issue. However, if your indexes are 0 based, you need to change your out of bounds check to:

if (index > size - 1 || index < 0) {

For example if there are 2 elements, you have indexes 0 and 1. An index of 2 is invalid in this case.

Erick G. Hagstrom · Accepted Answer · 2016-04-23T14:04:10.103

There are two instances of the same mistake in your code. You have to understand that index is zero-relative, which means that the last element in a list of size n would have the index n-1. The first mistake is in your new get() method:

// If index is bigger / smaller than Linked List size throw IndexOutOfBounds
if (index > size || index < 0){
    throw new IndexOutOfBoundsException();
}

Here you should check index >= size, as follows:

// If index is bigger / smaller than Linked List size throw IndexOutOfBounds
if (index >= size || index < 0){
    throw new IndexOutOfBoundsException();
}

The second mistake is in your test code. Where you write

System.out.println("Last Index: " + ll.get(ll.size()));

You should use ll.size() - 1 as follows:

System.out.println("Last Index: " + ll.get(ll.size() - 1));

Both of these things have been observed by others. It is, however, necessary to fix them both.

When I made those changes and ran your test it got to the last line and threw IndexOutOfBoundsException as expected. I also tested "Index Too Small" and "Index Too Big" and got IndexOutOfBoundsException.

God I'm such an idiot. I didn't write the node class so I just assumed it was a 0 based class, which wow would you look at that it's not. Anyway thank you for your detailed answer. — Frank R, Apr 23 '16 at 14:03

score 0 · Answer 3 · answered Apr 23 '16 at 12:45

0

This may not be the only reason (you only showed us parts of the code), but you messed up with the 'size' value, because if the index starts at 0 (as usual), the last element should be at

index == size -1

answered Apr 23 '16 at 12:45

J Fabian Meier

33,516
10
64
142

score 0 · Answer 4 · answered Apr 23 '16 at 13:02

0

Should have been

if (index >= size || index < 0){
        throw new IndexOutOfBoundsException();
    }

if (index < size && index >= 0) {
    for (int i = 0; i < index; i++) {
        f = f.next;
    }
}

answered Apr 23 '16 at 13:02

Arun George

1,167
3
15
29

LinkedList Get method

4 Answers4

Linked