Java Collections

java

Java Collections

Introduction

A collection is a data structure with a group of elements. Here is the hierarchy of Java collection framework:

java_collection_1

All the classes shown in the above picture are interfaces, and java.util.Collection and java.util.Map are the two main “root” interfaces of Java collection classes.

java.lang.Iterable

As shown in the collection framework, java.util.Collection is a sub-interface of java.lang.Iterable:

1
public interface Collection<E> extends Iterable<E>

java.util.Iterator is an indepent interface. However, in Iterable there is a method called iterator, which can return an Iterator object:

1
2
3
// iterator is an instance method, which 
// returns an Iterator object. 
Iterator<E> iterator();

Therefore, all sub-interfaces of Iterable(such as List and Set) can use Iterator. For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.*;

public class IterableDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("I");
        list.add("like");
        list.add("water");

        Iterator<String> iterator1 = list.iterator();

        while (iterator1.hasNext()) {
            String s = iterator1.next();
            System.out.print(s);
            System.out.print(" ");
        }

        System.out.println();

        Set<String> set = new HashSet<>();
        set.addAll(list);

        Iterator<String> iterator2 = set.iterator();
        
        while (iterator2.hasNext()) {
            String s = iterator2.next();
            System.out.print(s);
            System.out.print(" ");
        }
    }
}

The output of the above code is:

1
2
I like water 
like I water

The Iterable interface also provides a forEach method, which is a higher-order method:

1
2
3
4
5
6
7
8
9
10
11
// forEach method is an instance method, which 
// makes use of iterator mehod.
void forEach(Consumer<E> action) {
        
    Iterator iterator = this.iterator();
    
    while(iterator.hasNext()) {
        E e = iterator.next();
        action.accept(e);
    }
}

Similarly, all sub-interfaces of Iterable(such as List and Set) can use forEach:

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;

public class IterableDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("I");
        list.add("like");
        list.add("water");

        list.forEach(s -> System.out.println(s));        
    }
}

The output of the above code is:

1
2
3
I
like
water

java.util.Collection

There are different kinds of collections in Java, which are defined as interfaces:

  • A List is a collection where the elements are stored in a particular order.

  • A Set is a collection of distinct elements(no duplicates) in no particular order.

  • A SortedSet is a Set whose elements can be enumerated in sorted order.

  • A Queue is like a List, which only allows insertions/deletions at the end points.

Each interface above has one or more implementations.

The List interface has two implementations:

  1. ArrayList: ArrayList, which uses array to implement the list. All the elements of an arraylist are stored in consecutive locations of memory. The time complexity of accessing arbitrary elements is O(1), and the time complexity of insertion/deletion is O(n). ArrayList is a resizable array, which has a growth policy.

  2. LinkedList: LinkedList, which uses linkedlist to implement the list. The elements are stored in nodes and linked to each other via references. The time complexity of accessing arbitrary elements is O(n), and the time complexity of insertion/deletion is O(1).

The Set interface also has two implementations:

  1. TreeSet: TreeSet, which uses red-black tree(a kind of AVL tree) to implement set. TreeSet is sorted, therefore it only accept objects that implement Comparable interface. The operations of TreeSet, such as searching or insertion/deletion, are in O(log_n).

  2. HashSet: HashSet, which uses hash table to implement set. HashSet requires the element type to have hashCode functions. Normally, the operaions like searching or insertion/deletion are in O(1). But when the hash table gets relatively full, it would degenerate to O(n). HashSet also wastes memory space.

java.util.Map

A Map is a collection of entries. Every entry has two things: the key that we can search for, and the value that is associated with the key. 

1
2
3
// There are two type parameters to the Map type: 
// K for the “key” type and V for the “value” type.
public interface Map<K, V>

Note that in a map, the number of values may not be same as the number of keys, i.e., the number of values could be fewer than the number of the keys. The number of entries is the same as the number of keys.

There are several implementations of Map:

  1. TreeMap<K, V>: TreeMap, which uses tree(O(log_n)) to implement map. TreeMap is actually SortedMap. The key type K should be Comparable, while the value type V needs not be Comparable.

  2. HashMap<K, V>:HashMap, which uses hash table(O(1)) to implement map, and the key type K needs to have hashCode functions.

Maps are not collections, however, they are also iterable. Maps have an operation that returns their entries as a set:

1
Set<Map.Entry<K, V>> entrySet ();

Therefore, we can firstly obtain the entrySet of a map, then iterate the set using a forEach operator. For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;

public class IterableDemo {
    public static void main(String[] args) {
        SortedMap<String, String> students =
                new TreeMap<String, String>();

        students.put("2016205047", "Leslie Tang");
        students.put("2016205046", "Super King");
        students.put("2016205027", "CC Huang");

        Set<Map.Entry<String, String>> entries = students.entrySet();// obtain the entrySet
        entries.forEach(e -> System.out.println(e.getKey() + " : " + e.getValue()));// iterate the set
    }
}

The output of the above code is:

1
2
3
2016205027 : CC Huang
2016205046 : Super King
2016205047 : Leslie Tang

Besides, Maps also have their own forEach operators:

1
2
3
4
5
6
7
8
9
10
11
12
void forEach(BiConsumer<K,V> action) {     
    Object k;
    Object v;
    Iterator iterator = this.entrySet().iterator();
    
    while(iterator.hasNext()) {      
        Map.Entry entry = (Map.Entry)iterator.next();
        k = entry.getKey();
        v = entry.getValue();
        action.accept(k, v)          
    }
}

Therefore, we can iterate a map using forEach:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

public class IterableDemo {
    public static void main(String[] args) {
        SortedMap<String, String> students =
                new TreeMap<String, String>();

        students.put("2016205047", "Leslie Tang");
        students.put("2016205046", "Super King");
        students.put("2016205027", "CC Huang");

        students.forEach((k, v) -> System.out.println(k + " : " + v));
    }
}

The output of the above code is:

1
2
3
2016205027 : CC Huang
2016205046 : Super King
2016205047 : Leslie Tang