Collections¶

Introduction¶

Collections, also often referred to as containers, i.e. objects that aggregate items. Collections are used to store objects, obtain stored data, or manipulate data.

In Java, collections built into the language are based on the following mechanisms:

• Interface: abstract data type representing collections. Interfaces allow collections to be manipulated independently of implementation details.
• Implementation: concrete implementation of the collection interfaces. These are most often reusable data structures.
• Algorithm: useful operations on data structures that most often have a [polymorphic] structure (oop.md#polymorphism).

Java collections give developers the following benefits:

• release the programmer from the obligation to implement data structures from scratch, which reduces the time needed to implement a specific functionality,
• implemented data structures use the most effective mechanisms, and their implementation is optimal,
• when designing your own data structures, there is no need to "reinvent the wheel". You can reuse existing ones.

NOTE: Before you start writing your own algorithm or collection, make sure it has not been implemented yet.

Interfaces¶

Collection interfaces represent different types of containers. These interfaces enable the manipulation of collections without going into implementation details.

The core of all collections is the generic interface: public interface Collection <E> ...

Below are all the underlying Collection APIs:

• Set - a collection that cannot store duplicates.
• List - an ordered collection, may contain duplicates.
• Queue - a collection that implements the FIFO (first in, first out) or LIFO (last in, first out) mechanism.
• Deque - a kind of queue where you can add and remove items, both from the beginning and the end.
• Map - a collection for storing key-value pairs.

Set¶

java.util.Set is the generic data structure responsible for storing unique elements. Set uses only the methods of the Collection interface. Additionally, it introduces a strong connection between methods: equals andhashCode. There are three basic implementations of the Set interface:HashSet, TreeSet,LinkedHashSet.

• HashSet:

  • the order of the items is not kept
  • stores information in a hash table

• TreeSet:

  • the order of the elements is preserved according to the so-called natural order or according to some [Comparator] (collections.md # comparator)
  • stores data in a red-black tree

• LinkedHashSet:

  • saves information about the order of adding individual elements
  • the implementation is based on a hash table with linked list support

The following examples show the use of all three implementations of the Set interface:

final Set<Integer> numbersSet = new HashSet<>(); // stworzenie instancji HashSet
System.out.println(numbersSet.isEmpty()); // true, Set ndoes not contain elements
numbersSet.add(1);
numbersSet.add(17);
numbersSet.add(3);
numbersSet.add(2);
numbersSet.add(1); // Adding an item with a value that already exists - the item is NOT added again
numbersSet.forEach(System.out::println);

/* example order in which items can be listed:
 1 17 2 3
*/

final Set<Integer> numbersSet = new TreeSet<>();
numbersSet.add(1);
numbersSet.add(3);
numbersSet.add(2);
numbersSet.add(1); // Adding an item with a value that already exists - the item is NOT added again
numbersSet.forEach (System.out::println);
/* The order of the items will ALWAYS be the same (sorted in natural order):
 1 2 3
*/

final Set<Integer> numbersSet = new LinkedHashSet<>();
numbersSet.add(1);
numbersSet.add(3);
numbersSet.add(2);
numbersSet.add(1); // Adding an item with a value that already exists - the item is NOT added again
numbersSet.forEach (System.out::println);
/* The order of items will ALWAYS be the same (in the order of adding items)
 1 3 2
*/

List¶

java.util.List is the interface that represents ordered collections. It is characterized by the fact that:

• may contain duplicate elements (i.e. with the same value)
• the item can be downloaded based on its position in the list (based on the index)
• we can search for the item.

The most commonly used implementations of the List interface are:

• ArrayList, which is based on an array structure
• LinkedList, which is implemented as nodes. Each node indicates the position of the next node

The following examples show the use of both implementations:

final List<String> names = new ArrayList<>();
names.add("Andrew");  // adding an item to the end of the list
names.add("Gregory"); // adding an item to the end of the list
for (final String name: names) {
  System.out.println(name); // Andrew, Gregory will be displayed on the screen, keeping the order
}

final List<String> names = new LinkedList<>();
names.add(0, "Andrew");  // adding an item to the top of the list
names.add(0, "Gregory"); // adding an item to the top of the list
for (final String name: names) {
  System.out.println(name); // Gregory, Andrew will be printed on the screen in order
}

ArrayList and LinkedList - differences¶

When should we use ArrayList and when should we useLinkedList? To answer this question, we must remember that:

• getting an item based on its index from ArrayList is faster (O (1)) than fromLinkedList (O (n))
• adding an element using the add (E someELement) method has the same computational complexity for both implementations, but when the internal array in ArrayList overflows, this operation is slower (O (n))
• adding an element to a specific index, i.e. using the add (int index, E someElement) method, is faster with LinkedList.

NOTE: Unless we are sure which implementation to choose, ArrayList will be the optimal choice in most cases.

Queue¶

java.util.Queue is a generic interface representing the data structure to implement FIFO and LIFO queues. These queues work in the same way as the queues at the cash register in the store, i.e .:

• items added go to the end of the queue
• we can first "service" a person from:
  • start of queue ( FIFO )
  • at the end of the line ( LIFO ).

The queue, in addition to basic operations from the Collection interface, performs additional data manipulation operations:

public interface Queue<E> extends Collection<E> {
    E element();
    boolean offer(E e);
    E peek();
    E poll();
    E remove();
}

The different methods are used to:

• element() - returns an element from the "front" of the queue (but does not remove it from the structure) or throws a NoSuchElementException exception in case of an empty collection
• peek() - works the same as the element method, but doesn't throw an exception on an empty queue
• offer() - adds an item to the queue and returns if the operation was successful
• remove() - removes an element from the "head" of the queue and returns its value or throws an exception NoSuchElementException in case of an empty collection
• poll() - works the same as the remove method, but does not throw an exception on an empty queue

The primary implementation of a queue is LinkedList.

final Queue<String> events = new LinkedList<>();
events.offer("ButtonClicked");
events.offer("MouseMoved");
System.out.println(events.peek());   // displaying the first element
System.out.println(events.poll());   // removing the first item from the queue and returning a value
System.out.println(events.poll());   // removing the first item from the queue again and returning the value
System.out.println(events.isEmpty()); // at this point the queue is empty

Deque¶

Deque, or double-ended queue, is an interface that describes a data structure that is a kind of queue that allows items to be added and removed, both at the beginning and end.

The java.util.Deque interface extends thejava.util.Queue interface previously discussed. The most commonly used implementations of Deque areArrayDeque and LinkedList.

Deque additionally gives us access to the following methods:

• addFirst(e) anofferFirst(e), which add an element to the top of the queue
• addLast(e) and offerLast(e), which add an item to the end of the queue
• removeFirst() and pollFirst(), which remove an element from the front of the queue
• removeLast() and pollLast(), which remove an item from the end of the queue
• getFirst() and peekFirst(), which retrieve the item from the top of the queue
• getLast() and peekLast(), which retrieve the item from the end of the queue.

It should be remembered that the above prefix methods:

• add, remove and get will throw an exception on failure
• offer, poll, peek will return a special value on operation failure (null for objects and false for boolean).

Below is an example of how to use a double ended queue:

// create a Deque object
final Deque<Integer>deque = new ArrayDeque<>();
// add elements to deque
deque.offerLast(2);
deque.offerFirst(1);
System.out.println (deque.pollLast()); // remove elements from deque along with removing from structure -> 2
System.out.println (deque.peekLast()); // remove elements from deque without removing them from structure -> 1

Map¶

The java.util.Map interface is a data structure that enables key-value data manipulation. Each key in such an object must be unique, i.e. one key can contain exactly one value.

Map methods that are used to perform basic operations include:

• put - is used to add a suitable pair to the collection or replace an old value with a new one for a specific key
• get - Used to get a value based on a key
• remove - removes an element based on a key (or additional value)
• containsKey - Returns if there is a value in the map for the given key
• containsValue - Returns if there is a key in the map for the given value
• size - returns the number of pairs (the so-called Entry) in the collection
• isEmpty - returns if the map is empty

NOTE: The null value may be a key in the map.

In addition to standard operations, the map contains a set of operations responsible for returning items in the form of a different collection:

• keySet - returns the set of keys asSet
• values- returns all values ​​asCollection
• entrySet: returns the Set of key-value objects. A single pair is represented by the class [inner] (inner_classes.md) Map.Entry.

The three common implementations of the Map interface areHashMap, TreeMap, andLinkedHashMap. Implementation names and properties are very similar to the corresponding [Set] implementations (collections.md # set), i.e .:

• `HashMap:

  • the order of pairs is not preserved
  • stores information in a hash table.

• TreeMap:

  • the order of pairs is preserved according to the so-called natural order of keys or according to a certain key comparator
  • stores data in a red-black tree.

• LinkedHashMap:

  • saves information about the order of adding individual pairs
  • the implementation is based on a hash table with linked list support.

The following examples show map operations:

final Map<Integer, String> ageToNames = new HashMap<>(); // tworzenie HashMapy
ageToNames.put(11, "Andrew"); // adding items
ageToNames.put(22, "Michael");  // adding another pair
ageToNames.put(33, "John");  // adding a third pair to the map
ageToNames.remove(22);     // removing an item based on the key
System.out.println(ageToNames.get(11)); // displaying the value based on the key 11 -> Andrew

final Map<Integer, String> ageToNames = new LinkedHashMap<>(); // creating LinkedHashMap
ageToNames.put(20, "Maggie");
ageToNames.put(40, "Kate");
ageToNames.put(30, "Anne");

for (final Integer key : ageToNames.keySet()) { // key iteration using keySet()
  System.out.println("Key is map: " + key);     // the order of the keys is always the same -> 20, 40, 30
}

for (final String value : ageToNames.values()) {   // iteration over values using values()
  System.out.println("Value in map is: " + value); // the order of the values is always the same -> Maggie, Anne, Kate
}

for (final Map.Entry<Integer, String> ageToName : ageToNames.entrySet()) { // iteration over pairs with entrySet()
  System.out.println("Value for key  " + ageToName.getKey() + " is " + ageToName.getValue());
  /* the result will always be the following 3 lines, in this exact order (results from the use of LinkedHashMap)
     Value for key 20 is Maggie
     Value for key 40 is Kate
     Value for key 30 is Anne
   */
}

final Map<Integer, Integer> numberToDigitsSum = new TreeMap<>();
numberToDigitsSum.put(33, 6);
numberToDigitsSum.put(19, 10);
numberToDigitsSum.put(24, 6);
numberToDigitsSum.forEach((key, value) -> System.out.println(key + " " + value));

/* Items will always be listed in the same order:
  19 10
  24 6
  33 6
*/

Contract in Java¶

When adding items to collections such as Set, we need to determine on some basis whether such an object is already in the collection. The Java contract is closely related to the equals andhashCode methods, which are declared in the Object class. The implementations of both methods are often used together. The contract is based on the following rules:

• if x.equals(y) == true thenx.hashCode () == y.hashCode()is required
• if x.hashCode() == y.hashCode (), it is not required that x.equals(y) == true
• multiple calls to hashCode on the same object should always give the same result.

equals¶

Java primitive types are compared using the == operator, while the same logical operator, when comparing objects, will compare references to objects (i.e. whether both references point to the same address), not their values. In order to compare objects with regard to the indicated values, the overridden equals method is used.

int x = 10;
int y = 10;
boolean primitiveComparison = x == y;

Car car = new Car("BMW", "Sport");
Car car1 = new Car("BMW", "Sport");
boolean objectComparision = car == car1; // false, references vary
boolean objectComparisionUsingEquals = car.equals(car1); // true if the equals method is implemented in an intuitive way

The equals method is characterized by the following:

• is available in the Object class
• it can be called on any object
• this method should be returnable, i.e. someObject.equals (someObject) should return true
• should be a symmetric method, i.e. if x.equals (y) == true theny.equals (x) == true
• the method should be transitive, i.e. if x.equals (y) == true andy.equals (z) == true, then x.equals (z) == true
• this method should be consistent, i.e. calling the same method several times should give the same result
• when compared with null, the method should returnfalse.

Another class definition contains an example implementation of the equals method:

public class Car {
    private String name;
    private String type;

    public Car(String name, String type) {
        this.name = name;
        this.type = type;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Car car = (Car) o;
        return Objects.equals(name, car.name) &&
                Objects.equals(type, car.type);
    }

    @Override
    public String toString() {
        return "Car{" +
                "name='" + name + '\'' +
                ", type='" + type + '\'' +
                '}';
    }
}

The equals method is used when calling e.g. thecontains method from the Collection API, e.g .:

List<Car> cars = Arrays.asList(new Car("BMW", "Sport"), new Car("Volvo", "suv"));
boolean isVolvoInList = cars.contains(new Car("Volvo", "suv")); // true

hashCode¶

The hashCode method returns theint primitive and is ultimately intended to represent some kind of numeric representation of an object. Since this type is limited in scope, it is not a unique value for each object and therefore two different objects can return the same hashCode value. It is this property that many Java APIs use and it is the basis of the contract. The hashCode method is used to implement many data structures and algorithms, e.g. sorting. This method is characterized by:

• method available in the Object class
• the implementation of the hashCode method should be bound to theequals method
• the method is most often created based on the hashes of individual fields of the class. We usually multiply the hashes of attributes by prime numbers and sum them together.

An example implementation of such a method in the Car class defined in one of the examples above is shown below:

Java @Override public int hashCode () { int result = name.hashCode (); result = 31 * result + type.hashCode (); return result; } `

For the following code snippet, the contains method will returnfalse, despite overriding the equals method. For a structure of type HashSet, it is necessary to override thehashCode method for the code to work properly.

Set<Car> cars = new HashSet<>();
cars.add(new Car("BMW", "Sport"));
cars.add(new Car("Volvo", "suv"));
boolean isVolvoInSet = cars.contains(new Car("Volvo", "suv"));
System.out.println(isVolvoInSet); // true if the hashcode method is implemented in the Car class, false otherwise

NOTE: In practice, we rarely manually write implementations of the equals andhashcode methods. Most often we generate them or use external libraries for this purpose, e.g. the annotation @ EqualsAndHashCode from the library [lombok] (https://projectlombok.org/)

Sorting¶

Comparing collection elements in Java is performed using generic interfaces:

• Comparator <T>, which allows you to compare two objects of the same type using the compare method
• Comparable <T>, which compares the current object to an object of some type using the compareTo method.

The compare andcompareTo methods return the value of int. The compareTo method should return following values:

• value greater than 0 means that the compared object should be placed before the base object
• a value of 0 means that the objects have the same value
• a value less than 0 means that the base object should be placed before the object being compared with.

For example:

Integer x = 3;
System.out.println(x.compareTo(2)); // 1
System.out.println(x.compareTo(3)); // 0
System.out.println(x.compareTo(4)); // -1

The compare method should return:

• value less that 0 when first argument should be placed before second one
• value equal to 0 when both objects equals
• value greater than 0 when first argument should be placed after second one

For example:

Comparator<Integer> intComparator = Comparator.naturalOrder();
System.out.println(intComparator.compare(1, 2)); // -1
System.out.println(intComparator.compare(2, 2)); // 0
System.out.println(intComparator.compare(2, 1)); // 1

Comparator¶

To enable precise control of the sort order, we can use instances of comparators and pass them on, among others to sorting methods (such as Collections.sort,Arrays.sort, or the sorted methods inStream API.

Comparators can also be used to control the order of objects in data structures such as TreeMap orTreeSet.

Consider the following class:

public class User {
  private final String name;
  private final int age;

  public User(final String name, final int age) {
    this.name = name;
    this.age = age;
  }

  public String getName() {
    return name;
  }

  public int getAge() {
    return age;
  }
}

If we want to sort the list of objects of type User alphabetically, using thename field, we can use [anonymous class] (anonymous_classes.md) and the following implementation of the Comparator interface:

List<User> users = Arrays.asList(
  new User("Peter", 20),
  new User("John", 23));

Collections.sort(users, new Comparator<User>() {
  @Override
  public int compare(User o1, User o2) {
    return  (int)o1.getName().charAt(0) - (int)o2.getName().charAt(0);
  }
});

for (final User user : users) {
  System.out.println(user.getName());
}

In the example above, the first value to be written to the screen will be John, thenPeter.

Comparable¶

Using the implementation of the Comparable interface, we define the default class order according to which objects can e.g. be arranged into collections. The next example shows an implementation of the Comparable interface, where the order is based on theage field. Younger people will go before older people.

public class Sorting {

    public static void main(String[] args) {
        User[] users = new User[]{
                new User("Peter", 40),
                new User("John", 23)
        };
        Arrays.sort(users); // This method uses an implementation of the Comparable interface to sort the array
        System.out.println(Arrays.toString(users)); // output: [User{name='John', age=23}, User{name='Peter', age=40}]
    }
}

class User implements Comparable<User>{
    private String name;
    private int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public int compareTo(User o) {
        return  this.getAge() - o.age;
    }
}

Appendix - Arrays and Collections¶

Collections and arrays are widely used in most Java based applications. This is why Java offers several built-in classes which offer set of useful static methods. Below we describe some of them.

Arrays class¶

Arrays class is a utility class which provides methods which execute operations on arrays. We describe some of them below:

• binarySearch method allows finding an index of an element in a sorted array, e.g.:

int result = Arrays.binarySearch(new int[]{1, 2, 4, 5 ,6}, 5);
System.out.println(result); // 3

• asList method allows creating a list from given elements

List<Integer> ints = Arrays.asList(1, 2, 3, 4, 5);
List<Integer> ints2 = Arrays.asList(5, 2, 7, 4);

• in order to compare two arrays we can use compare method. The result 0 means that arrays are exactly the same (i.e. their elements are equal and are in the same order). In case result is negative/positive in means that first/second arrays is lexicographically less than second/first. It is possible to use equals metod for similar effect (boolean is returned, so we do not have information about lexicographical order)

int result1 = Arrays.compare(new int[]{1, 2, 3}, new int[]{1, 2, 3});
System.out.println(result1); // 0

int result2 = Arrays.compare(new int[]{1, 2}, new int[]{1, 2, 3});
System.out.println(result2); // -1

int result3 = Arrays.compare(new int[]{3, 1}, new int[]{1, 3});
System.out.println(result3); // 1

boolean result = Arrays.equals(new int[]{3, 1}, new int[]{1, 3});
System.out.println(result); // false

• we can copy array (or only part of it) with copyOf method. To display content of the array, we can use toString method, e.g.:

int[] original = new int[]{1, 2, 3, 4};
int[] copiedResult = Arrays.copyOf(original, 3);
System.out.println(Arrays.toString(copiedResult)); // [1, 2, 3]

• in order to sort an array (or only part of it) we use sort method, e.g.:

int[] ints = {3, 1, 5, 4, 2};
Arrays.sort(ints);
System.out.println(Arrays.toString(ints)); //[1, 2, 3, 4, 5]

• if we want to find index of the first element where two arrays differ from each other we can use mismatch method. Result -1 means that arrays do equal. If the return value is non-negative - it is an index of the mismatched element.

int result1 = Arrays.mismatch(new int[]{1, 2, 3}, new int[]{1, 2, 3});
System.out.println(result1); // -1

int result2 = Arrays.mismatch(new int[]{1, 2, 3}, new int[]{1, 3, 2});
System.out.println(result2); // 1

• sometime we have to convert array into a Stream. It is possible to do it with stream method, e.g.:

Arrays.stream(new int[]{1, 2, 3}) // IntStream
        .map(x -> x * 2)
        .sum(); // 12

Collections class¶

Collections class, similarly to Arrays class, offers several static method, which simplifies executing some operations on collections. We describe several of those methods below.

• to create empty (immutable) collections, we can use methods, whose name start with empty, e.g.:

List<String> list = Collections.emptyList();
Map<String, Integer> map = Collections.emptyMap();
Set<Object> set = Collections.emptySet();

list.add("2"); // UnsupportedOperationException - collection is immutable

• in addition to empty collections, Collections allows creating single element collections or synchronized collections, e.g.:

List<Integer> immutableList = Collections.singletonList(1);
Map<String, String> immutableMap = Collections.singletonMap("key", "value");
List<String> mutableList = new ArrayList<>();
mutableList.add("hi");
Collections.synchronizedSet(Set.of(1, 2, 3));

List<String> immutableWordList = Collections.unmodifiableList(mutableList);
immutableWordList.add("boom"); // UnsupportedOperationException

• min and max methods can be used to find minimum and maximum element in a collection. It is also possible to specify a Comparator:

Integer min = Collections.min(List.of(1, 2, 3));
Integer max = Collections.max(List.of(1, 2, 3));
Integer maxWithReverseOrder = Collections.max(List.of(1, 2, 3), Collections.reverseOrder());
System.out.println(min + " " + max + " " + maxWithReverseOrder); // 1 3 1

• reverse method allows reversing the order of elements in a mutable collection:

List<Integer> ints = new ArrayList<>();
ints.add(1);
ints.add(2);
ints.add(3);
Collections.reverse(ints);
ints.forEach(System.out::println); // 3 2 1

Collections.reverse(List.of(1, 2)); // List.of(...) create immutable collection -> UnsupportedOperationException is thrown

• replaceAll is a utility method which replaces all occurrences with a specified value.

List<Integer> ints = new ArrayList<>();
ints.add(1);
ints.add(2);
ints.add(2);
ints.add(3);
Collections.replaceAll(ints, 2, 4);
ints.forEach(System.out::println); // 1 4 4 3

• sorting operation can be done on a mutable collection with sort method. It is also possible to specify a Comparator, e.g.:

List<String> words = new LinkedList<>();
words.add("hi");
words.add("welcome");
words.add("hello!");
Collections.sort(words, Collections.reverseOrder());

System.out.println(words); // [welcome, hi, hello!]