Laboratory Training 4
Working with Generics and Collections
1 Training Tasks
1.1 Individual Task
Add new classes to the hierarchy of classes created by implementing of the individual task given in the
Laboratory training #2. You should add derived classes that represent
the first of the entities of the individual task. The first class should represent data using list
(ArrayList), the second should use set (SortedSet).
Use Collections class to sort the list. When working with set, you should consistently create multiple sets sorted according to different criteria.
Test both implementations. The results of the programs should match.
1.2 Enumeration for Representation of Months of the Year
Create enumeration that represents months of the year. It is necessary to define the constructor
and store the number of days (for non-leap year). Add methods of getting previous and next month, and a function
that returns a season for particular month. Create static method that prints all months. Test enumeration
in main() function of some test class.
1.3 Creation of a Library that Provides Generic Functions for Working with Arrays
Create a class with static generic methods that implement this functionality:
- swap of two groups of items
- swap of all neighbour items (with even and odd indices)
- inserting items of another array in the specified location
- replacement of some group with items of another array
Demonstrate the work of all methods using data of different types (Integer,
Double, String).
1.4 Creation of a Library that Provides Generic Functions for Working with Lists of Numbers
Create a class that contains static generic functions for implementing such actions with a list of
numbers (objects derived from Number):
- finding the index of the first zero element
- counting of the number of negative numbers
- return the last negative element
Test all functions on lists of numbers of different types.
1.5 Finding Different Words in a Sentence
Enter a sentence, create a collection (SortedSet) of different words in a sentence, and
display all these words in alphabetical order.
1.6 Data about Users
Present data about users in an associative array (username / password) with the assumption that all usernames are different. Display user information with a password length of more than 6 characters.
1.7 Creating a Custom Container Based on an Array
Create a generic class to represent a one-dimensional array, whose index of items varies from a certain
value from to value to inclusive. These values can be either positive or
negative. The class must implement the Collection interface. It is advisable to use the
AbstractList class as a base class.
1.8 Implementation of the Doubly-Linked List (Advanced Task)
Implement a generic class representing a doubly-linked list.
1.9 Implementation of the Element Removal Functions from the Tree (Advanced Task)
Add to the example 3.8 the function of deleting a given item from a tree.
1.10 Implementation of the Red-Black Tree (Advanced Task, Optional)
Independently implement associative array based on a red-black tree.
2 Instructions
2.1 Enumerations
Java 5 (since JDK 1.5) supports new reference type called enum
(enumeration). Enumeration represents a list of possible values that a variable of this type
can receive. In simplest case, their usage looks like one in C++ or C#.
enum DayOfWeek {
SUNDAY,
MONDAY,
TUESDAY,
WEDNESDAY,
THURSDAY,
FRIDAY,
SATURDAY
}
...
DayOfWeek d = DayOfWeek.WEDNESDAY;
Listed constants are public. The enum type itself can be public or
default. Names of possible values should be written using uppercase letters, because in fact they are
constants. These constants are associated with integer values. In the following example, these values
range respectively from 0 to 6. You can get these integer values using the ordinal()
method. Constant can be obtained using the name() method. For example:
DayOfWeek d = DayOfWeek.WEDNESDAY; System.out.println(d.name() + " " + d.ordinal());
The values() static function returns array of enumeration items:
for (int i = 0; i < DayOfWeek.values().length; i++) {
System.out.println(DayOfWeek.values()[i]);
}
The static valueOf() function allows you to get the item of enumeration by
its name. For example, you can get the integer value associated with a specific item:
System.out.println(DayOfWeek.valueOf("FRIDAY").ordinal());
In general, Java enumerations provide opportunities for defining and overloading
methods, creating additional fields, and so on. For example, the DayOfWeek enumeration can
be extended by printAll() static method:
static void printAll() {
for (DayOfWeek d : values()) {
System.out.println(d);
}
}
You can overload the output of enumeration via toString() function:
enum Gender {
MALE, FEMALE;
@Override
public String toString() {
switch (this) {
case MALE:
return "male gender";
case FEMALE:
return "female gender";
}
return "something impossible!";
}
}
public class GenderTest {
public static void main(String[] args) {
Gender g = Gender.FEMALE;
System.out.println(g);
}
}
The constants can be associated with some values. For example, an enumeration "Satellite of Mars" contains field "Distance from the center of Mars". We must also add a constructor and additional field and getter:
package ua.in.iwanoff.java.fourth;
enum MoonOfMars {
PHOBOS(9377), DEIMOS(23460);
private double distance;
private MoonOfMars(double distance) {
this.distance = distance;
}
double getDistance() {
return distance;
}
@Override
public String toString() {
return name() + ". " + distance + " km. from Mars";
}
}
public class MoonsOfMarsTest {
public static void main(String[] args) {
MoonOfMars m = MoonOfMars.PHOBOS;
System.out.println(m); // PHOBOS. 9377.0 km from Mars
}
}
As can be seen, the presence of constructor requires definition of constants with actual parameters.
2.2 Generics
2.2.1 The Concept of Generic Programming
Often there is a need for so-called container classes that contain objects of arbitrary types. Sometimes, objects of different types held in containers require applying the same actions. The code for processing objects of different types looks almost the same. This is especially true if the different types of data needed to implement algorithms such as quick sorting or processing linked lists, binary trees, etc. In such cases, the code is the same for all types of objects.
Generic programming is a programming paradigm that provides a description of the data storage rules and algorithms in general form, regardless of the specific data types. Specific data types to which actions are applied are specified later. The mechanisms separating data structures and algorithms, as well as the formulation of abstract descriptions of data requirements are defined differently in different programming languages. First, generic programming opportunities presented in the seventies of the twentieth century in CLU and Ada languages (generic functions) and were later implemented in the ML language (parametric polymorphism).
The idea of generic programming is implemented in C++ most fully and flexibly thanks to the templates mechanism. A template in C++ is a code snippet that describes a generalized work on some abstract type, specified as a template parameter. This piece of code (class or function)) can be finally compiled only after template instantiation, i.e. after substituting a specific type instead of a template parameter. The Standard Template Library (STL) is based on the use of template functions and parameterized classes. STL includes a description of standard container classes and their generic algorithms.
To implement generic programming, Java offers generics - a special language feature that appeared in the language syntax starting with the Java 5 version.
2.2.2 Problems of Creating Universal Containers in Java 2
Suppose we need to create a container to store a pair of objects of the same type. The simplest container
class (Pair) will contain two references to the Object class:
public class Pair {
Object first, second;
public Pair(Object first, Object second) {
this.first = first;
this.second = second;
}
}
Since Object is the base class for all reference types, you can, for example, use this class
to store a pair of strings:
Pair p = new Pair("Surname", "Name");
This approach has some drawbacks:
- To read objects, you need to use explicit type conversion:
String s = (String) p.first; // Instead of String s = p.first;
Integer i = (Integer) p.second; // Runtime error
Pair p1 = new Pair("Surname", new Integer(2)); // No any error messages
Similar problems occurred in the Java 2 with standard container classes. This resulted in potential runtime errors that could not be found at compile time.
2.2.3 The Syntax of Generics
Starting with version 5, Java allows you to create and use generics - a syntax construct that can be used for definition of classes and functions with extra parameters, which contain additional information about data types. These parameters are taken in angular brackets. Generics provide the ability to create and use type safe containers. Classes described using such parameters are called generic classes. When you create a generalized class object, you must specify names instead of the parameters. Only reference types can be used. The previous example can be implemented using generics.
public class Pair<T> {
T first, second;
public Pair(T first, T second) {
this.first = first;
this.second = second;
}
public static void main(String[] args) {
Pair<String> p = new Pair<String>("Surname", "Name");
String s = p.first; // Get string value without type casting
Pair<Integer> p1 = new Pair<Integer>(1, 2); // You can use integer constants
int i = p1.second; // Get integer value without type casting
}
}
Note: Java 7 (and above) allows you to not repeat the actual parameter of generic after the constructor name. For example:
Pair<Integer> p1 = new Pair<>(1, 2);
If you try to add a couple different data types, the compiler will generate an error. Is also erroneous attempt to explicitly convert type:
Pair<String> p = new Pair<String>("1", "2");
Integer i = (Integer) p.second; // Compiler error
The data type with the parameter in angle brackets (e.g. Pair<String>) is called parameterized
type.
Generics are similar to C++ templates on their external presentation and use. But unlike the C++
templates, there are no several different types of Pair, but one. In fact, the class
fields contain references to the Object type. Parameter type information is used by the
compiler to check and automatically cast types in the source code.
In addition to generic classes, you can create generic interfaces. The parameter can be used in the description of functions declared in the interface. Interfaces can be implemented by both generic and non-generic classes. By the implementation in non-generic class, generic parameter can be replaced by some reference type. For example:
interface Function<T> {
T func(T x);
}
class DoubleFunc implements Function<Double> {
@Override
public Double func(Double x) {
return x * 1.5;
}
}
class IntFunc implements Function<Integer> {
@Override
public Integer func(Integer x) {
return x % 2;
}
}
Generic classes and interfaces in Java are neither new types nor templates. This is just mechanism that tells the compiler to further type check and add type conversions.
Java also allows you to create generic functions inside both generic and non-generic classes:
public class ArrayPrinter {
public static<T> void printArray(T[] a) {
for (T x : a) {
System.out.print(x + "\t");
}
System.out.println();
}
public static void main(String[] args) {
String[] as = {"First", "Second", "Third"};
printArray(as);
` Integer[] ai = {1, 2, 4, 8};
printArray(ai);
}
}
As you can see from the example, the call of a generic function does not require an explicit type definition. Sometimes such a definition is necessary, for example, when the function does not have generic type parameters. If this function is static, its class must be explicitly indicated. For example:
public class TypeConverter {
public static <T>T convert(Object object) {
return (T) object;
}
public static void main(String[] args) {
Object o = "Some Text";
String s = TypeConverter.<String>convert(o);
System.out.println(s);
}
}
Recommended names of formal parameters are names of a single capital letter. Generics can have two or more parameters. In the following example, the pair may contain references to objects of different types:
public class PairOfDifferentObjects<T, E> {
T first;
E second;
public PairOfDifferentObjects(T first, E second) {
this.first = first;
this.second = second;
}
public static void main(String[] args) {
PairOfDifferentObjects<Integer, String> p =
new PairOfDifferentObjects<Integer, String>(1000, "thousand");
PairOfDifferentObjects<Integer, Integer> p1 =
new PairOfDifferentObjects<Integer, Integer>(1, 2);
//...
}
}
You can apply to objects of the generic parameter type only actions that are allowed for objects in the
Object class. Sometimes it is desirable to expand the functionality to specify the type.
For example, if you want to call methods declared in a particular class or interface, you can apply the
following parameter syntax: <T extends SomeBaseType> or <T
extends FirstType & SecondType>, etc. The word extends is
used for both classes and interfaces.
For example, you can create a generic function for calculating the arithmetic mean of some numerical
values stored in an array. The standard Double, Float, Integer,
Long, and other numeric wrapper classes have a common abstract base class
java.lang.Number
that declares, in particular, the doubleValue() method, which allows you to get the number
stored in the object in the form of a double value. This fact can be used
to calculate the arithmetic mean. The created function can work with arrays of numbers of different
types:
package ua.inf.iwanoff.java.fourth;
public class AverageTest {
public static<E extends Number> double average(E[] arr) {
double result = 0;
for (E elem : arr) {
result += elem.doubleValue();
}
return result / arr.length;
}
public static void main(String[] args) {
Double[] doubles = { 1.0, 1.1, 1.5 };
System.out.println(average(doubles)); // 1.2
Integer[] ints = { 10, 20, 3, 4 };
System.out.println(average(ints)); // 9.25
}
}
The syntax of generics involves the use of so-called wildcards (the '?' character). Wildcards are used, for example, to describe references to an unknown type. Using wildcards makes generics classes and functions more compatible. The wildcards provide the way to create functions that are non-generic by themselves, but use generics as arguments.
Here is an example of creating a generic class that represents an array of a certain type. We can also add a static function to output to the console elements of an array of arbitrary type, which demonstrates the use of wildcards:
public class MyArray<T> {
private T[] arr;
public MyArray(T... arr) {
this.arr = arr;
}
public int size() {
return arr.length;
}
public T get(int i) {
return arr[i];
}
public void set(int i, T t) {
arr[i] = t;
}
public static void printGenericArray(MyArray<?> a) {
for (int i = 0; i < a.size(); i++) {
System.out.print(a.get(i) + "\t");
}
System.out.println();
}
}
Our array can be tested in some another class:
package ua.inf.iwanoff.java.fourth;
public class MyArrayTest {
public static void main(String[] args) {
MyArray<String> arr1 = new MyArray<>("First", "Second", "Third");
MyArray.printGenericArray(arr1);
MyArray<?> arr2 = new MyArray<>(1, 2, 3); // MyArray<?> instead of MyArray<Integer>
MyArray.printGenericArray(arr2);
}
}
You cannot create arrays of generic type objects:
T arr = new T[10]; // Error!
In our example, this problem can be solved using references to the Object class. In
addition, for ease of use, the constructor can be implemented as a function with a variable number of
parameters. It will also be useful to add an item to the end of the array. An alternative implementation
of the class can be as follows:
package ua.inf.iwanoff.java.fourth;
import java.util.Arrays;
public class MyArray<T> {
private Object[] arr = {};
public MyArray(T... arr) {
this.arr = arr;
}
public MyArray(int size) {
arr = new Object[size];
}
public int size() {
return arr.length;
}
public T get(int i) {
return (T)arr[i];
}
public void set(int i, T t) {
arr[i] = t;
}
public void add(T t) {
Object[] temp = new Object[arr.length + 1];
System.arraycopy(arr, 0, temp, 0, arr.length);
arr = temp;
arr[arr.length - 1] = t;
}
public void remove(int i) {
Object[] temp = new Object[arr.length - 1];
System.arraycopy(arr, 0, temp, 0, i);
System.arraycopy(arr, i + 1, temp, i, arr.length - i - 1);
arr = temp;
}
@Override
public String toString() {
return Arrays.toString(arr);
}
}
Another class will be created for testing:
package ua.inf.iwanoff.java.fourth;
public class TestClass {
public static void main(String[] args) {
MyArray<String> a = new MyArray<>("1", "2");
String s = a.get(a.size() - 1);
System.out.println(s); // 2
a.set(1, "New");
System.out.println(a); // 1 New
MyArray<Double> b = new MyArray<>(3);
b.set(0, 1.0);
b.set(1, 2.0);
b.set(2, 4.0);
b.remove(2);
b.add(8.0);
System.out.println(b); // [1.0, 2.0, 8.0]
}
}
The functionality of a class can be extended by adding a new element inside an array, deleting all elements, etc.
You can restrict the use of the function parameter type to certain derived classes, such as MyArray<?
super String>. Then, MyArray<Integer> is not possible.
2.2.4 Use of Optional Class
An example of a standard generic type is class Optional.
Optional values are containers for values that can sometimes be empty. Traditionally, for uncertain values,
the value null was used. Using the null constant
can be inconvenient because it can lead to the throwing of the NullPointerException exception,
which complicates debugging and maintenance of the program.
A generic Optional class allows you to save the reference value to some object, and also to
check if the value is set. For example, some method returns a numeric value, but for some arguments the argument
cannot return something definite. This method can return an Optional type object and this value
can then be used in the calling function. Suppose some function calculates and returns the reciprocal value
and returns an "empty" object if the argument is equal to 0. The main() function performs
the calculation for the reciprocal numbers for array items:
package ua.inf.iwanoff.oop.fifth;
import java.util.Optional;
public class OptionalDemo {
static Optional<Double> reciprocal(double x) {
Optional<Double> result = Optional.empty();
if (x != 0) {
result = Optional.of(1 / x);
}
return result;
}
public static void main(String[] args) {
double[] arr = { -2, 0, 10 };
Optional<Double> y;
for (double x : arr) {
System.out.printf("x = %6.3f ", x);
y = reciprocal(x);
if (y.isPresent()) {
System.out.printf("y = %6.3f%n", y.get());
}
else {
System.out.printf("The value cannot be calculated%n");
}
}
}
}
If you do not check for the presence of a value (isPresent()), a java.util.NoSuchElementException
will
be thrown when you try to call the get() function for the "empty" value. It can be
caught instead of calling the isPresent() function.
In some cases, the null value should not be considered as possible. In this
case, use ofNullable() to store the value. For example:
Integer k = null; Optional<Integer> opt = Optional.ofNullable(k); System.out.println(opt.isPresent()); // false
Assume that if the reciprocal() function described before does not return a value in the case
of division by zero, the y variable should be assigned to 0. Traditionally, in this case, the
if ... else statement
or conditional operation is used:
y = reciprocal(x); double z = y.isPresent() ? y.get() : 0;
The orElse() method allows you to make the code more compact:
double z = reciprocal(x).orElse(0.0);
In addition to the generic Optional class, you can also use classes optimized for primitive
types: OptionalInt, OptionalLong, OptionalBoolean, etc. The previous
example (calculation of the reciprocal value) could be realized in this way (using OptionalDouble):
package ua.inf.iwanoff.oop.fifth;
import java.util.OptionalDouble;
public class OptionalDoubleDemo {
static OptionalDouble reciprocal(double x) {
OptionalDouble result = OptionalDouble.empty();
if (x != 0) {
result = OptionalDouble.of(1 / x);
}
return result;
}
public static void main(String[] args) {
double[] arr = {-2, 0, 10};
OptionalDouble y;
for (double x : arr) {
System.out.printf("x = %6.3f ", x);
y = reciprocal(x);
if (y.isPresent()) {
System.out.printf("y = %6.3f%n", y.getAsDouble());
}
else {
System.out.printf("The value cannot be calculated%n");
}
}
}
}
As can be seen from the example, the result can be obtained using the getAsDouble() method instead
of get().
2.3 Container Classes and Interfaces. Working with Lists
2.3.1 Overview
Java tools to work with collection provide a unified architecture for representing and managing data sets. This architecture allows you to work with collections regardless of the details of their internal representation. The tools for working with collections include more than a dozen interfaces, as well as standard implementations of these interfaces and a set of algorithms for working with them.
A collection is an object representing a group of objects. The use of collections helps to increase the efficiency of programs through the use of high-performance algorithms, and also helps to create a reusable code. The main components of working with collections are:
- interfaces
- standard implementation of interfaces
- algorithms
- tools for working with arrays
In addition, Java 8 supports Java 1.1 containers. These are Vector, Enumeration,
Stack, BitSet and some others. For example, the Vector class
provides functions similar to ArrayList. These containers did not provide a standardized
interface in the first version, they do not allow the user to omit excessive synchronization, which is
relevant only in a multithreading environment, and therefore not sufficiently effective. As a result,
they are considered obsolete and not recommended for use. Instead, you should use the corresponding
generic Java 5 containers.
Standard Java container classes allow you to store a collection of references to objects whose classes
derived from Object class. Container classes are implemented in the java.util
package. Starting with Java 5, all container classes are implemented as generic.
There are two base interfaces those declare functionality of container classes:
Collection (derived from Iterable) and Map. The
Collection interface is a base interface for List, Set,
Queue
and Deque (double-ended queue) interfaces.
The List interface represents an ordered collection (also known as a sequence) whose
elements can be repeated.
The Set interface is implemented by classes HashSet and
LinkedHashSet. The SortedSet interface, derived from Set, is
implemented by the TreeSet class. The Map interface is implemented by the
HashMap class. The SortedMap, derived from Map, is implemented by
the TreeMap class.
The HashSet, LinkedHashSet, and HashMap classes use so-called hash
codes to identify the items. A hash code is a unique sequence of bits of fixed length. For each
object, this sequence is considered unique. Hash codes provide quick access to data for some key. The
mechanism for obtaining hash codes ensures their almost complete uniqueness. All Java objects can
generate hash codes: the hashCode() method is defined for the Object class.
For most collections, there are both "normal" implementations and implementations that are safe
from the viewpoint of multithreading, for example, CopyOnWriteArrayList,
ArrayBlockingQueue,
etc.
2.3.2 Collection Interface
The Collection interface is the base for most Collection Framework interfaces and declares
the most common collection methods:
| Method | Description |
|---|---|
int size() |
Returns the number of items in this collection |
boolean isEmpty() |
Returns true if this collection contains no items |
boolean contains(Object o) |
Returns true if this collection contains the specified item |
Iterator<E> iterator() |
Returns an iterator (an object that consistently points to the items) |
Object[] toArray() |
Returns an array of Object containing all of the items in this collection |
<T> T[] toArray(T[] a) |
Returns an array of T containing all of the items in this collection |
boolean add(E e) |
Adds an item to the collection. Returns true if the object is
added
|
boolean remove(Object o) |
Removes a single instance of the specified item from this collection, if it is present |
boolean containsAll(Collection<?> c) |
Returns true if this collection contains all the items of the
specified collection
|
boolean addAll(Collection<? extends E> c)
|
Adds items to a collection. Returns true if objects are added |
boolean removeAll(Collection<?> c) |
Removes objects that are present in the specified collection |
boolean retainAll(Collection<?> c) |
Leaves objects that are present in another collection |
void clear() |
Removes all the items from collection |
Note: the table does not list methods with default implementation, added in Java 8.
The following example demonstrates how the interface methods work. In the example, the
ArrayList class is used as the simplest implementation of the Collection
interface:
package ua.inf.iwanoff.java.fourth;
import java.util.*;
public class CollectionDemo {
public static void main(String[] args) {
Collection<Integer> c = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
System.out.println(c.size()); // 5
System.out.println(c.isEmpty()); // false
System.out.println(c.contains(4)); // true
c.add(6);
System.out.println(c); // [1, 2, 3, 4, 5, 6]
c.remove(1);
System.out.println(c); // [2, 3, 4, 5, 6]
Collection<Integer> c1 = new ArrayList<>(Arrays.asList(3, 4));
System.out.println(c.containsAll(c1));// true
c.addAll(c1);
System.out.println(c); // [2, 3, 4, 5, 6, 3, 4]
Collection<Integer> c2 = new ArrayList<>(c); // copy
c.removeAll(c1);
System.out.println(c); // [2, 5, 6]
c2.retainAll(c1);
System.out.println(c2); // [3, 4, 3, 4]
c.clear();
System.out.println(c); // []
}
}
2.3.3 Working with Lists
The List interface describes an ordered collection (sequence). The most used standard
implementations of List interface are ArrayList and LinkedList.
The ArrayList class is a resizable-array implementation of the List interface.
The LinkedList class stores objects using the so-called linked list.
There is also a standard abstract implementation of the list, the AbstractList class. This
class derived from AbstractCollection provides a number of useful tools. Practically all
methods except get() and size() are implemented. However, for a specific
implementation of the list, most functions should be overridden. The AbstractList class is
the base class for the ArrayList. The AbstractSequentialList class derived
from AbstractList is the base class for the LinkedList class.
You can create an empty list of references to objects of some type (SomeType) using the
constructor that takes no arguments:
List<SomeType> al = new ArrayList<SomeType>();
You can also directly define the reference to ArrayList:
ArrayList<SomeType> al = new ArrayList<SomeType>();
The second approach is sometimes less desirable, because it reduced flexibility of a program. The first
option makes it easy to replace ArrayList implementation with any other implementation of
List interface, which is more consistent with the requirements of a particular task. In the
second case, we can call methods specific to ArrayList, so switching to another
implementation will be difficult.
An object of ArrayList class contains an array elementData of type
Object. The physical size of the array (capacity), if you do not call the constructor with
an explicit indication of this size, is set to 10. Each addition of an item involves calling the
internal method ensureCapacity(), which in case of filling the array creates a new array
with copying existing items. The size of the new array is calculated by the formula (old_size * 3) / 2 + 1.
When you delete items, the physical size of the array does not decrease. To save memory after repeatedly
deleting items, it is advisable to call the trimToSize() method.
Once you have created an empty list object, you can put object references in it using the
add() method. The add() method with one argument of reference type adds an
element to the end of the list. The add() method with two arguments inserts a new element
into a list before a given index, so it can be used to insert an element at any position
in a list except the last. The following code fragment shows the use of the add() method:
List<String> al = new ArrayList<String>();
al.add("abc");
al.add("def");
al.add("xyz");
al.add(2, "ghi"); // Inserts a new string before "xyz"
You can add all elements of other collection to your list using addAll() method.
You can create a new list using the existing one. The new list contains references to copies of the items. For example:
List<String> a11 = new ArrayList<String>(al);
You can create a list from an existing array using static asList() method of java.util.Arrays
class. An array can be created directly in the function parameter list. For example:
String[] arr = {"one", "two", "three"};
List<String> a2 = Arrays.asList(arr);
List<String> a3 = Arrays.asList("four", "five");
Lists provide overloaded toString() function, which allows, for example, to show all the
elements of the list on the screen without using loops. Items are displayed in square brackets:
System.out.println(a3); // [four, five]
Lists allow you to work with individual elements. The size() method returns the number of
elements in a list. As with arrays, list items can be accessed by index, but using the
get() and set() methods, not by [] operator. The
get() method returns the element at the specified position in this list. Like arrays, list
objects are indexed starting at zero. In the following example, all previously added strings are printed
using println() method:
List<String> al = new ArrayList<String>();
al.add("abc");
al.add("def");
al.add("xyz");
for (int i = 0; i < al.size(); i++) {
System.out.println(al.get(i));
}
The set() method allows you to change the object stored at a specified position, while the
remove() method removes the object at the specified position:
al.set(0, "new"); al.remove(2); System.out.println(al); // [new, def]
The subList(fromIndex, toIndex) function returns a list composed of elements beginning with
an index fromIndex and not including an item with a toIndex index. For
example:
System.out.println(al.subList(1, 3)); // [def, xyz]
The removeRange(m, n) method removes all the elements whose index is between
m, inclusive, and n, exclusive. You can also remove all the elements from
the list using the clear() method. The contains() method returns
true if this list contains the specified element. For example:
if (al.contains("abc")) {
System.out.println(al);
}
The toArray() method returns a reference to an array of references to copies of objects
stored in the list.
Object [] a = al.toArray(); System.out.println(a[1]); // def (al.toArray()) [2] = "text"; // the modification of a new array
You can use wrapper classes Integer and Double if you want to store numeric
values in container.
In those cases where the operations of adding and removing elements in arbitrary places are more often
than selecting an arbitrary element, it is advisable to use the LinkedList class, which
stores objects using the so-called linked list. The linked list that implemented in Java by the
LinkedList
container is a doubly linked list, where each element contains a reference to the previous and the next
elements.
For convenient work , the addFirst(), addLast(), removeFirst(),
and removeLast() methods are added.
LinkedList<String> list = new LinkedList<String>();
list.addLast("last"); // The same as list.add("last");
list.addFirst("first");
System.out.println(list); // [first, last]
list.removeFirst();
list.removeLast();
System.out.println(list); // []
These specific features are added in LinkedList, because they cannot be effectively
implemented in ArrayList.
Linked lists in Java support working with individual items, but these functions cannot be implemented effectively.
2.3.4 Iterators
An iterator is a special auxiliary object that is used for the sequential passage of the
elements of the collection (list). Like the containers themselves, iterators are based on the interface.
The Iterator interface defined in java.util package. An object that implements
the Iterator interface provides three methods for dealing with the collection:
boolean hasNext(); // returns true if the iteration has more elements Object next(); // returns the next element in the iteration void remove(); // removes the last element returned by the iterator
After the first next() invocation, iterator points to the first element. Java collections
return iterators from iterator() method.
List<String> s = new ArrayList<String>();
s.add("First");
s.add("Second");
for (Iterator<String> i = s.iterator(); i.hasNext(); ) {
System.out.println(i.next());
}
As can be seen from the example above, the iterator is also a generic type.
An alternate form of the for (for each) loop allows you to bypass the list without
explicitly creating the iterator:
List<Integer> a = new ArrayList<Integer>();
a.add(1);
a.add(2);
a.add(3);
a.add(4);
for (Integer i : a) {
System.out.print(i + " ");
}
As for arrays, the alternative form of the for loop does not allow you to change the
values of elements, or delete them.
The special kind of list iterator, ListIterator, provides additional iteration capabilities,
in particular, passing through the list in reverse order. In the following example, to check whether the
word is a palindrome, a list of characters and a ListIterator are used, which provides the
reverse order:
package ua.inf.iwanoff.java.fourth;
import java.util.*;
public class ListIteratorTest {
public static void main(String[] args) {
String palStr = "racecar";
List<Character> palindrome = new LinkedList<Character>();
for (char ch : palStr.toCharArray()) {
palindrome.add(ch);
}
System.out.println("Input string is: " + palStr);
ListIterator<Character> iterator = palindrome.listIterator();
ListIterator<Character> revIterator = palindrome.listIterator(palindrome.size());
boolean result = true;
while (revIterator.hasPrevious() && iterator.hasNext()) {
if (iterator.next() != revIterator.previous()) {
result = false;
break;
}
}
if (result) {
System.out.print("Input string is a palindrome");
}
else {
System.out.print("Input string is not a palindrome");
}
}
}
2.3.5 Additional Features for Standard Containers
Starting with Java 8, the standard interfaces of the java.util package are supplemented with
methods that focus on using lambda expressions and references to methods. To ensure compatibility with
previous versions, new interfaces provide the default implementation of the new methods. In particular,
the Iterable interface defines the forEach() method, which allows you to
perform some actions in the loop that do not change the elements of the collection. You can specify an
action using a lambda expression or a reference to a method. For example:
public class ForEachDemo {
static int sum = 0;
public static void main(String[] args) {
Iterable<Integer> numbers = new ArrayList(Arrays.asList(2, 3, 4));
numbers.forEach(n -> sum += n);
System.out.println(sum);
}
}
In the above example, the sum of collection elements is calculated. The variable that holds the sum is described as a static class field, since lambda expressions cannot change local variables.
The Collection interface defines the removeIf() method, which allows you to
remove items from the collection if items match a certain filter rule. In the following example, odd
items are removed from the collection of integers. The forEach() method is used for
columnwise output the collection items:
Collection<Integer> c = new ArrayList(Arrays.asList(2, 4, 11, 8, 12, 3)); c.removeIf(k -> k % 2 != 0); // The rest of the items are displayed columnwise: c.forEach(System.out::println);
The List interface provides methods replaceAll() and sort(). The
second one can be used instead of the analogous static method of the Collections class, but
the definition of the sorting feature is obligatory:
List<Integer> list = new ArrayList(Arrays.asList(2, 4, 11, 8, 12, 3)); list.replaceAll(k -> k * k); // replace the numbers with their second powers System.out.println(list); // [4, 16, 121, 64, 144, 9] list.sort(Integer::compare); System.out.println(list); // [4, 9, 16, 64, 121, 144] list.sort((i1, i2) -> Integer.compare(i2, i1)); System.out.println(list); // [144, 121, 64, 16, 9, 4]
2.4 Working with Queues and Stacks
A queue in the broad sense is a data structure that is filled in by element, and it allows getting objects from it according to a certain rule. In the narrow sense, this rule is "First In - First Out" (FIFO). In a queue organized on the principle of FIFO, adding an element is possible only at the end of the queue, and getting is only possible from the beginning of the queue.
In the container library, the queue is represented by the Queue interface. Methods declared this interface are listed in the table below:
| Type of operation | Throws an exception | Returns a special value |
|---|---|---|
| Adding | add(e) |
offer(e) |
| Obtaining an item with removing | remove() |
poll() |
| Obtaining an item without removing | element() |
peek() |
The offer() method returns false if the item could not be added, for
example, if the queue has a limited number of items. In this case, the add() method throws
an exception. Similarly, remove() and element() throw an exception if the
queue is empty, but poll() and peek() in this case return null.
The most convenient way to implement the queue is the use of the LinkedList class that
implements the Queue interface. For example:
package ua.inf.iwanoff.java.fourth;
import java.util.LinkedList;
import java.util.Queue;
public class SimpleQueueTest {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
queue.add("First");
queue.add("Second");
queue.add("Third");
queue.add("Fourth");
String s;
while ((s = queue.poll()) != null) {
System.out.print(s + " "); // First Second Third Fourth
}
}
}
The PriorityQueue class arranges the elements according to the comparator (the object that
implements the Comparator interface) specified in the constructor as a parameter. If an
object is created using a constructor without parameters, the elements will be ordered in a natural way
(ascending for numbers, in alphabetical order for strings). For example:
package ua.inf.iwanoff.java.fourth;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueTest {
public static void main(String[] args) {
Queue<String> queue = new PriorityQueue<>();
queue.add("First");
queue.add("Second");
queue.add("Third");
queue.add("Fourth");
String s;
while ((s = queue.poll()) != null) {
System.out.print(s + " "); // First Fourth Second Third
}
}
}
The Deque interface (double-ended-queue) provides the ability to add and remove items from
both ends. Methods declared in this interface are listed below:
| Type of operation | Working with the first element | Working with the last element |
|---|---|---|
| Adding | addFirst(e) |
addLast(e) |
| Obtaining an item with removing | removeFirst() |
removeLast() |
| Obtaining an item without removing | getFirst() |
getLast() |
Each pair represents the function that throws an exception, and the function that returns some special
value. There are also methods for removing the first (or last) occurrence of a given element (removeFirstOccurrence()
and removeLastOccurrence(), respectively).
You can use whether the special ArrayDeque class or LinkedList to implement the
interface.
A stack is a data structure organized on the principle "last in – first out" (LIFO). There are three stack operations: adding element (push), removing element (pop) and reading head element (peek).
In JRE 1.1, the stack is represented by the Stack class. For example:
package ua.inf.iwanoff.java.fourth;
import java.util.Stack;
public class StackTest {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
stack.push("First");
stack.push("Second");
stack.push("Third");
stack.push("Fourth");
String s;
while (!stack.isEmpty()) {
s = stack.pop();
System.out.print(s + " "); // Fourth Third Second First
}
}
}
This class is currently not recommended for use. Instead, you can use the Deque interface,
which declares the similar methods. For example:
package ua.inf.iwanoff.java.fourth;
import java.util.ArrayDeque;
import java.util.Deque;
public class AnotherStackTest {
public static void main(String[] args) {
Deque<String> stack = new ArrayDeque<>();
stack.push("First");
stack.push("Second");
stack.push("Third");
stack.push("Fourth");
String s;
while (!stack.isEmpty()) {
s = stack.pop();
System.out.print(s + " "); // Fourth Third Second First
}
}
}
Stacks are often used in various algorithms. In particular, it is often possible to implement a complex algorithm without recursion with the help of a stack.
2.5 Static Methods of the Collections Class. Algorithms
2.5.1 Creating Special Containers using the Collections Class
As the Arrays class for arrays, collections have an assistant Collections
class. This class provides a number of functions for working with collections, including lists. A large
group of functions is designed to create collections of different types. The following example
demonstrates the creation of collections using static Collections methods: respectively, a
blank list (emptyList()), singleton (singletonList()), and a read-only list ((unmodifiableList())
, or a read-only collection (unmodifiableCollection()):
import java.util.*;
public class CollectionsCreationDemo {
public static void main(String[] args) {
List<Integer> emptyList = Collections.emptyList();
System.out.println(emptyList); // []
List<Integer> singletonList = Collections.singletonList(10);
System.out.println(singletonList); // [10]
List<Integer> list = new ArrayList<>(Arrays.<Integer>asList(1, 2, 3));
List<Integer> unmodifiableList = Collections.unmodifiableList(list);
Collection<Integer> collection = Collections.unmodifiableCollection(list);
}
}
All of the above functions create read-only collections.
Similarly, methods that create the corresponding sets are emptySet(),
singleton(), and unmodifiableSet().
2.5.2 Algorithms
The algorithm of the collection library is a certain function that implements the work with
the collection (obtaining a certain result or converting the elements of the collection). In the Java
Collections API, this function is usually static and generic.
Like Arrays class, Collections class contains static functions for sorting and
filling collections (sort() and fill() accordingly), with the same rules of
usage. In addition, there are a large number of static functions to process lists without looping. This,
for example, max() (searches for the maximum element), min() (finds the
minimum element), indexOfSubList() (searches index of the first complete occurrence of some
list), frequency() (determines the count of occurrence of a particular element within the
list), reverse() (allocates elements in reverse order), rotate() (provides
cyclic shift of elements), shuffle() (shuffles elements), nCopies() (creates a
new list with a specific number of identical elements). The use of these functions can be illustrated by
the following example:
List<Integer> a = Arrays.asList(0, 1, 2, 3, 3, -4); System.out.println(Collections.max(a)); // 3 System.out.println(Collections.min(a)); // -4 System.out.println(Collections.frequency(a, 2)); // 1 time System.out.println(Collections.frequency(a, 3)); // 2 times Collections.reverse(a); // reverse order System.out.println(a); // [-4, 3, 3, 2, 1, 0] Collections.rotate(a, 3); // cyclic shift by 3 positions System.out.println(a); // [2, 1, 0, -4, 3, 3] List<Integer> sublist = Collections.nCopies(2, 3); // the new list contains 2 threes System.out.println(Collections.indexOfSubList(a, sublist)); // 4 Collections.shuffle(a); // shuffle elements System.out.println(a); // elements in random order Collections.sort(a); System.out.println(a); // [-4, 0, 1, 2, 3, 3] List<Integer> b = new ArrayList<Integer>(a); Collections.fill(b, 8); System.out.println(b); // [8, 8, 8, 8, 8, 8] Collections.copy(b, a); System.out.println(b); // [-4, 0, 1, 2, 3, 3] System.out.println(Collections.binarySearch(b, 2)); // 3 Collections.swap(b, 0, 5); System.out.println(b); // [3, 0, 1, 2, 3, -4] Collections.replaceAll(b, 3, 10); System.out.println(b); // [10, 0, 1, 2, 10, -4]
The Collections class also provides methods specifically for working with lists, for
example, getting the starting position of the first and last occurrence of the specified sublist in the
list (indexOfSubList(), lastIndexOfSubList()), etc.
2.6 Working with Sets and Maps
2.6.1 Sets
A set is a collection that does not contain the same elements. The three main implementations of
the Set interface are HashSet, LinkedHashSet and
TreeSet. Like lists, sets are generic types. HashSet and
LinkedHashSet classes use hash codes to identify an item. The TreeSet class
uses a binary tree to store elements and guarantees their particular order.
The add() method adds an element to a set and returns true if the
element was previously absent. Otherwise, the item is not added, and the add() method
returns false. All elements of the set are cleared using the clear()
method.
Set<String> s = new HashSet<String>();
System.out.println(s.add("First")); // true
System.out.println(s.add("Second")); // true
System.out.println(s.add("First")); // false
System.out.println(s); // [First, Second]
s.clear();
System.out.println(s); // []
The remove() method removes the specified element from the set, if present. The method
contains() returns true if this set contains the specified
element.
In the following example, ten random values in the range from -9 to 9 are added to the set of integers:
package ua.inf.iwanoff.java.fourth;
import java.util.*;
public class SetOfIntegers {
public static void main(String[] args) {
Set<Integer> set = new TreeSet<Integer>();
Random random = new Random();
for (int i = 0; i < 10; i++) {
Integer k = random.nextInt() % 10;
set.add(k);
}
System.out.println(set);
}
}
The resulting set usually contains less than 10 numbers, since individual values can be repeated. Since
we use TreeSet, the numbers are stored and displayed in ascending order. In order to add
ten different numbers, the program should be modified, with the use of the while
instead of for:
while (set.size() < 10) {
. . .
}
It is possible to create an array that contains copies of the set items. In this way, items can be accessed by index. For example, we can output set elements in reverse order:
Set<Integer> set = new HashSet<>(Arrays.asList(1, 2, 4));
Object[] arr = set.toArray();
for (int i = set.size() - 1; i >= 0; i--) {
System.out.println(arr[i]);
}
Since the set can contain only different elements, it can be used to count different words, letters,
numbers, etc.: a set is created and the size() method is invoked. Applying
TreeSet, you can display words and letters alphabetically. In the following example,
sentences are entered and all the different letters of the sentence (not including separators) are
displayed in alphabetical order:
package ua.inf.iwanoff.java.fourth;
import java.util.*;
public class Sentence {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// The nextLine() function reads the string to the end of line:
String sentence = scanner.nextLine();
// Create a set of separators:
Set<Character> delimiters = new HashSet<Character>(
Arrays.asList(' ', '.', ',', ':', ';', '?', '!', '-', '(', ')', '\"'));
// Create a set of letters:
Set<Character> letters = new TreeSet<Character>();
// Add all letters except separators:
for (int i = 0; i < sentence.length(); i++) {
if (!delimiters.contains(sentence.charAt(i))) {
letters.add(sentence.charAt(i));
}
}
System.out.println(letters);
}
}
You can specify the sort order of TreeSet elements by implementing the
Comparable interface, or by passing the reference to the class object that implements the
Comparator interface into the TreeSet constructor. For example, you can sort
the tree in reverse order:
package ua.inf.iwanoff.java.fourth;
import java.util.*;
public class CompTest {
public static void main(String args[]) {
TreeSet<String> ts = new TreeSet<String>(new Comparator<String>()
{
@Override
public int compare(String s1, String s2) {
return s2.compareTo(s1);
}
});
ts.add("C");
ts.add("E");
ts.add("D");
ts.add("B");
ts.add("A");
ts.add("F");
for (String element : ts)
System.out.print(element + " ");
}
}
}
2.6.2 Associative Containers
Associative arrays hold pairs of references to objects. Associative arrays are also generic types.
Associative arrays in Java are represented by generic Map interface. The most-used
implementation of Map interface is HashMap. SortedMap, an
interface derived from Map, assumes storing of pairs, which are sorted by key. The NavigableMap
interface, appearing on the java SE 6, extends the SortedMap and adds new key search
capabilities. This interface is implemented by the TreeMap class.
Each value (object) that is stored in the associative array is associated with the specific value of
another object (key). You can add a new pair using put(key, value) method. If the map
previously contained a mapping for this key, the old value is replaced by the specified value. The
method returns previous value associated with specified key, or null if there was no
mapping for key. The get(Object key) method returns the object by the given key. To check
whether key (value) presents in a map, the methods containsKey() and
containsValue() are used.
At the logical level, an associative array can be represented through three auxiliary collections:
keySet: set of keys;values: list of values;entrySet: set of key-value pairs.
Due to the functions keySet(), values(), and entrySet(), you can
perform certain actions, e.g. successive passage of the elements.
The following program counts entering of different words in a statement. Words and their counts are
stored in a map. Usage of the TreeMap class guarantees alphabetic order of words (keys).
package ua.inf.iwanoff.java.fourth;
import java.util.*;
public class WordsCounter {
public static void main(String[] args) {
Map<String, Integer> m = new TreeMap<String, Integer>();
String s = "the first men on the moon";
StringTokenizer st = new StringTokenizer(s);
while (st.hasMoreTokens()) {
String word = st.nextToken();
Integer count = m.get(word);
m.put(word, (count == null) ? 1 : count + 1);
}
for (String word : m.keySet()) {
System.out.println(word + " " + m.get(word));
}
}
}
Using keySet() involves a separate search for each value by the key. It is more recommended
to bypass the associative array through a set of pairs:
for (Map.Entry<?, ?> entry : m.entrySet())
System.out.println(entry.getKey() + " " + entry.getValue());
The entrySet() method allows you to get representation of the associative array in the form
of the Set collection.
The TreeMap sort order can also be changed by sending to the TreeMap
constructor as a parameter an object that implements the Comparator interface, or by
setting the key as the object that implements the Comparable interface:
package ua.inf.iwanoff.java.fourth;
import java.util.*;
public class TreeMapKey implements Comparable<TreeMapKey> {
private String name;
public String getName() {
return name;
}
public TreeMapKey(String name) {
super();
this.name = name;
}
@Override
public int compareTo(TreeMapKey o) {
return name.substring(o.getName().indexOf(" ")).trim()
.compareToIgnoreCase(o.getName().substring(o.getName().indexOf(" ")).trim());
}
public static void main(String args[]) {
TreeMap<TreeMapKey, Integer> tm = new TreeMap<TreeMapKey, Integer>();
tm.put(new TreeMapKey("Peter Johnson"), new Integer(1982));
tm.put(new TreeMapKey("John Peterson"), new Integer(1979));
tm.put(new TreeMapKey("Jacob Nickson"), new Integer(1988));
tm.put(new TreeMapKey("Nick Jacobson"), new Integer(1980));
for (Map.Entry<TreeMapKey, Integer> me : tm.entrySet()) {
System.out.print(me.getKey().getName() + ": ");
System.out.println(me.getValue());
}
System.out.println();
}
}
The Hashtable class is one of the implementations of the Map interface. Hashtable
in addition to size has a capacity (buffer size, selected for elements of the array). In addition, it is
characterized by the load factor - the portion of the buffer, after which the capacity automatically
increases. The Hashtable() constructor without parameters creates an empty object with a
capacity of 101 elements and a load index of 0.75.
The Properties class derived from Hashtable stores pairs of strings. If in a
particular task keys and values of the associative array elements are of the String type,
it is more convenient to use the Properties class. In the Properties class,
methods are getProperty(String key) and setProperty(String key, String value).
Starting with Java 8, new methods have been added to the Map interface. The added methods
listed in the table:
| Method | Description |
|---|---|
V getOrDefault(Object key, V& defaultValue) |
Returns a value, or a default value, if the key is missing |
V putIfAbsent(K key, V value) |
Adds a pair if the key is missing and returns the value |
boolean remove(Object key, Object value) |
Removes a pair if it is present |
boolean replace(K key, V oldValue, V newValue) |
Replaces value with the new one if pair is present |
V replace(K key, V value) |
Replaces the value if the key is present, returns the old value |
V compute(K key, BiFunction<?& super K, super V,
? extends V> remappingFunction) |
Invokes the function to construct a new value. A new pair is added, a pair that existed before is deleted, and a new value is returned |
V computeIfPresent(K key, BiFunction<? super K,
? super V, ? extends V> remappingFunction) |
If a specified key is present, a new function is called to create a new value, and the new value replaces the previous one. |
V computeIfAbsent(K key, Function<? super K,
? extends V> mappingFunction) |
Returns the value by the key. If the key is missing, a new pair is added, the value is calculated by function |
V merge(K key, V value, BiFunction<? super V, ? super V,
? extends V> remappingFunction) |
If the key is absent, then a new pair is entered and the value v is returned.
Otherwise, the given function returns a new value based on the previous value and the key is
updated to access this value. and then it returns
|
void forEach(BiConsumer<? super K,
? super V> action) |
Performs a given action on each element |
The following example demonstrates the use of some of these methods:
import java.util.HashMap;
import java.util.Map;
public class MapDemo {
static void print(Integer i, String s) {
System.out.printf("%3d %10s %n", i, s);
}
public static void main(String[] args) {
Map<Integer, String> map = new HashMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(7, "seven");
map.forEach(MapDemo::print); // columnwise output
System.out.println(map.putIfAbsent(7, "eight")); // seven
System.out.println(map.putIfAbsent(8, "eight")); // null
System.out.println(map.getOrDefault(2, "zero")); // two
System.out.println(map.getOrDefault(3, "zero")); // zero
map.replaceAll((i, s) -> i > 1 ? s.toUpperCase() : s);
System.out.println(map); // {1=one, 2=TWO, 7=SEVEN, 8=EIGHT}
map.compute(7, (i, s) -> s.toLowerCase());
System.out.println(map); // {1=one, 2=TWO, 7=seven, 8=EIGHT}
map.computeIfAbsent(2, (i) -> i + "");
System.out.println(map); // nothing changed
map.computeIfAbsent(4, (i) -> i + "");
System.out.println(map); // {1=one, 2=TWO, 4=4, 7=seven, 8=EIGHT}
map.computeIfPresent(5, (i, s) -> s.toLowerCase());
System.out.println(map); // nothing changed
map.computeIfPresent(2, (i, s) -> s.toLowerCase());
System.out.println(map); // {1=one, 2=two, 4=4, 7=seven, 8=EIGHT}
// Adding a new pair:
map.merge(9, "nine", (value, newValue) -> value.concat(newValue));
System.out.println(map.get(9)); // nine
// The text is concatenated with the previous one:
map.merge(9, " as well", (value, newValue) -> value.concat(newValue));
System.out.println(map.get(9)); // nine as well
}
}
2.7 Internal Representation of Sets and Associative Containers
2.7.1 Implementation of Sets and Associative Containers using Hashing
To store data in HashSet and HashMap, the so-called hashing is used. Hashing
is the process of obtaining from an object a unique code using some formal algorithm. In a broad sense,
the result is a sequence of bits of fixed length, in the particular case, this is a simple integer. This
conversion is performed by a so-called hash function. The hash function should meet the
following requirement: the hash function should return the same hash code each time it is applied to
identical or equal objects.
.All Java objects inherit the standard implementation of a hashCode() function defined in
the Object class. This function returns a hash code obtained by converting an object's
internal address to a number, which ensures the creation of a unique code for each individual object.
Specific standard classes implement their hash functions. For example, for a string, the value of the hash function is calculated by the formula:
s[0]*31n-1 + s[1]*31n-2 + ... + s[n-1]
Here s[0], s[1], etc. are codes of the corresponding characters.
Containers constructed using hashing do not guarantee a certain order of storage items, but provide relatively high efficiency of search, addition and removing operations.
The mechanisms of data storage in the HashSet and HashMap classes is similar.
Let's consider the representation of data on an example of the HashMap container. The
nested Entry class represents a key-value pair:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
// ... Next, constructor and a number of auxiliary methods are implemented
}
Objects of this class are stored in an array. First, the array is designed to store 16 items, but then
its size can vary. Items of this array are called baskets, because they store references to the
lists of elements (in the next field). When adding a new key-value pair, the basket number
(the cell number of the array) into which the new entry puts will be calculated according to the key's
hash code. In this case, the value of the hash code is projected onto an array taking into account its
real size. If the basket is empty, then the reference to the added element is stored in it, if there is
already an element there, then a traversal over a linked list is done and a new element is added after
the last element. If an element with the same key was found in the list, the value will be replaced.
The efficiency of adding, retrieving and deleting operations depends on the implementation of the hash function. If it returns a constant value, the container is converted into a linked list with low efficiency.
2.7.2 Implementation of Containers Based on Binary Trees
A binary tree represents a tree-like data structure (graph without cycles), in which each vertex (node) has no more than two descendants (children). They are called respectively the left child and right child. In turn, they can act as vertex subtree. We can talk about the left and right subtree.
A binary tree can be used for storing objects that are ordered by a specific criterion (ordering by key). In this case we speak about the so-called binary search tree, which satisfies such rules:
- the left and right subtrees are also binary search trees;
- in all nodes of the left subtree of some node the value of the keys is less than the value of the key in this node;
- in all nodes of the right subtree of the same node the value of the keys is not less than the value of the key in this node.
Usually binary search trees implement such basic operations:
- adding item
- getting (searching) item
- deleting item (node)
- bypass the tree
The binary tree is called perfectly balanced if for each of its vertices, the number of vertices in the left and right subtree differs by no more than 1. In an unbalanced tree, this rule is not followed. The simplest implementation of a tree gives an unbalanced tree. Depending on the order of adding elements, the tree can be balanced or completely unbalanced. Suppose a binary tree maintains integer values. If the numbers from 1 to 7 are added in a certain order (for example, 4, 2, 3, 1, 6, 7, 5), a perfectly balanced tree may come out:
If you add numbers in ascending order, a highly unbalanced tree will be created:
We can say about a different degree of balance. Unbalance reduces performance when looking for an item. However, the creation of perfectly balanced trees causes computational difficulties when adding and removing. In practice, partially balanced trees are often used.
The so-called red-black tree is a binary search tree that automatically maintains a certain balance. This allows you to effectively implement the basic operations (adding, searching and deleting). Each node of the tree is placed in accordance with the color - red or black. Fictitious leaf nodes that contain no data attached to each node. There are additional requirements:
- the root of the tree should be black
- all leaf nodes are black
- both children of each red node are black
- each simple path from this node to any leaf node that is its descendant contains the same number of black nodes
For example, a red-black tree might be as follows (from the site en.wikipedia.org):
When adding a new node (always red), it is sometimes needed to repaint the tree and rotate it. Adding
nodes, taking into account the constraints and the "rotation" with the transfer of nodes,
makes the tree self-balancing. Red-black trees are used to build TreeSet and
TreeMap containers.
2.8 Creating Custom Containers
In spite of the large number of standard container classes, there is sometimes a need to create custom containers. These can be, for example, complex trees, more flexible lists, specialized collections of items, etc.
In some cases, it is only necessary to bypass elements of some sequence using the alternative form of the
for loop. It's enough to implement the Iterable<>
interface. It requires the implementation of the function that returns an iterator. Often, the
implementation of an iterator needs the creation an internal non-static class. The following example
creates a Sentence with an iterator that moves around the individual words. The program
displays the words of the entered sentence in separate lines:
package ua.inf.iwanoff.java.fourth;
import java.util.Iterator;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Sentence implements Iterable<String> {
private String text;
public Sentence(String text) {
this.text = text;
}
private class WordsIterator implements Iterator<String> {
StringTokenizer st = new StringTokenizer(text);
@Override
public boolean hasNext() {
return st.hasMoreTokens();
}
@Override
public String next() {
return st.nextToken();
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
public Iterator<String> iterator() {
return new WordsIterator();
}
public static void main(String[] args) {
String text = new Scanner(System.in).nextLine();
Sentence sentence = new Sentence(text);
for (String word : sentence) {
System.out.println(word);
}
}
}
In most cases the creation of iterators required definition of the so-called cursor, the variable referring to the current element of the sequence. In this case, the implementation of the next() method involves moving the cursor and returning the reference to the current element. For example:
public class SomeArray<E> implements Iterable<E> {
private E[] arr;
...
private class InnerIterator implements Iterator<E> {
int cursor = -1;
@Override
public boolean hasNext() {
return cursor < arr.length – 1;
}
@SuppressWarnings("unchecked")
@Override
public E next() {
return arr[++cursor];
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
@Override
public Iterator<E> iterator() {
return new InnerIterator();
}
...
}
To create a full-fledged custom container, it's the best way to use existing abstract classes. These are
AbstractCollection<E>, AbstractList<E>,
AbstractMap<K,V>,
AbstractQueue<E>, AbstractSet<E>, as well as some abstract
auxiliary classes. For example, in order to create your own read only list, it's formally enough to
override two abstract methods, get() and size(). When working with read-only
lists, methods such as add(), set(), remove(), and others that
are intended to change the list generate an UnsupportedOperationException exception. The
following example creates the simplest read only list:
package ua.inf.iwanoff.java.fourth;
import java.util.AbstractList;
public class MyList extends AbstractList<String> {
String[] arr = { "one", "two", "three" };
@Override
public String get(int index) {
return arr[index];
}
@Override
public int size() {
return arr.length;
}
public static void main(String[] args) {
MyList list = new MyList();
for (String elem : list) {
System.out.println(elem); {
}
System.out.println(list.subList(0, 2)); // [one, two]
System.out.println(list.indexOf("two")); // 1
list.add("four"); // Exception "UnsupportedOperationException"
}
}
In order to implement the container for reading and writing, it is necessary to override some extra methods. In the example 3.9, an appropriate container is implemented.
3 Sample Programs
3.1 Use of Enumeration
Suppose you want to create an enumeration that describes days of the week. An example of
such enumeration was shown previously. We can add a function that returns the next day. Also, we need to check
whether this day belongs to the weekend or not. We can also get the day number (0 - Sunday 1 - Monday, etc.).
In the main()function we start from Monday and traverse over weekdays, displaying information
about the day and signal if this day belongs to weekend. The program will look like this:
package ua.in.iwanoff.oop.fourth;
enum DayOfWeek {
SUNDAY,
MONDAY,
TUESDAY,
WEDNESDAY,
THURSDAY,
FRIDAY,
SATURDAY;
@Override
public String toString() {
return name() + " " + ordinal();
}
DayOfWeek next() {
DayOfWeek day = values()[(ordinal() + 1) % values().length];
return day;
}
boolean isWeekend() {
switch (this) {
case SATURDAY:
case SUNDAY:
return true;
default:
return false;
}
}
}
public class EnumTest {
public static void main(String[] args) {
DayOfWeek d = DayOfWeek.MONDAY;
for (int i = 0; i < 7; i++) {
d = d.next();
System.out.println(d + " " + d.isWeekend());
}
}
}
As in other cases, data output is controlled by the overridden toString()
method.
3.2 Generic Function that Searches for a Given Item
Suppose we need to implement a static generic function that return index the first occurrence of a specific value. The function should return index of that element, or -1 if there is none. A class with the required function would look as follows:
package ua.inf.iwanoff.java.fourth;
public class ElementFinder {
public static <E>int indexOf(E[] arr, E elem) {
for (int i = 0; i < arr.length; i++) {
if (arr[i].equals(elem)) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
Integer[] a = {1, 2, 11, 4, 5};
System.out.println(indexOf(a, 11)); // 2
System.out.println(indexOf(a, 12)); // -1
String[] b = {"one", "two"};
System.out.println(indexOf(b, "one")); // 0
}
}
To compare objects, we need to use equals() method instead of ==.
3.3 Sum of List Elements of Double Type
The following program reads real numbers from keyboard adding them to list, and then finds their sum.
package ua.inf.iwanoff.java.fourth;
import java.util.*;
public class SumOfElements {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List<Double> a = new ArrayList<>();
double d = 1; // the initial value should not be 0
while (d != 0) {
d = scanner.nextDouble();
a.add(d);
}
double sum = 0;
for (double x : a) { // implicit iterator
sum += x;
}
System.out.println("Sum is " + sum);
}
}
Reading numbers from the keyboard is carried out until the user enters a value of 0.
3.4 Index of the Maximum Element
The following program finds index of the maximum element in a list of integer numbers. To fill out the
list we can use an array with the initial values of the elements. An array is implicitly created while
executing the asList() function.
package ua.inf.iwanoff.java.fourth;
import java.util.*;
public class MaxElement {
public static void main(String[] args) {
List<Integer> a = Arrays.asList(2, 3, -7, 8, 11, 0);
int indexOfMax = 0;
for (int i = 1; i < a.size(); i++) {
if (a.get(i) > a.get(indexOfMax)) {
indexOfMax = i;
}
}
System.out.println(indexOfMax + " " + a.get(indexOfMax));
}
}
Iterator cannot be used because the index is needed.
3.5 Country Data in the Associative Array
Country data (name and territory) can be stored in associative array. The output is carried out in alphabetical order of the countries:
package ua.inf.iwanoff.java.fourth;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
public class Countries {
public static void main(String[] args) {
SortedMap<String, Double> countries = new TreeMap<>();
countries.put("Ukraine", 603700.0);
countries.put("Germany", 357021.0);
countries.put("France", 547030.0);
for (Map.Entry<?, ?> entry : countries.entrySet())
System.out.println(entry.getKey() + " " + entry.getValue());
}
}
3.6 Letters of Sentence in Alphabetical Order
In the example below, sentence is entered and all the different letters (except separators) are displayed in alphabetical order:
package ua.inf.iwanoff.java.fourth;
import java.util.*;
public class Sentence {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// The nextLine() function reads the line to the end:
String sentence = scanner.nextLine();
// Create a set of separators:
Set<Character> delimiters = new HashSet<Character>(
Arrays.asList(' ', '.', ',', ':', ';', '?', '!', '-', '(', ')', '\"'));
// Create a set of letters:
Set<Character> letters = new TreeSet<Character>();
// Add all the letters except separators:
for (int i = 0; i < sentence.length(); i++) {
if (!delimiters.contains(sentence.charAt(i))) {
letters.add(sentence.charAt(i));
}
}
System.out.println(letters);
}
}
3.7 The Product of the Entered Numbers
In the example below, integers are entered, displayed as a decrease, and their product is calculated. The entering ends with zero:
package ua.inf.iwanoff.java.fourth;
import java.util.*;
public class Product {
@SuppressWarnings("resource")
public static void main(String[] args) {
Queue<Integer> queue = new PriorityQueue<>(100, new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
return -Double.compare(i1, i2);
}
});
Scanner scanner = new Scanner(System.in);
Integer k;
do {
k = scanner.nextInt();
if (k != 0) {
queue.add(k);
}
}
while (k != 0);
int p = 1;
while ((k = queue.poll()) != null) {
p *= k;
System.out.print(k + " ");
}
System.out.println();
System.out.println(p);
}
}
3.8 Creation of a Singly Linked List
The following example creates and fills a singly linked list:
package ua.inf.iwanoff.java.fourth;
public class SinglyLinkedList<E> {
private class Node {
E data;
Node next;
Node(E data, Node next) {
this.data = data;
this.next = next;
}
}
private Node first = null;
private Node last = null;
private int count = 0;
public void add(E elem) {
Node newNode = new Node(elem, null);
if (last == null) {
first = newNode;
}
else {
last.next = newNode;
}
last = newNode;
count++;
}
public void removeFirstOccurrence(E value) {
// Separately check the first element
if (first != null && first.data.equals(value)) {
first = first.next;
count--;
}
else {
Node link = first;
while (link.next != null) {
if (link.next.data.equals(value)) {
link.next = link.next.next;
count--;
}
if (link.next == null) {
last = link;
break; // the last item was removed
}
link = link.next;
}
}
}
public final int size() {
return count;
}
@Override
public String toString() {
String s = "size = " + size() + "\n[";
Node link = first;
while (link != null) {
s += link.data;
link = link.next;
if (link != null) {
s += ", ";
}
}
s += "]\n";
return s;
}
public static void main(String[] args) {
SinglyLinkedList<Integer> list = new SinglyLinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list);
// Remove the intermediate element:
list.removeFirstOccurrence(3);
System.out.println(list);
// Remove the first element:
list.removeFirstOccurrence(1);
System.out.println(list);
// Remove the last element:
list.removeFirstOccurrence(4);
System.out.println(list);
}
}
3.9 Creating a Binary Tree
The following example creates and fills a plain (unbalanced) binary tree containing a pair of integer / string:
package ua.inf.iwanoff.java.fourth;
public class BinaryTree {
// Class for node representation
public static class Node {
int key;
String value;
Node leftChild;
Node rightChild;
Node(int key, String name) {
this.key = key;
this.value = name;
}
@Override
public String toString() {
return "Key: " + key + " Value:" + value;
}
}
private Node root;
public void addNode(int key, String value) {
// Create a new node:
Node newNode = new Node(key, value);
if (root == null) { // first added node
root = newNode;
}
else {
// Begin bypass:
Node currentNode = root;
Node parent;
while (true) {
parent = currentNode;
// Check the keys:
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
if (currentNode == null) {
// Place the node in the appropriate place:
parent.leftChild = newNode;
return;
}
}
else {
currentNode = currentNode.rightChild;
if (currentNode == null) {
// Place the node in the appropriate place:
parent.rightChild = newNode;
return;
}
}
}
}
}
// Bypass the nodes in order of increasing the keys
public void traverseTree(Node currentNode) {
if (currentNode != null) {
traverseTree(currentNode.leftChild);
System.out.println(currentNode);
traverseTree(currentNode.rightChild);
}
}
public void traverseTree() {
traverseTree(root);
}
// Search the node by key
public Node findNode(int key) {
Node focusNode = root;
while (focusNode.key != key) {
if (key < focusNode.key) {
focusNode = focusNode.leftChild;
}
else {
focusNode = focusNode.rightChild;
}
// Not found:
if (focusNode == null) {
return null;
}
}
return focusNode;
}
// Test:
public static void main(String[] args) {
BinaryTree continents = new BinaryTree();
continents.addNode(1, "Europe");
continents.addNode(3, "Africa");
continents.addNode(5, "Australia");
continents.addNode(4, "America");
continents.addNode(2, "Asia");
continents.addNode(6, "Antarctica");
continents.traverseTree();
System.out.println("\nContinent with key 4:");
System.out.println(continents.findNode(4));
}
}
3.10 Creating a New Container Based on the ArrayList
In the following example, a class is implemented to represent an array whose indexing begins with 1. It
is necessary to redefine all methods associated with the index. Inside, we can use
ArrayList:
package ua.inf.iwanoff.java.fourth;
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
@SuppressWarnings("unchecked")
public class ArrayFromOne<E> extends AbstractList<E> {
ArrayList<Object> arr = new ArrayList<>();
@Override
public E get(int index) {
return (E)arr.get(index – 1);
}
@Override
public int size() {
return arr.size();
}
@Override
public void add(int index, E element) {
arr.add(index – 1, element);
}
@Override
public boolean add(E e) {
return arr.add(e);
}
@Override
public E set(int index, E element) {
return (E)arr.set(index – 1, element);
}
@Override
public E remove(int index) {
return (E)arr.remove(index – 1);
}
@Override
public int indexOf(Object o) {
return arr.indexOf(o) + 1;
}
@Override
public int lastIndexOf(Object o) {
return arr.lastIndexOf(o) + 1;
}
@Override
public Iterator<E> iterator() {
return (Iterator<E>)arr.iterator();
}
public static void main(String[] args) {
ArrayFromOne<Integer> a = new ArrayFromOne<>();
a.add(1);
a.add(2);
System.out.println(a.get(1) + " " + a.get(2)); // 1 2
System.out.println(a.indexOf(2)); // 2
a.set(1, 3);
for (Integer k : a) {
System.out.print(k + " "); // 3 2
}
System.out.println();
a.remove(2);
System.out.println(a); // [3]
a.addAll(Arrays.asList(new Integer[]{ 4, 5 }));
System.out.println(a.get(3)); // 5
}
}
The @SuppressWarnings("unchecked") annotation before the class is required to
suppress the warnings associated with explicit type casting.
3.11 Storing Census Data in a List and in a Set
Suppose we need to create classes for working with censuses. The first of them will store data using a
list, the second
with a set. We can add such classes to the pre-created hierarchy. The first class will store the data in
the list. For
sorting by population, it's advisable to use the sort() static method of the
Collections
class.
For sorting by comments, it's advisable to use the sort() method of the List
interface. The
class code will be as follows:
package ua.inf.iwanoff.java.fourth;
import ua.inf.iwanoff.java.second.Census;
import ua.inf.iwanoff.java.second.AbstractCountry;
import java.util.*;
/**
* Class for presenting the country in which the censuses are carried out.
* Census data are represented with a list
*/
public class CountryWithList extends AbstractCountry {
private List<Census> list = new ArrayList<>();
/**
* Returns reference to the census by index in a sequence
* @param i census index
* @return reference to the census with given index
*/
@Override
public Census getCensus(int i) {
return list.get(i);
}
/**
* Sets a reference to a new census within the sequence
* according to the specified index.
* @param i census index
* @param census a reference to a new census
*/
@Override
public void setCensus(int i, Census census) {
list.set(i, census);
}
/**
* Adds a reference to a new census to the end of the sequence
* @param census a reference to a new census
* @return {@code true} if the reference has been added
* {@code false} otherwise
*/
@Override
public boolean addCensus(Census census) {
if (list.contains(census)) {
return false;
}
return list.add(census);
}
/**
* Creates a new census and adds a reference to it at the end of the sequence
* @param year year of census
* @param population population in the specified year
* @param comments the text of the comment
* @return {@code true} if the reference has been added
* {@code false} otherwise
*/
@Override
public boolean addCensus(int year, int population, String comments) {
return addCensus(new Census(year, population, comments));
}
/**
* Returns the number of censuses in the sequence
* @return count of censuses
*/
@Override
public int censusesCount() {
return list.size();
}
/**
* Removes all of the censuses from the sequence
*/
@Override
public void clearCensuses() {
list.clear();
}
/**
* Sorts the sequence of censuses by population
*/
@Override
public void sortByPopulation() {
Collections.sort(list);
}
/**
* Sorts the sequence of censuses in the alphabetic order of comments
*/
@Override
public void sortByComments() {
list.sort(Comparator.comparing(Census::getComments));
}
//**
* Puts data from an array of censuses into a sequence
* @param censuses array of references to censuses
*/
@Override
public void setCensuses(Census[] censuses) {
list = new ArrayList<>(Arrays.asList(censuses));
}
/**
* Returns an array of censuses obtained from the sequence
* @return array of references to censuses
*/
@Override public Census[] getCensuses() {
return list.toArray(new Census[0]);
}
/**
* Demonstration of functions' work
* @param args command line arguments (not used)
*/
public static void main(String[] args) {
new CountryWithList().createCountry().testCountry();
}
}
Now we can create a class that stores data in the set. Since the set is immediately ordered on a certain attribute, and it is not possible to sort it, it is possible to create different variants of data sets for the getting ordered sequences.
Since the beginning of the censuses should be arranged in ascending order of the year. The
CountryWithSet
class
code will be as follows:
package ua.inf.iwanoff.java.fourth;
import ua.inf.iwanoff.java.second.Census;
import ua.inf.iwanoff.java.second.AbstractCountry;
import java.util.Arrays;
import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;
/**
* Class for presenting the country in which the censuses are carried out.
* Census data are represented with a set
*/
public class CountryWithSet extends AbstractCountry {
private SortedSet<Census> set = new TreeSet<>(Comparator.comparing(Census::getYear));
/**
* Returns reference to the census by index in a sequence
* @param i census index
* @return reference to the census with given index
*/
@Override
public Census getCensus(int i) {
return set.toArray(new Census[0])[i];
}
/**
* Sets a reference to a new census within the sequence
* according to the specified index.
* @param i census index
* @param census a reference to a new census
*/
@Override
public void setCensus(int i, Census census) {
Census oldCensus = getCensus(i);
set.remove(oldCensus);
set.add(census);
}
/**
* Adds a reference to a new census to the end of the sequence
* @param census a reference to a new census
* @return {@code true} if the reference has been added
* {@code false} otherwise
*/
@Override
public boolean addCensus(Census census) {
return set.add(census);
}
/**
* Creates a new census and adds a reference to it at the end of the sequence
* @param year year of census
* @param population population in the specified year
* @param comments the text of the comment
* @return {@code true} if the reference has been added
* {@code false} otherwise
*/
@Override
public boolean addCensus(int year, int population, String comments) {
return set.add(new Census(year, population, comments));
}
/**
* Returns the number of censuses in the sequence
* @return count of censuses
*/
@Override
public int censusesCount() {
return set.size();
}
/**
* Removes all of the censuses from the sequence
*/
@Override
public void clearCensuses() {
set.clear();
}
/**
* Sorts the sequence of censuses by population
*/
@Override
public void sortByPopulation() {
SortedSet<Census> newSet = new TreeSet<>();
newSet.addAll(set);
set = newSet;
}
/**
* Sorts the sequence of censuses in the alphabetic order of comments
*/
@Override
public void sortByComments() {
SortedSet<Census> newSet = new TreeSet<>(Comparator.comparing(Census::getComments));
newSet.addAll(set);
set = newSet;
}
/**
* Puts data from an array of censuses into a sequence
* @param censuses array of references to censuses
*/
@Override
public void setCensuses(Census[] censuses) {
set = new TreeSet<>(Comparator.comparing(Census::getYear));
set.addAll(Arrays.asList(censuses));
}
/**
* Returns an array of censuses obtained from the sequence
* @return array of references to censuses
*/
@Override
public Census[] getCensuses() {
return set.toArray(new Census[0]);
}
/**
* Demonstration of functions' work
* @param args command line arguments (not used)
*/
public static void main(String[] args) {
new CountryWithSet().createCountry().testCountry();
}
}
The results of the programs should be identical.
4 Exercises
- Create an enumeration
DayOfWeek. Add methods for getting "the day before yesterday" and "the day after tomorrow." Test enumeration inmain()function of a test class. - Create an enumeration
Season. Describe the method of getting the previous and next season. Test enumeration inmain()function of a test class. - Create an enumeration
Continent. Override thetoString()method so that it shows the name of the continent in different languages. Test enumeration inmain()function of a test class. - Implement a static generic function of obtaining the index of the last occurrence of an item with a certain value. Test the function on two arrays of different types.
- Create a static generic function to replace the order of items in the opposite. Test function on two arrays of different types.
- Implement a static generic function for determining the number of occurrences some item in an array. Test function on two arrays of different types.
- Implement a static generic function of a cyclic shift of an array to a given number of items. Test function on two arrays of different types.
- Read from keyboard integer values and add them to a list. Find the product of the elements.
- Initialize a list of floating point values with an array of initial values. Find the sum of positive items
- Initialize a list of integers with an array of initial values. Find the product of nonzero items.
- Initialize a list of integers with an array of initial values. Create a new list composed of even elements of the original list.
- Initialize a list of floating point values with an array of initial values. Create a new list composed of positive elements of the original list.
- Initialize a list of strings with an array of initial values. Find and display a list item (string) with the maximum length.
- Initialize a list of strings with an array of initial values. Find and display index of string with the smallest length.
- Enter the number of elements of the future set of integers and the range of numbers. Fill this set with random values. Output elements in ascending order.
- Enter the number of elements of the future set of real numbers and the range of numbers. Fill this set with random values. Output the elements in descending order.
- Fill a set of integers with random positive even values (no more than a definite number). Output the result.
- Enter the word and output all the different letters of the word in alphabetical order.
- Enter a sentence and calculate the number of different letters from which the sentence is composed. Do not include spaces or punctuation marks.
- Enter a sentence and calculate the number of different words in the sentence.
- Initialize a list of integers with an array of initial values. Find the sum of the maximum and
minimum elements. Use features of
Collectionsclass. - Initialize a list of strings with an array of initial values. Allocate items in reverse order. Use
features of
Collectionsclass. - Create a function that calculates the square root, if possible, and returns an
OptionalDoubleobject. - Create a program in which all positive integers of the specified range are printed, if the sum of digits is equal to the specified value. Use data streams. Do not use explicit loops.
5 Quiz
- What is usage of enumerations?
- What is the purpose of definition constructor within enumeration?
- How to create a cycle of receiving all the constants described in the enumeration?
- What are the problems associated with creating generic containers?
- In what cases it is necessary to create generic classes?
- What is a parameterized type?
- How are generics different from C ++ templates?
- Why use generic functions?
- Is it possible to create objects of generic types?
- Is it possible to create arrays of generic types?
- Why you cannot store integer and floating point numbers directly in the container class, but only references?
- How to restrict the type of generics parameter and what opportunities it provides?
- What is the usage of a wildcard in the description of the parameters?
- Can I use wildcards when creating local variables?
- What is the usage of
Optionalclass? - Is it possible to use the
Optionalclass with primitive types? - What is a collection?
- What are the basic interfaces declared in the
java.utilpackage? - What containers are considered obsolete?
- Why integers and real numbers cannot be stored directly in the collection, but only references?
- How can you get a list from an array?
- How can you store integer and floating point values in Java lists?
- What is the advantage of definition of references to interfaces (e.g.,
List) compared to the definition of references to classes that implement these interfaces (e.g.,ArrayList)? - What are advantages of iterators compared to the index of the container item?
- When is it better to use
LinkedListcompared toArrayList(and vice versa)? - What data structure is used to implement
LinkedList? - What are the
Queueinterface methods used to add items? - Why are the methods for working with the queue implemented in two versions: with exception throwing and without exception throwing?
- What is the use of the
PriorityQueueclass? - What are the stacks used for?
- What are the standard ways to implement the stack?
- What algorithms does the
Collectionsclass provide? - What is a set different from the list?
- Give examples of associative arrays.
- What is the difference between
MapandSortedMapinterfaces? - How can "baskets" be used to store data in a hash table?
- What is a binary tree?
- What is a balanced and unbalanced tree?
- What is a red-black tree and what are its advantages?
- How to create your own container?
- How to implement a read-only container?