Java collections


Creative Commons License
This -Java collections- tutorial is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Preamble

This tutorial is about collections in Java up to Java ver. 8 only.

Headlines
Java iteration on collections has been simplified from Java 5.

Example

java.util.Collection<Boolean> my_collection = new java.util.LinkedList<>(); // Diamond-based instantiation
java.util.Random random = new java.util.Random();
// Old style:
for(int i = 0;i < 5;i++) {
    boolean b = random.nextBoolean();
    my_collection.add(b);
}
// New style:
for(Boolean b : my_collection) System.out.print("\t" + b);
Java sequences are basic collections including (advanced) arrays (e.g., java.util.Vector<E>), lists, etc. Java offers the java.util.List<E> interface as key functional entry point.

Rule(s)

Example (basic usage)

public class Prisoner {
    …
    final java.util.List<Criminal_case> _all_criminal_cases = new java.util.LinkedList<>(); // Ver. 1
// First alternative:
    final java.util.List<Criminal_case> _all_criminal_cases = new java.util.ArrayList<>(); // Ver. 2
// Second alternative:
    final java.util.Deque<Criminal_case> _all_criminal_cases = new java.util.ArrayDeque<>(); // Ver. 3
// Insertion in Java sequences:
    public void involve(Criminal_case criminal_case) {
        boolean result = _all_criminal_cases.add(criminal_case);
        assert result;
    }
    …
}

Example (advanced usage)

// Adding at the end ('_all_criminal_cases' is typed with 'java.util.List<>'):
_all_criminal_cases.add(criminal_case)
// Adding at the beginning ('_all_criminal_cases' is typed with 'java.util.List<>'):
_all_criminal_cases.add(0,criminal_case);
// Adding at the end ('_all_criminal_cases' is typed with 'java.util.LinkedList<>'):
_all_criminal_cases.addLast(criminal_case);
// Adding at the beginning ('_all_criminal_cases' is typed with 'java.util.LinkedList<>'):
_all_criminal_cases.addFirst(criminal_case);
// Getting the last one:
public Criminal_case last() { // ('_all_criminal_cases' is typed with 'java.util.LinkedList<>')
    return _all_criminal_cases.isEmpty() ? null : _all_criminal_cases.getLast();
}
// Getting the last one, alternative:
public Criminal_case last() { // ('_all_criminal_cases' is typed with 'java.util.List<>')
    Criminal_case last = null;
    java.util.ListIterator<Criminal_case> iterator = _all_criminal_cases.listIterator();
    while(iterator.hasNext()) last = iterator.next();
    return last;
}

See also

Java sets are collections without duplicates. Java offers two interfaces as functional entry points: java.util.Set<E> and java.util.SortedSet<E>.

Example (basic usage)

public class Jail {
    final java.util.Set<Prisoner> _prisoners = new java.util.HashSet<>(); // Loss of insertion order
// First alternative:
    final java.util.Set<Prisoner> _prisoners = new java.util.LinkedHashSet<>(); // Preservation of insertion order
// Second alternative:
    final java.util.Set<Prisoner> _prisoners = new java.util.TreeSet<>(); // Preservation of insertion order with 'Comparable<T>'
// Insertion in Java sets:
    public void incarcerate(Prisoner prisoner) {
        boolean result = _prisoners.add(prisoner);
        assert result;
    }
    …
}

Example (advanced usage)

Specification
Implementation Set_illustration.Java.zip 
public class Set_illustration<T> extends java.util.HashSet<T> {
    public boolean strict_subset(final Set_illustration<T> s) {
        return s.containsAll(this) && !s.equals(this);
    }
    public Set_illustration() {
        super();
    }
    public Set_illustration(java.util.Collection<? extends T> s) {
        super(s);
    }
    public Set_illustration<T> difference(final Set_illustration<T> s) { // 's' = F
        Set_illustration<T> difference = new Set_illustration<>(this); // 'this' = 'E'
        difference.removeIf((T t) -> s.contains(t));
        return difference;
    }
    public Set_illustration<T> symmetrical_difference(final Set_illustration<T> s) {
        Set_illustration<T> symmetrical_difference = new Set_illustration<>(this);
        symmetrical_difference.addAll(s);
        Set_illustration<T> intersection = new Set_illustration<>(this);
        intersection.retainAll(s);
        // Formally, symetrical symmetrical_difference is 'union - intersection':
        symmetrical_difference.removeIf((T t) -> intersection.contains(t));
        return symmetrical_difference;
    }
    public static void main(String args[]) {
        Set_illustration<Character> E = new Set_illustration<Character>();
        Set_illustration<Character> F = new Set_illustration<Character>();
        E.add('a');
        F.add('a');
        F.add('b');
        System.out.println("E strictly included in F ? " + E.strict_subset(F)); // 'true'
        E.add('b');
        System.out.println("E strictly included in F ? " + E.strict_subset(F)); // 'false'
        F.remove('b');
        F.add('c');
        Set_illustration<Character> difference = E.difference(F);
        System.out.print("E - F: ");
        difference.forEach((c) -> {
            System.out.print(c + " "); // 'b'
        });
        System.out.print("\nE - F (symmetrical): ");
        Set_illustration<Character> symmetrical_difference = E.symmetrical_difference(F);
        symmetrical_difference.forEach((c) -> {
            System.out.print(c + " "); // 'b', 'c'
        });
    }
}

Rule(s)

Example (overriding equals, and therefore hashCode, inherited Java methods)

public class Prisoner {
    final String _prison_file_number;
    Prisoner(String prison_file_number) {
        _prison_file_number = prison_file_number;
    }
    public boolean equals(Object object) {
        return this == object ? true : object instanceof Prisoner ?
            _prison_file_number.equals(((Prisoner)object)._prison_file_number) : false;
    }
    public int hashCode() {
        return _prison_file_number.hashCode();
    }
    …
}

Rule(s)

Example

public enum Temperature_unit {
    Celsius("°C"), Fahrenheit("°F"), Kelvin("°K");

    final String _literal;
    private Temperature_unit(String literal) { _literal = literal; }
    public String toString() { return _literal; }
}
…
Temperature_unit tu = Temperature_unit.Celsius;
System.out.println(tu.toString()); // '°C' is displayed

Example

enum Decision_type {Conviction, Shortened_sentence, Final_discharge}
Enum<Decision_type> decision_type; // <=> 'Decision_type decision_type;'

See also

Java maps are hash tables (a.k.a. dictionaries, hash maps or maps for short), i.e., associative containers.

Rule(s)

Example (hashCode algorithm for String)

String s = "CC"; // ASCII value of 'C' is '67'
assert(s.hashCode() == 2144); // Algorithm: 67 * 31pow(0) + 67 * 31pow(1) = 2144

Example (basic usage)

java.util.Map<Integer,Double> polynomial = new java.util.Hashtable<>();
polynomial.put(1,-12.D);
polynomial.put(39,8.D);

java.util.Map<Object,String> my_map = new java.util.Hashtable<>();
Object o1 = new Object();
my_map.put(o1,"inserted string at the ‘o1’ index (key)");
String s = my_map.get(o1);
assert(s.equals("inserted string at the ‘o1’ index (key)") == true);

Rule(s)

Example (String objects differ in terms of content) Hashtable_illustration.Java.zip 

String s1 = "Franck";
String s2 = "Franck";
assert (s1 != s2); // 's1' and 's2' are NOT the same memory object
assert (s1.equals(s2)); // However, 's1' equals 's2'
assert (s1.hashCode() == s2.hashCode());

Example (String as “key” type)

java.util.Map<String, Integer> my_map = new java.util.HashMap<>();
String s1 = "A";
String s2 = "A";
my_map.put(s1, 1);
my_map.put(s2, 2);  
System.out.println (my_map.get(s1)); // '2'

Rule(s)

Example (advanced usage) Hashtable_illustration.Java.zip 

int max = 100;
float theta = 0.5F;
java.util.Map<String, String> given_names__dictionary = new java.util.HashMap<>(max, theta);
given_names__dictionary.put("Franck", "German origin...");
given_names__dictionary.put("Frank", "English origin...");
assert (given_names__dictionary.size() == 2);

java.util.Map<Object, String> hashtable_with_possible_null_keys = new java.util.HashMap<>();
hashtable_with_possible_null_keys.put(null, "Allowing 'null' keys");
System.out.println(hashtable_with_possible_null_keys.get(null));

Rule(s)

See also

Java priority queues (a.k.a. heaps) keep a natural ordering or apply that provided by java.util.Comparator<T>.
Internal representation

Example Heap.Java.zip 

java.util.Comparator<Short> comparator = (Short i, Short j) -> {
    return i - j;
};

java.util.PriorityQueue<Short> my_priority_queue = new java.util.PriorityQueue<>(10, comparator);
short native_tab[] = {13, 12, 11, 8, 7, 6, 4, 3};
for (short s : native_tab) {
    my_priority_queue.add(s);
}
my_priority_queue.forEach((s) -> {
    System.out.print("\t" + s); // '3   4   6   8   11  12  7   13' is displayed...
});

See also

java.util.Collections utility class is not a common container! It is mainly used for collection creation, conversion (from native arrays especially), sorting and other generic algorithms like C++ generic algorithms.

Example

short native_tab[] = {3, 4, 6, 7, 8, 11, 12, 13};

java.util.List<Short> advanced_tab = new java.util.Vector<>();
for (int i = 0; i < native_tab.length; i++) advanced_tab.add(native_tab[i]);

java.util.Collections.shuffle(advanced_tab); // Random permutation of elements to loose the initial order
for (short s : advanced_tab) System.out.print("\t" + s);

System.out.print(java.util.Collections.binarySearch(advanced_tab, (short) 0)); // '-1' (insertion point) is returned since '0' is not present in 'advanced_tab'

java.util.Collections.sort(advanced_tab);
for (short s : advanced_tab) System.out.print("\t" + s);
User-defined collections allow the extension of the container type pool offered by Java. For example, a AVL tree is such a user-defined container.

Example Binary_tree.Java.zip 

public class Binary_tree<T> {
    protected T _content;
    protected Binary_tree<T> _left, _right, _super;
    public void infix() {
        if (_left != null) {
            _left.infix();
        }
        System.out.println();
        if (_right != null) {
            _right.infix();
        }
    } // a+b-c*d

    public void prefix() {
        System.out.println();
        if (_left != null) {
            _left.prefix();
        }
        if (_right != null) {
            _right.prefix();
        }
    } // +a*-bcd
    public void postfix() {
        if (_left != null) {
            _left.postfix();
        }
        if (_right != null) {
            _right.postfix();
        }
        System.out.println();
    } // abc-d*+
    public int h() {
        if (_super == null) {
            return 0;
        }
        return _super.h() + 1;
    }
    public int H() {
        int H_left, H_right;
        if (_left != null) {
            H_left = _left.H() + 1;
        } else {
            H_left = 0;
        }
        if (_right != null) {
            H_right = _right.H() + 1;
        } else {
            H_right = 0;
        }
        return H_left < H_right ? H_right : H_left;
    }
    public boolean isAVL() {
        if (_left == null && _right == null) {
            return true;
        }
        if (_left == null) {
            return _right.H() < 1;
        }
        if (_right == null) {
            return _left.H() < 1;
        }
        return false;
    }