Created Linked List not returning correct index

Question

I created a list that goes {50, 10, 60, 30, 40} and want to return the index when I reach 30 in my Linked List, however my program always returns -1 (basically it is unable to increment and return my index). I am not sure about how to go about getting back the index in a different manor unless I am able to cast the anEntry object into an integer and equal it my index.

class MyLinkedList {
    private Node firstNode; // index = 0
    private int length;
    public MyLinkedList() {
        firstNode = null;
        length = 0;
    } // end default constructor
    /** Task: Adds a new entry to the end of the list.
     * @param newEntry the object to be added as a new entry
     * @return true if the addition is successful, or false if not */
    public boolean add(Object newEntry) {
        Node newNode = new Node(newEntry);
        if (isEmpty())
            firstNode = newNode;
        else {
            Node lastNode = getNode(length-1);
            lastNode.next = newNode;
        }
        length++;
        return true;
    } // end add
    /** Task: Adds a new entry at a specified index
     * @param newEntry the object to be added at the specified index
     * @return true if successful, or false if not */
    public boolean add(int index, Object newEntry) {
        boolean isSuccessful = true;
        if ((index >= 0) && (index <= length)) {
            Node newNode = new Node(newEntry);
            if (isEmpty() || (index == 0)) {
                newNode.next = firstNode;
                firstNode = newNode;
            }
            else {
                Node nodeBefore = getNode(index - 1);
                Node nodeAfter = nodeBefore.next;
                newNode.next = nodeAfter;
                nodeBefore.next = newNode;
            }
            length++;
        }
        else
            isSuccessful = false;
        return isSuccessful;
    } // end add
    /** Task: Determines whether the list contains a given entry.
     * @param anEntry the object that is the desired entry
     * @return true if the list contains anEntry, or false if not */
    public boolean contains(Object anEntry) {
        boolean found = false;
        Node currentNode = firstNode;
        while (!found && (currentNode != null)) {
            if (anEntry.equals(currentNode.data))
                found = true;
            else
                currentNode = currentNode.next;
        } // end while
        return found;
    } // end contains
    /** Task: Gets an entry in the list.
     * @param the desired index
     * @return the desired entry, or
     * null if either the list is empty or index is invalid */
    public Object getEntry(int index) {
        Object result = null; // result to return
        if (!isEmpty() && (index >= 0) && (index < length))
            result = getNode(index).data;
        return result;
    } // end getEntry
    /** Task: Gets index of an entry in the list.
     * @param the desired entry
     * @return index of the first occurrence of the specified entry
     * in this list, or -1 if this list does not contain the entry */
    public int getIndex(Object anEntry) {
        Node currentNode = firstNode;
        int index = 0; // result to return
        while (anEntry != currentNode.data) {
           currentNode = currentNode.next;
           index++;
           if (anEntry.equals(currentNode.data)){
               break;
           }
           else {
               return -1;
           }
        }
        return index;
    } // end getIndex
    private Node getNode(int index) {
        Node currentNode = firstNode;
        // traverse the list to locate the desired node
        for (int counter = 0; counter < index; counter++)
            currentNode = currentNode.next;
        return currentNode;
    } // end getNode
        private Node getNode(int index) {
        Node currentNode = firstNode;
        // traverse the list to locate the desired node
        for (int counter = 0; counter < index; counter++)
            currentNode = currentNode.next;
        return currentNode;
    } // end getNode
    private class Node {
        private Object data; // data portion
        private Node next; // link to next node

        private Node(Object dataPortion) {
            data = dataPortion;
            next = null;
        } // end constructor
        private Node(Object dataPortion, Node nextNode) {
            data = dataPortion;
            next = nextNode;
        } // end constructor
        private void setData(Object dataPortion) {
            data = dataPortion;
        } // end setData
        private Object getData() {
            return data;
        } // end getData
        private void setNextNode(Node nextNode) {
            next = nextNode;
        } // end setNextNode
        private Node getNextNode() {
            return next;
        } // end getNextNode
    } // end Node
} // end MyLinkedList

Answer 1

The problem is that your while loop never does more than one iteration.

if (anEntry.equals(currentNode.data)){
    break;
}
else {
    return -1;
}

If the current element matches, then I have found the item so we can stop. If it doesn't, then the list does not contain this item. It should be relatively clear that this logic is wrong. Just because the current element doesn't match does not mean that subsequent elements might not match.

You can demonstrate this further by observing that getIndex(50) actually does return the correct index: zero. Your statement "my program always returns -1" is actually incorrect.

We need to swap this logic around - only return -1 after we have already tried all the elements.

while (anEntry != currentNode.data) {
    currentNode = currentNode.next;
    index++;
    if (anEntry.equals(currentNode.data)){
        return index;
    }
}
return -1;

You will still have a problem where your code will throw an exception if the element is not in the list. This can be trivially solved with a minor change to the above code, but I'll leave that up to you to figure out!