Java ArrayList.remove() not decrementing the Size of the ArrayList

Question

I have an ArrayList to store some data, but whenever I remove an item from the list, the size does not decrease, even when I call ArrayList.trimToSize(). This is causing me nullPointerExceptions.

How can I remove a single item from an ArrayList and have the list's size() shrink accordingly?

EDIT: All right, here's the code. Here's a bit of background you'll need to know, since I can't post all the code. I have an ArrayList called _dataHeap and a HashMap called _dataMap. The ArrayList is a binary Heap containing a "findable" object, which has a Key. The HashMap bind from a Key to the index of the object in the ArrayList. This is so an item in the queue can be found by item using the HashMap or by index using ArrayList. The Key can be any Object, as long as it is unique for every item in the queue.

I've debugged this line by line, and the Heap contains the object, even down to the Hashcode. The problem is, the Object is never being removed from the ArrayList. This must mean that _dataMap.get(element.getKey()) is not pointing to where it should. I've checked it though, I used a test object outside of my implementation that maps from a String to a custom object with String as a Key.

I make one object, with String "one" as its key. I insert it, then try to remove it. I've stepped through this, and everything checks out, except one thing: The object is never removed from the queue. It's got the same Hashcode, the same Key, everything. It gets removed from the map just fine, but not from the ArrayList.

Here's the remove method:

public T remove(T element) {
    //We'll need this data to return the proper value
    T t = _dataHeap.get(_dataMap.get(element.getKey()));
    /*
     * this Swap() call is used to swap our target with the end
     * of the arraylist. This means that whenever we remove it,
     * we don't have a change in indexes of the other nodes.
     * After that, we downHeapify() to fix the whole graph back
     * to it's functional state.
     */
    swap(_dataMap.get(element.getKey()),length()-1);
    //Remove from the Heap
    _dataHeap.remove(_dataMap.get(element.getKey()));
    _dataHeap.trimToSize();
    //Remove from the Map
    _dataMap.remove(element.getKey());
    downHeapify();
    return t;

I hope this gives you a better idea of what I'm doing wrong.

EDIT THE SECOND: Holy crap I finally fixed it! I pulled the _dataHeap.get(element.index) into it's own variable. That solved EVERYTHING!

Answer 1

As Bemace said, check if remove works as you intend. I'd bet money that your equals() method on the object you're composing doesn't work how you'd expect it to, because you did not override it.

Furthermore, after you override equals, take care to also override hashCode. It'll save you a SO question when your object doesn't work with HashMaps. :)

A tip: Look into using JUnit. It will blow these little errors right out of the water, making it obvious to you when something's not working how you'd hope. It's very hard to ignore a bright red spot on your beautiful green bar.

Answer 2

Sounds to me like you're not actually removing anything. What's the return value of your remove call?

If you're using remove(int) the return value should be non-null. If using remove(Object), the result should be true. Otherwise you haven't actually removed anything. Attempting to remove an element which doesn't exist is not an error, just returns null or false.