Randomized Queue with ArrayList from Princeton's Algorithm Book

Question

In the book they recommend to utilize an Array, but I think that it's easier to use an ArrayList instead, is there any problem with that? Is this code well designed?

package com.company;

import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Random;

public class RandomQueue<Item>{
    private ArrayList<Item> a;
    private int size;
    Random r;

    public RandomQueue(){
        a = new ArrayList<Item>();
        size = 0;
    }
    
    public int size(){
        return size;
    }
    
    public boolean isEmpty(){
        return size == 0;
    }
    
    public void enqueue(Item item){
        a.add(item);
        size++;
    }
    
    public Item dequeue(){
        if(isEmpty()){
            throw new NoSuchElementException("Queue is empty");
        }else {
            r = new Random();
            int randomIndex = r.nextInt(size);
            Item item = a.get(randomIndex);
            a.remove(randomIndex);
            size--;
            return item;
        }
    }
    
    public Item sample(){
        r = new Random();
        if(isEmpty()){
            throw new IndexOutOfBoundsException();
        }
    
        int index = r.nextInt(size);
        return a.get(index);
    }

}

Answer 1

You should document the reason why Random r is package private. At the moment the reason is not clear, but if you fix the "perpetual reinstantiation" by initializing the r variable in the constructor, then you can take advantage of the package private visibility in unit tests by replacing the random number generator with a non-random Random implementation (because unit testing random behaviour is pretty much impossible).

If you go with the static Random as suggested by @mdfst13, then you should use ThreadLocalRandom so that different threads that use the class do not interfere with each other.

It is customary in Java that generic types are defined using single capital letters. Using a name that resembles a class name (<Item>) can be confusing as in a cursory glance it suggests that a specific Item class should be used. This increases cognitive load, which makes following the code more difficult.

Beyond generic types, single letter names should be avoided. Use names that describe the purpose of the field. Non-descriptive field names again increase the cognitive load on the reader.

The two instances of generating a random index should be refactored to an internal method.

public class RandomQueue<T> {
    
    private final List<T> data = new ArrayList<>();
    
    /**
     * Package private so that it can be overridden in unit tests.
     */
    Random rand = new Random();
    
    private int randomIndex() {
        return rand.nextInt(data.size());
    }

    ....
}

Because this is Java and the class implements a collection of objects, you should see if it would make sense to implement the Collection interface. This might make the class more versatile.

Answer 2

This is in addition to Torben's answer.

Java Collections Framework

It was a good idea to replace the original array with an ArrayList, but you can get even more benefit from that replacement.

Your size field isn't necessary any more, as there is a size() method in the collections framework, and what you count yourself is exactly the size of your list, so you can use that method and delete the size field.

You declare the list as

    private ArrayList<Item> a;

It's recommended to declare fields and variables with the least specific interface type that matches your needs. Candidates are Collection and List. Collection doesn't support the indexed access that you need, so you should write

    private List<Item> a;

or even include the initialization there instead of the constructor:

    private List<Item> a = new ArrayList<>();

This way, it's easier to later change e.g. from an ArrayList to a LinkedList if you see a benefit, or want to do performance comparisons. As both classes fully comply with the List interface, no other line of code has to be touched for that change.

You might even decide to make your own class conform to the Collections framework by declaring to implement Collection or one of its sub-interfaces. This makes such a queue class much more useful than its "isolated" counterpart.

But be warned that there is some complexity in implementing a compliant Collection from scratch, so the recommended way would be to extend some existing class, maybe AbstractList or AbstractQueue.

Style

Your indentation is perfect.

Your naming can be improved (see Torben's answer).

Your usage of spaces is a bit inconsistent and not following the conventions we all are used to see, e.g. in

    }else {

Your IDE surely has a function for re-formatting your code (if not, switch to decent one, e.g. Eclipse), and you should make it a habit to let it do its job regularly.

Documentation

This class could well become part of a useful library. Then it's important to let your fellow developers know what the various methods do. While it's quite possible to guess what enqueue() and dequeue() do (good naming!), at least your sample() method isn't self-explanatory from its name, and deserves a documentation.

You should make it a habit to write Javadoc-formatted comments for classes, constructors and public methods so others can read what they are meant for, without having to dive into your source code. The Javadoc format is well supported in all decent IDEs, e.g. showing up as a tooltip on method names.

Answer 3

It's not a good idea to use an ArrayList because the object of the class is to teach you algorithms and data structures, so when you submit the assignment, the tests will fail, because java.util.* is banned.

The goal of this assignment is for you to implement the array-backed List yourself, and handle the resizing of the underlying array and correctly keep track of the size.

If you use an ArrayList, the size variable becomes meaningless, just use the .size() method on the ArrayList.

One of the design goals is for every operation to be in constant time, so they also want you to think about how to remove and return a random item without having to move half the items if you remove and return one from the middle of the list.

As you have correctly observed, all these requirements become quite easy if you just use ArrayList from the java.util package. ArrayList handles the resizing of the underlying array for you, it takes care of .remove(), keeps track of the size.

From the java.util.ArrayList code:

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

As you can see, it could move all of the items to the right of i. If there's a billion items in the RandomizedQueue, on average your code may be doing half a billion hidden copy operations under the hood. This is something you might not think of if you had never implemented an ArrayList from scratch. I recommend only adding / removing from the end, so you have to think about how to return a random value while only removing from the end. Remember that moving costs about 1/2 N, but swapping is constant time.