5
\$\begingroup\$

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);
    }

}
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for the detailed explanation as well \$\endgroup\$
    – Enzo Yasuo
    Sep 11 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.