Programming 3

Creating a list

Let’s create a list of objects of type Integer:

List<Integer> lista_de_enteros = new ArrayList<Integer>();

The reason why we use ‘new ArrayList’ and no ‘new List’ will become clear when we talk about polymorphism and interfaces.

Since version 1.7 of Java, the type of element in the list can be omitted in the new statement:

List<Integer> lista_de_enteros = new ArrayList<>();

The compiler is responsible for performing what is called type inference, inferring from the compile-time type of lista_de_enteros what the type of its elements is and therefore what type must go between <> (<> is known as the diamond operator in Java jargon)[.

Adding elements to the list

The add(·) method adds a reference to an object at the end of the list:

lista_de_enteros.add(new Integer(4));
lista_de_enteros.add(new Integer(5));
lista_de_enteros.add(new Integer(7));
lista_de_enteros.add(2,new Integer(6)); // adds it at position 2, between 5 and 7
lista_de_enteros.add(4); // add 4 again, using 'boxing'
// this last line is equivalent to: lista_de_enteros.add(new Integer(4));

Size of a list

Use size() to know the size of a list:

int tam = lista_de_enteros.size();

returns 5: the list contains 5 elements.

Getting elements from a list

The get(int) method serves to access any element of the list, by its position:

Integer primero = lista_de_enteros.get(0);
int primer = lista_de_enteros.get(0); // 'unboxing', directly getting an 'int'.

returns the object at position 0, that is, the first of those I added.

Integer ultimo = lista_de_enteros.get(lista_de_enteros.size()-1);

returns the last element of the list.

Knowing if an element is in the list

Use the contains(·) method to ask the list if it contains the given object:

lista_de_enteros.contains(new Integer(7)); // will return 'true'
lista_de_enteros.contains(new Integer(8)); // will return 'false'

Getting the position of an object in the list

The indexOf(·) method tells me the position of the first occurrence of the object in the list (remember that the same object can be repeated in different positions):

lista_de_enteros.indexOf(new Integer(6)); // returns 2
lista_de_enteros.indexOf(new Integer(10)); // returns -1

Traversing the elements of the list

We can use a conventional loop:

for (int i=0; i < lista_de_enteros.size(); i++) {
  System.out.println(lista_de_enteros.get(i));
}

which would allow us to traverse only part of the list if we are interested (e.g., the first four elements).

With a for loop like this:

for (Integer entero : lista_de_enteros) {
  System.out.println(entero);
}

where the variable ‘entero’ of type Integer (it can also be of type ‘int’ in this case) takes the value of the next element of the list ‘lista_de_enteros’ in each iteration. With this type of loop, we traverse ALL elements of the list.

A somewhat more sophisticated, but more flexible way to do this is to use iterators:

Iterator<Integer> iterador = lista_de_enteros.iterator(); 
while (iterador.hasNext()) {
  Integer entero = iterador.next();
  System.out.println(entero); // prints an element
}

Notice that in the ‘while’ loop we could add more conditions to stop the loop where we are interested, which we cannot do with the previous ‘for’ loop.

Removing an object from the list

For this, we use the remove(·) method in two ways:

boolean quitado = lista_de_enteros.remove(new Integer(7)); // or remove(7)

removes the first occurrence of 7 in the list and returns ‘true’. If there is no 7, it would return ‘false’.

Integer unEntero = lista_de_enteros.remove(1);

removes the second element of the list and returns it.

NOTE: You might think that in this second call to remove() on a List, the Java compiler will perform boxing and call the first version of the method, but it does not and calls this second version, which accepts exactly one argument of type int (try it). On lists with another type of elements, this doubt would not arise.

Knowing if a list is empty or clearing it

This is easy:

boolean estaVacia = lista_de_enteros.isEmpty(); // will return 'false'
lista_de_enteros.clear(); // now it is indeed empty

Creating a set

Let’s create a set of objects of type Integer:

Set<Integer> conjunto_de_enteros = new HashSet<Integer>();

Why ‘new HashSet’ and not ‘new Set’ will become clear when we talk about polymorphism and interfaces.

Adding elements to the set

The add(·) method adds a reference to an object to the set.

conjunto_de_enteros.add(new Integer(4));
conjunto_de_enteros.add(new Integer(5));
conjunto_de_enteros.add(new Integer(7));
boolean repe = conjunto_de_enteros.add(new Integer(4));
// does not add 4 because it is already in the set and also returns 'false'

(with all collections of the JCF we can use boxing/unboxing, so we will not comment on it further.)

Size of a set

conjunto_de_enteros.size();

returns 3: the set contains 3 elements.

Knowing if an element is in the set

conjunto_de_enteros.contains(new Integer(7)); // will return 'true'
conjunto_de_enteros.contains(new Integer(8)); // will return 'false'

A Set does not have the get(·) and indexOf(·) methods; elements are not in any particular position. Basically, with a set what we can do is add elements, remove them, and ask if an element belongs to the set.

Traversing all elements of the set

With a for loop like this:

for (Integer entero : conjunto_de_enteros) {
  System.out.println(entero);
}

This loop prints all the integers in the set, one on each line. The problem is that it does not traverse the set in any particular order. There is no defined order in the set.

Removing an object from the set

boolean quitado = conjunto_de_enteros.remove(new Integer(7));

returns ‘true’. If there is no 7, it would return ‘false’.

Knowing if a set is empty or clearing it

boolean estaVacio = conjunto_de_enteros.isEmpty(); // will return 'false'
conjunto_de_enteros.clear(); // now it is indeed empty

Creating a queue

Queue<Integer> cola = new LinkedList<>(); // LinkedList implements the Queue interface

Enqueuing, dequeuing, and examining the head of the queue

There are two ways to perform these operations with a queue: using methods that throw unchecked exceptions if they fail (for example, if we try to dequeue from an empty queue), or methods that return a special value (null or false) in case of error. In this table you have the operations of Queue that throw exceptions (throw) or return a value (return) if they fail:

// using add()
cola.add(5);
cola.add(6);

// using offer()
cola.offer(5);
cola.offer(6);

cola.offer(5);
cola.offer(6);
int a = cola.peek(); // the element is not dequeued
a = cola.element();  // same operation

cola.offer(5);
cola.offer(6);
int a = cola.poll(); // returns the head element and dequeues it
a = cola.remove(); // same operation

Priority queues

They are a type of queue where elements are enqueued, but are ordered in the queue based on a criterion. So that at the head of the queue is the element with highest (or lowest) priority. There are two ways to define this ordering criterion: by making the elements of the list implement the Comparable interface, or by means of a Comparator object provided to the queue at creation time that implements the desired order.

For example, the Integer class implements the Comparable interface and therefore we can store integers in a priority queue, so that the smallest element among those inserted in the queue will occupy the head position:

PriorityQueue<Integer> cola = new PriorityQueue();
cola.add(5);
cola.add(2);
cola.add(3);
int a = cola.peek(); // returns 2
a = cola.poll(); // returns 2 and dequeues it
a = cola.peek(); // returns 3

If we want the integers to be ordered differently in the queue (for example, from largest to smallest), we must provide the queue with an integer comparator that orders them that way.

This is done by creating a class that implements the Comparator<T> interface, which tells us that we must implement the compare(a,b) method to compare two objects of type T ‘a’ and ‘b’, such that:

• if a < b, then compare(a,b) returns a negative number.
• if a.equals(b), then compare(a,b) returns zero.
• if a > b, then compare(a,b) returns a positive number.

Continuing with the integer queue example, if we want them to be ordered ‘in reverse’ from largest to smallest, then we must invert the order making:

• if a < b, then compare(a,b) returns a positive number.
• if a.equals(b), then compare(a,b) returns zero.
• if a > b, then compare(a,b) returns a negative number.

The following code does precisely this with a priority queue for integers:

Comparator<Integer> comparador = new Comparator<Integer>() {
  @Override
  public int compare(Integer a, Integer b) {
    return b - a;
  }
};

PriorityQueue<Integer> cola = new PriorityQueue(comparador);
cola.add(5);
cola.add(2);
cola.add(3);
int a = cola.peek(); // returns 5
a = cola.poll(); // returns 5 and dequeues it
a = cola.peek(); // returns 3

Adding an entry to the map

The put(·) method adds a correspondence between a key and its value:

damero.put(new CoordenadaAjedrez('A',3),
           new PiezaAjedrez("ALFIL",Color.BLANCO));

damero.put(new CoordenadaAjedrez('B',7),
           new PiezaAjedrez("CABALLO",Color.NEGRO));

damero.put(new CoordenadaAjedrez('B',7),
           new PiezaAjedrez("REINA",Color.BLANCO));

The last instruction changes the piece associated with square B7 to a white queen. It is as if we had taken the black knight off the board and put the white queen in its place. The map therefore has 2 elements (key-value pairs) and not 3.

Notice that nothing prevents us from associating the same value with different keys:

damero.put(new CoordenadaAjedrez('F',4),
           new PiezaAjedrez("REINA",Color.BLANCO));
// now the map indeed has 3 key-value pairs

Or associating a key with a ‘null’ value:

damero.put(new CoordenadaAjedrez('A', 1), null);
// now the map has 4 elements

Size of a map

damero.size(); // returns 4

The map contains 4 entries: ([A3, white BISHOP], [B7, white QUEEN], [F4, white QUEEN], [A1, null]).

Getting the value associated with a key in the map

The get(·) method allows us to search in the map using a key:

PiezaAjedrez pieza = damero.get(new CoordenadaAjedrez('A',3));  

returns a reference to the bishop. If the key is not in the map, it will return ‘null’.

Knowing if a key is in the map

Use the containsKey(·) method to ask the map if the given key has any associated value:

damero.containsKey(new CoordenadaAjedrez('A',3)); // returns 'true'
damero.containsKey(new CoordenadaAjedrez('H',3)); // returns 'false'

Knowing if a value is associated with any key

Use the containsValue(·) method to ask the map if the given value is associated with at least one key:

damero.containsValue(new PiezaAjedrez("ALFIL",Color.BLANCO)); // returns 'true'
damero.containsValue(new PiezaAjedrez("REY",Color.NEGRO)); // returns 'false'

Traversing a map

Maps cannot be traversed directly, as we do with a list or a set. However, we can obtain the set of keys stored in the map, traverse this set, and ask the map for the value associated with each key:

Set<CoordenadaAjedrez> coordenadas = damero.keySet();

for (CoordenadaAjedrez coord : coordenadas) {
  PiezaAjedrez pieza = damero.get(coord);
  System.out.println(coord.toString() + " -> " + pieza.toString());
}

Removing an entry from the map

For this, we use the remove(·) method:

PiezaAjedrez pieza = damero.remove(new CoordenadaAjedrez('A',3));

Removes the entry associated with square A3 and returns the piece that was in that square. If the square were not in the map, it would return ‘null’.

Knowing if a map is empty or clearing it

This is easy:

boolean estaVacio = damero.isEmpty(); // will return 'false'
damero.clear(); // now it is indeed empty

hashCode()

This method, which is usually implemented in all classes, returns an integer that acts as an identifier for an object. It is a method compatible with equals(), so that if object1.equals(object2) returns ‘true’, then object1.hashCode() returns the same value as object2.hashCode().

Some implementations of lists, sets, and maps use hashCode(·) instead of equals(·) to know if two objects are equal.

JCF API

Finally, every Java programmer makes intensive use of the language’s API (Application Programming Interface) documentation. The full documentation of the Java Collections Framework for version 1.8 of Java can be consulted here:

Java Collections Framework