CODEWITHSUNDEEP
javaarraysarraylist
wcm_1348
wcm_1348

Reputation: 21

Randomly choose an array element in a non-full array

I have a program where I am creating an arrayList. One method randomly removes an item from the list. I also have a method that resizes the array if a certain amount of elements are added to make space for more elements to be added if wanted.

I am receiving a NullPointerExceptionError when the lists are resized and then the method tries to remove one of the null spaces in the newly resized array.

Without using a for loop and keeping a constant time, I'm trying to find a way to make my int value of choice just the number of non null elements in the array. I hope that makes sense - can anyone help?

remove method: 

public T remove() {
  if (isEmpty()) {
     return null;
  }
  Random rand = new Random();
  int choice = rand.nextInt(size);
  size--;
  elements[choice] = elements[size];
  elements[size] = null;
  return elements[choice];
}

Upvotes: 1

Views: 71

Answers (1)

Andreas
Andreas

Reputation: 5093

This question boils down to "Given an array with null elements scattered throughout, how can I return the nth non-null element?" The answer is iterate through the array, which doesn't uphold the constant time constraint your're looking for.

But wait, how can array lists work in that case?!? Here is how java.util.ArrayList does it:

@Override
public E get(int location) {
    if (0 <= location && location < (lastIndex - firstIndex)) {
        return (E) array[firstIndex + location];
    }
    throw new IndexOutOfBoundsException(Messages.getString("luni.0A",
            location, lastIndex - firstIndex));
}

Note that there are no null checks, the Arraylist always maintains its elements in a contiguous block so gets are super fast. So some magic must happen when removing elements so there won't be nulls scattered about...

@Override
public E remove(int location) {
    E result;
    int localLastIndex = lastIndex;
    int size = localLastIndex - firstIndex;
    if (0 <= location && location < size) {
        if (location == size - 1) {
            result = (E) array[--localLastIndex];
            array[localLastIndex] = null;
        } else if (location == 0) {
            result = (E) array[firstIndex];
            array[firstIndex++] = null;
        } else {
            int elementIndex = firstIndex + location;
            result = (E) array[elementIndex];
            if (location < size / 2) {
                System.arraycopy(array, firstIndex, array, firstIndex + 1,
                        location);
                array[firstIndex++] = null;
            } else {
                System.arraycopy(array, elementIndex + 1, array,
                        elementIndex, size - location - 1);
                array[--localLastIndex] = null;
            }
        }
        if (firstIndex == localLastIndex) {
            firstIndex = localLastIndex = 0;
        }
    } else {
        throw new IndexOutOfBoundsException(Messages.getString("luni.0A",
                location, localLastIndex - firstIndex));
    }
    lastIndex = localLastIndex;
    modCount++;
    return result;
}

There is the key! When removing an element the JDK impl doesn't leave a gap, nor does it move all the elements over to close the gap. It calls a native method that copies a chunk of array around as an atomic operation: https://docs.oracle.com/javase/7/docs/api/java/lang/System.html#arraycopy(java.lang.Object,%20int,%20java.lang.Object,%20int,%20int)

Upvotes: 2

Related Questions