Question

In this chapter we will deal with collections. Java provides specialized classes for data storage and retrieval. In one of the previous chapters, we have described arrays. Collections are enhancement to the arrays.

Java 5 introduced generic collections. The generic collections are more flexible and they are the preferred way to work with data. Generic collections enhance code reuse, type safety, and performance.

There are many classes in the collection framework. Some of them, like ArrayBlockingQueue or IdentityHashMap, are specialized containers used in specific situations. We will mention a few generic purpose containers.

ArrayList

An ArrayList is a dynamic, resizable array. It provides random access to its elements. Random access means that we can grab any element in constant time. An ArrayList automatically expands as data is added. Unlike arrays, an ArrayList can hold data of multiple data types. Elements in the ArrayList are accessed via an integer index. Indexes are zero based. Indexing of elements and insertion and deletion at the end of the ArrayList takes constant time.

Inserting or deleting an element in the middle of the dynamic array is more costly. It requires shifting all the latter elements over. The process takes linear time.

package com.zetcode;

import java.util.ArrayList;

class Base { }

public class ArrayListExample {

  public static void main(String[] args) {

    ArrayList da = new ArrayList();

    da.add("Java");
    da.add(3.5);
    da.add(55);
    da.add(new Base());

    for (Object el : da) {
      
      System.out.println(el);
    }
  }
}

In the above example, we have created an ArrayList collection. We have added some elements to it. They are of various data type.

import java.util.ArrayList;

From the java.util package, we import the ArrayList class.

ArrayList da = new ArrayList();

An ArrayList collection is created.

da.add("Java");
da.add(3.5);
da.add(55);
da.add(new Base());

We add four elements to the array with the add() method.

for (Object el : da) {
  
  System.out.println(el);
}

We iterate through the array list and print its elements to the console.

$ java com.zetcode.ArrayListExample 
Java
3.5
55
com.zetcode.Base@1535ac

Here we can see the output of the com.zetcode.ArrayListExample .

The second example will use generic collections.

package com.zetcode;

import java.util.ArrayList;
import java.util.Iterator;

public class ArrayListExample2 {

  public static void main(String[] args) {

    ArrayList<String> names = new ArrayList<String>();
    names.add("Jane");
    names.add("Thomas");
    names.add("Robin");
    names.add("David");
    names.add("Becky");
    
    System.out.println(names);  
    names.set(1, "Tom");
    System.out.println(names);     

    System.out.format("There are %d elements in the collection%n",
        names.size());

    names.remove(1);
    System.out.format("There are %d elements in the collection%n",
        names.size());      
    
    System.out.println(names.get(3));
    
    System.out.println("************");

    Iterator<String> it = names.iterator();
    
    while (it.hasNext()) {
      
      System.out.println(it.next());
    }    
  }
}

In the example we present some useful methods of the ArrayList container.

ArrayList<String> names = new ArrayList<String>();

A generic ArrayList is created. We restrict the data type of elements to String data type. This is done by writing the data type between the <> characters.

names.add("Jane");
names.add("Thomas");
names.add("Robin");
names.add("David");
names.add("Becky");

We add five string elements to the array list.

System.out.println(names); 

Putting the container as a parameter to the println() method will call the container's toString() method. It transforms the collection into a string.

names.set(1, "Tom");

The set() method replaces the element at the specified index with the given element. "Thomas" is replaced with "Tom".

System.out.format("There are %d elements in the collection%n",
    names.size());

The size of the ArrayList is determined by the size() method.

names.remove(1);

We remove the second element from the collection. The parameter is the index to the collection.

System.out.println(names.get(3));

The get() method retrieves the fourth element of the container.

Iterator<String> it = names.iterator();

while (it.hasNext()) {
  
  System.out.println(it.next());
}   

We go through the container using the Iterator object. The hasNext() method checks if there are some elements left and the next() method retrieves the next element in the iteration.

$ java com.zetcode.ArrayListExample2 
[Jane, Thomas, Robin, David, Becky]
[Jane, Tom, Robin, David, Becky]
There are 5 elements in the collection
There are 4 elements in the collection
Becky
************
Jane
Robin
David
Becky

This is a sample output of the com.zetcode.ArrayListExample2 example.

In the next example, we continue working with ArrayList .

package com.zetcode;

import java.util.ArrayList;

public class ArrayListExample3 {

  public static void main(String[] args) {
    
    ArrayList<String> names = new ArrayList<>();
    names.add("Jane");
    names.add(0, "Thomas");
    names.add(1, "Robin");
    names.add("David");
    names.add("Becky");
  
    System.out.println(names);
    
    System.out.println(names.isEmpty());
    System.out.println(names.contains("Jane"));
    System.out.println(names.contains("Robert"));
    
    System.out.println(names.indexOf("Jane"));
    
    System.out.println(names.subList(1, 4));
    
    names.clear();
    System.out.println(names.isEmpty());
    System.out.println(names);
  }
}

We show another five methods that can be used to work with ArrayLists.

ArrayList<String> names = new ArrayList<>();

Since Java 7 it is possible to omit the explicit type arguments in constructor calls to generic classes. The compiler infers the parameter types for constructors of generic classes.

names.add("Jane");
names.add(0, "Thomas");

The add() method adds a new item to the container. The overloaded second option specifies the index where the item will be placed. In the end, the "Thomas" string is located before the "Jane" string.

System.out.println(names.isEmpty());

The empty() method checks if the container is empty. The line returns false . At this moment, we have five strings in the container.

System.out.println(names.contains("Jane"));

The contains method determines if the specified element is present in the container.

System.out.println(names.indexOf("Jane"));

The indexOf() method returns the index of the first occurrence of the specified element, or -1 if the list does not contain the element.

System.out.println(names.subList(1, 4));

The subList() method returns a slice of the list between the specified indexes. The element at the first index is included in the slice, the element at the second index is not.

names.clear();

The clear() method removes all elements from the container.

$ java com.zetcode.ArrayListExample3 
[Thomas, Robin, Jane, David, Becky]
false
true
false
2
[Robin, Jane, David]
true
[]

This is the output of the com.zetcode.ArrayListExample3 .

LinkedList

A LinkedList is a doubly linked list in Java. Insertions and removals of elements take constant time. Linked lists provide sequential access to their elements, which means that grabbing elements takes linear time. Because linked lists need extra storage for references, they are impractical for lists of small data items such as characters.

package com.zetcode;

import java.util.LinkedList;

public class LinkedListExample {

  public static void main(String[] args) {
    
    LinkedList<Integer> nums = new LinkedList<>();
    
    nums.add(5);
    nums.add(10);
    nums.add(13);
    nums.add(12);
    nums.add(15);
    nums.add(23);
    
    System.out.println(nums);
    
    nums.removeFirst();
    nums.removeLast();
    nums.addFirst(17);
    nums.addLast(77);
    
    System.out.println(nums);      
  }
}

This is a LinkedList example with some of its methods.

LinkedList<Integer> nums = new LinkedList<>();

This LinkedList holds integer numbers.

nums.add(5);
nums.add(10);

We add numbers to the list. Autoboxing wraps primitive int types to the Integer objects.

nums.removeFirst();
nums.removeLast();

These two methods remove the first and the last element from the container.

nums.addFirst(17);
nums.addLast(77);

We add an element at the beginning and at the end of the list.

$ java com.zetcode.LinkedListExample 
[5, 10, 13, 12, 15, 23]
[17, 10, 13, 12, 15, 77]

The elements contained by the linked list are printed twice to the console.

HashMap

A HashMap is a container that that stores key/value pairs. Each key is associated with one value. Keys must be unique. This container type is called an associative array or a dictionary in other programming languages. HashMaps take more memory, because for each value there is also a key.

Deletion and insertion operations take constant time. HashMaps can store null values.

package com.zetcode;

import java.util.HashMap;
import java.util.Set;

public class HashMapExample {

  public static void main(String[] args) {
    
    HashMap<String, String> domains = new HashMap<>();

    domains.put("de", "Germany");
    domains.put("sk", "Slovakia");
    domains.put("us", "United States");
    domains.put("ru", "Russia");
    domains.put("hu", "Hungary");
    domains.put("pl", "Poland");  
    
    System.out.println(domains.get("pl"));
    
    for (String item : domains.values()) {
      
      System.out.println(item);
    }    
    
    Set keys = domains.keySet();
    
    System.out.println(keys);
  }
}

We have a HashMap where we map domain names to their country names.

HashMap<String, String> domains = new HashMap<>();

We create a HashMap with string keys and values.

domains.put("de", "Germany");
domains.put("sk", "Slovakia");
domains.put("us", "United States");
...

We put some data to the HashMap. The first string is the key. The second is the value.

System.out.println(domains.get("pl"));

We retrieve a specific value by its key. For the retrieval operation, we use the get method.

for (String item : domains.values()) {
  
  System.out.println(item);
}  

The values() method returns a collection of values contained in the domains HashMap . We go through the values with the for loop and print them to the console.

Set keys = domains.keySet();

The keySet() method returns the keys of the HashMap in a Set collection. A Set is a collection of unique elements.

System.out.println(keys);

The elements of the set are printed to the console.

$ java com.zetcode.HashMapExample 
Poland
Germany
Slovakia
Hungary
Poland
United States
Russia
[de, sk, hu, pl, us, ru]

This is the output of the example.

TreeMap

A TreeMap is a map that is sorted according to the natural ordering of its keys. While a HashMap is more time-efficient, a TreeMap is more space-efficient.

package com.zetcode;

import java.util.TreeMap;

public class TreeMapExample {

  public static void main(String[] args) {
    
    TreeMap<String, String> domains = new TreeMap<>();

    domains.put("de", "Germany");
    domains.put("sk", "Slovakia");
    domains.put("us", "United States");
    domains.put("ru", "Russia");
    domains.put("hu", "Hungary");
    domains.put("pl", "Poland");  
    
    System.out.println(domains);    
    System.out.println(domains.descendingMap());
  }
}

In the example, we create a TreeMap and put domains with their country names into it.

TreeMap<String, String> domains = new TreeMap<>();

A TreeMap is created.

System.out.println(domains);    

This will print the keys/values in their natural sort order — in ascending order.

System.out.println(domains.descendingMap());

THe descendingMap() method returns a reverse order view of the mappings contained in this map.

$ java com.zetcode.TreeMapExample 
{de=Germany, hu=Hungary, pl=Poland, ru=Russia, sk=Slovakia, us=United States}
{us=United States, sk=Slovakia, ru=Russia, pl=Poland, hu=Hungary, de=Germany}

The com.zetcode.TreeMapExample program printed keys with their values in ascending and descending sort order.

HashSet

A HashSet is a collection that contains no duplicate elements. This class offers constant time performance for the basic operations (add, remove, contains, and size). A HashSet does not provide ordering of elements.

package com.zetcode;

import java.util.HashSet;

public class HashSetExample {

  public static void main(String[] args) {
    
    HashSet<String> brands = new HashSet<>();
    brands.add("Pepsi");
    brands.add("Amazon");
    brands.add("Volvo");
    brands.add("IBM");
    brands.add("IBM");
    
    System.out.println(brands);   
    
    System.out.println(brands.isEmpty());
    System.out.println(brands.contains("Volvo"));
    brands.remove("Volvo");
    System.out.println(brands.contains("Volvo"));
    
    brands.clear();
    System.out.println(brands);   
  }
}

There can be only one brand registered under a name. So the brand names is a good example for a HashSet .

HashSet<String> brands = new HashSet<>();
brands.add("Pepsi");
brands.add("Amazon");
brands.add("Volvo");
brands.add("IBM");
brands.add("IBM");

We create a HashSet and add new elements. The IBM brand is added twice. However, the IBM is present in the container only once.

System.out.println(brands);   

We print all the elements in one shot.

System.out.println(brands.isEmpty());

The isEmpty() method checks if the container is empty.

System.out.println(brands.contains("Volvo"));

With the contains() method we check if the Volvo brand is present in the brands container. The line prints true .

brands.remove("Volvo");
System.out.println(brands.contains("Volvo"));

We remove the Volvo brand from the brands container. The second line prints false .

brands.clear();

The clear() method removes all of the elements from the set.

$ java com.zetcode.HashSetExample 
[IBM, Pepsi, Volvo, Amazon]
false
true
false
[]

This is the output of the com.zetcode.HashSetExample program.

TreeSet

A TreeSet is a set which has elements ordered using their natural ordering. A TreeSet is slower than a HashSet . A HashSet can contain null values, while a TreeSet cannot.

package com.zetcode;

import java.util.ArrayList;
import java.util.TreeSet;

public class TreeSetExample {

  public static void main(String[] args) {
    
    ArrayList<String> brands = new ArrayList<>();
    brands.add("Pepsi");
    brands.add("Amazon");
    brands.add("Volvo");
    brands.add("IBM");  
    brands.add("HP");
    brands.add("Apple");
    brands.add("Starbucks");
    
    TreeSet<String> brands2 = new TreeSet<>();
    brands2.addAll(brands);
    
    System.out.println(brands2);    
    System.out.println(brands2.descendingSet());
    
    System.out.println(brands2.first());
    System.out.println(brands2.last());
    
    System.out.println(brands2.headSet("IBM", true));
    System.out.println(brands2.tailSet("IBM", false));
    System.out.println(brands2.subSet("Apple", true, "Starbucks", true));    
  }
}

In this example, we work with a TreeSet .

ArrayList<String> brands = new ArrayList<>();
brands.add("Pepsi");
brands.add("Amazon");
brands.add("Volvo");
brands.add("IBM");  
brands.add("HP");
brands.add("Apple");
brands.add("Starbucks");

An ArrayList of various brands is created.

TreeSet<String> brands2 = new TreeSet<>();
brands2.addAll(brands);

With the help of the addAll() method, a new TreeSet is created from the ArrayList container.

System.out.println(brands2);    
System.out.println(brands2.descendingSet());

The elements of the container are printed to the console in ascending and descending orders.

System.out.println(brands2.first());
System.out.println(brands2.last());

We print the first and the last element of the container.

System.out.println(brands2.headSet("IBM", true));

The headSet() method returns a slice of the set whose elements are less than the specified element. The second parameter controls whether the specified element is included.

System.out.println(brands2.tailSet("IBM", false));

The tailSet() method returns a slice of the set whose elements are greater than the specified element.

System.out.println(brands2.subSet("Apple", true, "Starbucks", true));  

The subSet() method returns a portion of the container whose elements range from the first specified element to the second one.

$ java com.zetcode.TreeSetExample 
[Amazon, Apple, HP, IBM, Pepsi, Starbucks, Volvo]
[Volvo, Starbucks, Pepsi, IBM, HP, Apple, Amazon]
Amazon
Volvo
[Amazon, Apple, HP, IBM]
[Pepsi, Starbucks, Volvo]
[Apple, HP, IBM, Pepsi, Starbucks]

This is the output of the com.zetcode.TreeSetExample example.

Collections class

The Collections is a utility class that provides many useful methods for working with containers. It consists exclusively of static methods. Some of the methods are not applicable to all collection types. For example, it is not possible to use the sort() method on a HashSet , because this container does not support ordered elements.

package com.zetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;


public class CollectionsExample {

  public static void main(String[] args) {
    
    Integer[] nums = { 4, 3, 2, 4, 5, 6, 4, 2, 7, 8, 9, 0, 1 };
    
    ArrayList<Integer> ns = new ArrayList<>(Arrays.asList(nums));
    System.out.println("Default order:");
    System.out.println(ns);
  
    System.out.println("Ascending order:");
    Collections.sort(ns);
    System.out.println(ns);
    
    System.out.println("Descending order:");
    Collections.reverse(ns);
    System.out.println(ns);
    
    System.out.println("Swapping the first and the last elements:");
    Collections.swap(ns, 0, ns.size()-1);
    System.out.println(ns);
    
    System.out.println("Replacing all 4s with 0s:");
    Collections.replaceAll(ns, 4, 0);
    System.out.println(ns);
    
    System.out.println("Random order:");
    Collections.shuffle(ns);
    System.out.println(ns);
    
    System.out.println(Collections.max(ns));
    System.out.println(Collections.min(ns));
  }
}

In the example, we use several methods of the Collections class.

Integer[] nums = { 4, 3, 2, 4, 5, 6, 4, 2, 7, 8, 9, 0, 1 };

ArrayList<Integer> ns = new ArrayList<>(Arrays.asList(nums));

An ArrayList is created from an array of Integers. The asList() method of the Arrays class is used to transform an array into a list which is then passed to the constructor.

Collections.sort(ns); 

The sort() method sorts the elements in ascending order.

Collections.reverse(ns);

The reverse() method reverses the order of elements in the list.

Collections.swap(ns, 0, ns.size()-1);

The swap() method exchanges two elements. The first element with the last element in our case.

Collections.replaceAll(ns, 4, 0);

This line replaces all occurrences of number 4 with 0.

Collections.shuffle(ns);

The shuffle() method randomly reorders the elements in the container.

System.out.println(Collections.max(ns));
System.out.println(Collections.min(ns));

Here we print the maximum and the minimum values of the list.

$ java com.zetcode.CollectionsExample 
Default order:
[4, 3, 2, 4, 5, 6, 4, 2, 7, 8, 9, 0, 1]
Ascending order:
[0, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9]
Descending order:
[9, 8, 7, 6, 5, 4, 4, 4, 3, 2, 2, 1, 0]
Swapping the first and the last elements:
[0, 8, 7, 6, 5, 4, 4, 4, 3, 2, 2, 1, 9]
Replacing all 4s with 0s:
[0, 8, 7, 6, 5, 0, 0, 0, 3, 2, 2, 1, 9]
Random order:
[1, 6, 2, 8, 0, 2, 0, 9, 5, 0, 7, 3, 0]
9
0

This is a sample output of the com.zetcode.CollectionsExample program.

This part of the Java tutorial was dedicated to collections in Java.