Immutable Empty Collections and iterators in Java with Examples

Sometimes it is appropriate to use an immutable empty collection. There are several ways to create immutable empty List in Java. The Immutable Empty Collections class provides methods to get such collections in an efficient way:

List anEmptyList = Collections.emptyList();
Map anEmptyMap   = Collections.emptyMap();
Set anEmptySet   = Collections.emptySet();

These methods are generic and will automatically convert the returned collection to the type it is assigned to. That is, an invocation of e.g. emptyList() can be assigned to any type of List and likewise for emptySet() and emptyMap().

The collections returned by these methods are immutable in that they will throw UnsupportedOperationException if you attempt to call methods which would change their contents (add, put, etc.). These collections are primarily useful as substitutes for empty method results or other default values, instead of using null or creating objects with new.

Sub Collections

List subList(int fromIndex, int toIndex)

Here fromIndex is inclusive and toIndex is exclusive.

List list = new ArrayList();
List list1 = list.subList(fromIndex,toIndex);
  1. If the list doesn’t exist in the give range, it throws IndexOutofBoundException.
  2. What ever changes made on the list1 will impact the same changes in the list.This is called backed collections.
  3. If the fromnIndex is greater than the toIndex (fromIndex > toIndex) it throws IllegalArgumentException.

Example:

List list = new ArrayList();
List list = new ArrayList();
list.add("Hello1");
list.add("Hello2");
System.out.println("Before Sublist "+list);
List list2 = list.subList(0, 1);
list2.add("Hello3");
System.out.println("After sublist changes "+list);
Output:
Before Sublist [Hello1, Hello2]
After sublist changes [Hello1, Hello3, Hello2]

Set subSet(fromIndex,toIndex)

Here fromIndex is inclusive and toIndex is exclusive.

Set set = new TreeSet();
Set set1 = set.subSet(fromIndex,toIndex);

The returned set will throw an IllegalArgumentException on an attempt to insert an element outside its range.

Map subMap(fromKey,toKey)

fromKey is inclusive and toKey is exclusive

Map map = new TreeMap();
Map map1 = map.get(fromKey,toKey);

If fromKey is greater than toKey or if this map itself has a restricted range, and fromKey or toKey lies outside the bounds of the range then it throws IllegalArgumentException.

All the collections support backed collections means changes made on the sub collection will have same change on the main collection.

Unmodifiable Collection

Sometimes it’s not a good practice expose an internal collection since it can lead to a malicious code vulnerability due to it’s mutable characteristic. In order to provide “read-only” collections java provides its unmodifiable versions.

An unmodifiable collection is often a copy of a modifiable collection which guarantees that the collection itself cannot be altered. Attempts to modify it will result in an UnsupportedOperationException exception.

It is important to notice that objects which are present inside the collection can still be altered.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class MyPojoClass {
     private List intList = new ArrayList<>();

     public void addValueToIntList(Integer value){
         intList.add(value);
}

    public List getIntList() {
        return Collections.unmodifiableList(intList);
    }
}

The following attempt to modify an unmodifiable collection will throw an exception:

import java.util.List;

public class App {

     public static void main(String[] args) {
          MyPojoClass pojo = new MyPojoClass();
          pojo.addValueToIntList(42);

          List list = pojo.getIntList();
          list.add(69);
     }
}

output:

Exception in thread “main” java.lang.UnsupportedOperationException
at java.util.Collections$UnmodifiableCollection.add(Collections.java:1055)
at App.main(App.java:12)

Pitfall: concurrent modification exceptions

This exception occurs when a collection is modified while iterating over it using methods other than those provided by the iterator object. For example, we have a list of hats and we want to remove all those that have ear flaps:

List hats = new ArrayList<>();
hats.add(new Ushanka()); // that one has ear flaps
hats.add(new Fedora());
hats.add(new Sombrero());
for (IHat hat : hats) {
      if (hat.hasEarFlaps()) {
           hats.remove(hat);
       }
}

If we run this code, ConcurrentModificationException will be raised since the code modifies the immutable empty collection while iterating it. The same exception may occur if one of the multiple threads working with the same list is trying to modify the collection while others iterate over it. Concurrent modification of collections in multiple threads is a natural thing, but should be treated with usual tools from the concurrent programming toolbox such as synchronization locks, special collections adopted for concurrent modification, modifying the cloned collection from initial etc.

Removing matching items from Lists using Iterator

Above I noticed an example to remove items from a List within a Loop and I thought of another example that may come in handy this time using the Iterator interface. This is a demonstration of a trick that might come in handy when dealing with duplicate items in lists that you want to get rid of.

Note: This is only adding on to the Removing items from a List within a loop example:

So let’s define our lists as usual

String[] names = {"James","Smith","Sonny","Huckle","Berry","Finn","Allan"};
List nameList = new ArrayList<>();

//Create a List from an Array
nameList.addAll(Arrays.asList(names));

String[] removeNames = {"Sonny","Huckle","Berry"};
List removeNameList = new ArrayList<>();

//Create a List from an Array
removeNameList.addAll(Arrays.asList(removeNames));

The following method takes in two Collection objects and performs the magic of removing the elements in our removeNameList that match with elements in nameList.

private static void removeNames(Collection collection1, Collection collection2) {   //get Iterator.
      Iterator iterator = collection1.iterator();

     //Loop while collection has items
     while(iterator.hasNext()){
           if (collection2.contains(iterator.next()))
                  iterator.remove(); //remove the current Name or Item
     }
}

Calling the method and passing in the nameList and the removeNameListas follows removeNames(nameList,removeNameList);
Will produce the following output:

Array List before removing names: James Smith Sonny Huckle Berry Finn Allan
Array List after removing names: James Smith Finn Allan

A simple neat use for Collections that may come in handy to remove repeating elements within lists.

Join lists

Following ways can be used for joining lists without modifying source list(s).
First approach. Has more lines but easy to understand

List newList = new ArrayList();
newList.addAll(listOne);
newList.addAll(listTwo);

Second approach. Has one less line but less readable.

List newList = new ArrayList(listOne);
newList.addAll(listTwo);

Third approach. Requires third party Apache commons-collections library.

ListUtils.union(listOne,listTwo);
Version ≥ Java SE 8

Using Streams the same can be achieved by

List newList = Stream.concat(listOne.stream(),
listTwo.stream()).collect(Collectors.toList());

Creating your own Iterable structure for use with Iterator or for-each loop

To ensure that our collection can be iterated using iterator or for-each loop, we have to take care of following steps:

  1. The stuff we want to iterate upon has to be Iterable and expose iterator().
  2. Design a java.util.Iterator by overriding hasNext(), next() and remove().

I have added a simple generic linked list implementation below that uses above entities to make the linked list iterable.

package org.algorithms.linkedlist;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedList implements Iterable {

     Node head, current;
     private static class Node {
        T data;
        Node next;
        Node(T data) {
            this.data = data;
        }
    }

    public LinkedList(T data) {
       head = new Node<>(data);
    }
    public Iterator iterator() {
       return new LinkedListIterator();
   }

   private class LinkedListIterator implements Iterator {

        Node node = head;
        @Override
        public boolean hasNext() {
             return node != null;
        }
        @Override
        public T next() {
            if (!hasNext())
              throw new NoSuchElementException();
            Node prevNode = node;
            node = node.next;
            return prevNode.data;
       }

       @Override
       public void remove() {
           throw new UnsupportedOperationException("Removal logic not implemented.");
       }
    }
    public void add(T data) {
           Node current = head;
           while (current.next != null)
                current = current.next;
           current.next = new Node<>(data);
    }
}
class App {
    public static void main(String[] args) {
         LinkedList list = new LinkedList<>(1);
         list.add(2);
         list.add(4);
         list.add(3);

         //Test #1
         System.out.println("using Iterator:");
         Iterator itr = list.iterator();
         while (itr.hasNext()) {
               Integer i = itr.next();
               System.out.print(i + " ");
         }

         //Test #2
         System.out.println("\n\nusing for-each:");
         for (Integer data : list) {
              System.out.print(data + " ");
         }
    }
}

Output:

using Iterator:
1 2 4 3
using for-each:
1 2 4 3

This will run in Java 7+. You can make it run on Java 5 and Java 6 also by substituting:

LinkedList list = new LinkedList<>(1);
with
LinkedList list = new LinkedList(1);

or just any other version by incorporating the compatible changes.

Collections and Primitive Values

Collections in Java only work for objects. I.e. there is no Map in Java. Instead, primitive values need to be boxed into objects, as in Map. Java auto-boxing will enable transparent use of these collections:

Map map = new HashMap<>();
map.put(1, 17); // Automatic boxing of int to Integer objects
int a = map.get(1); // Automatic unboxing.

Unfortunately, the overhead of this is substantial. A HashMap will require about 72 bytes per entry (e.g. on 64-bit JVM with compressed pointers, and assuming integers larger than 256, and assuming 50% load of the map). Because the actual data is only 8 bytes, this yields a massive overhead. Furthermore, it requires two level of indirection (Map -> Entry -> Value) it is unnecessarily slow.

There exist several libraries with optimized collections for primitive data types (that require only ~16 bytes per entry at 50% load, i.e. 4x less memory, and one level of indirection less), that can yield substantial performance benefits when using large collections of primitive values in Java.

LEAVE A REPLY

Please enter your comment!
Please enter your name here