Java Advanced

Faster input and output

Scanner and System.out.print work well at first, but become less efficient when processing larger inputs, so we need methods to improve IO speed.

Using Kattio + StringTokenizer for input

One of the most common methods is to use Kattio.java from Kattis to improve IO efficiency.¹ This method wraps StringTokenizer and PrintWriter in one class for convenient use. When solving problems (if permitted by the contest or organizer), this template can be used directly.

The following is the IO template that should be included in the code. Since Kattis's original Kattio contains some less commonly used functionality, the template below has been adjusted (the original Kattio uses the MIT license).

class Kattio extends PrintWriter {
    private BufferedReader r;
    private StringTokenizer st;
    // Standard IO
    public Kattio() { this(System.in, System.out); }
    public Kattio(InputStream i, OutputStream o) {
        super(o);
        r = new BufferedReader(new InputStreamReader(i));
    }
    // File IO
    public Kattio(String intput, String output) throws IOException {
        super(output);
        r = new BufferedReader(new FileReader(intput));
    }
    // Return null when there is no more input
    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(r.readLine());
            return st.nextToken();
        } catch (Exception e) {}
        return null;
    }
    public int nextInt() { return Integer.parseInt(next()); }
    public double nextDouble() { return Double.parseDouble(next()); }
    public long nextLong() { return Long.parseLong(next()); }
}

The following code briefly demonstrates how to use Kattio:

class Test {
    public static void main(String[] args) {
        Kattio io = new Kattio();
        // String input
        String str = io.next();
        // int input
        int num = io.nextInt();
        // Output
        io.println("Result");
        // Make sure to close the IO stream so that the output is written correctly
        io.close();
    }
}

Using StreamTokenizer for input

In some cases, using StringTokenizer causes MLE (Memory Limit Exceeded). In that case, we need to use StreamTokenizer for input.

import java.io.*;
public class Main {
    // IO code
    public static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in), 32768));
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    public static double nextDouble() throws IOException { in.nextToken(); return in.nval; }
    public static float nextFloat() throws IOException { in.nextToken(); return (float)in.nval; }
    public static int nextInt() throws IOException { in.nextToken(); return (int)in.nval; }
    public static String next() throws IOException { in.nextToken(); return in.sval; }
    public static long nextLong() throws Exception { in.nextToken(); return (long)in.nval;}
    
    // Usage example
    public static void main(String[] args) throws Exception {
        int n = nextInt();
        out.println(n);
        out.close();
    }
}

Analysis and comparison of Kattio + StringTokenizer and StreamTokenizer

1. StreamTokenizer uses less memory than StringTokenizer. When a Java standard solution gets MLE, StreamTokenizer can be tried, but StreamTokenizer loses precision and can cause problems when reading some data;
   • The StreamTokenizer source contains Type; this Type determines the type according to the input. If a string such as 123oi starts with a digit, it is forcibly treated as type double, so reading it as a String through a double type causes an exception;
   • StreamTokenizer loses precision when reading numbers larger than 1e14;
2. When using PrintWriter, remember to call close() to close the output stream at the end of the program, or call flush() when output is needed to clear the buffer; otherwise, the contents will not be written to the console/file.
3. Kattio inherits from the PrintWriter class, so its objects have the functionality of PrintWriter and can directly call functions of the PrintWriter class for output; it also uses StringTokenizer as a member variable. The second Main, on the other hand, uses StreamTokenizer and PrintWriter as its member variables at the same time, so there are some differences in usage.

In summary, StringTokenizer is preferable to StreamTokenizer in most cases. StreamTokenizer can be tried in extreme MLE situations, but data beyond the range of int cannot be handled by StreamTokenizer.

BigInteger and number theory

BigInteger is a high-precision calculation class provided by Java and can conveniently solve high-precision problems.

Initialization

There are two common ways to create a BigInteger:

import java.io.PrintWriter;
import java.math.BigInteger;

class Main {
    static PrintWriter out = new PrintWriter(System.out);
    public static void main(String[] args) {
        BigInteger a = new BigInteger("12345678910");  // Create a BigInteger object from the string in base 10
        out.println(a);  // The value of a is 12345678910 
        BigInteger b = new BigInteger("1E", 16);  // Create a BigInteger object from the string in the specified base
        out.println(b);  // The value of b is 30 
        out.close();
    }
}

Basic operations

In the following, this denotes the current BigIntger:

Example:

import java.io.PrintWriter;
import java.math.BigInteger;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static BigInteger a, b;
    
    static void abs() {
        out.println("abs:");
        a = new BigInteger("-123");
        out.println(a.abs());  // Output 123 
        a = new BigInteger("123");
        out.println(a.abs());  // Output 123 
    }
    
    static void negate() {
        out.println("negate:");
        a = new BigInteger("-123");
        out.println(a.negate());  // Output 123 
        a = new BigInteger("123");
        out.println(a.negate());  // Output -123 
    }
    
    static void add() {
        out.println("add:");
        a = new BigInteger("123");
        b = new BigInteger("123");
        out.println(a.add(b));  // Output 246 
    }
    
    static void subtract() {
        out.println("subtract:");
        a = new BigInteger("123");
        b = new BigInteger("123");
        out.println(a.subtract(b));  // Output 0 
    }
    
    static void multiply() {
        out.println("multiply:");
        a = new BigInteger("12");
        b = new BigInteger("12");
        out.println(a.multiply(b));  // Output 144 
    }
    
    static void divide() {
        out.println("divide:");
        a = new BigInteger("12");
        b = new BigInteger("11");
        out.println(a.divide(b));  // Output 1 
    }
    
    static void remainder() {
        out.println("remainder:");
        a = new BigInteger("12");
        b = new BigInteger("10");
        out.println(a.remainder(b));  // Output 2 
        a = new BigInteger("-12");
        b = new BigInteger("10");
        out.println(a.remainder(b));  // Output -2 
    }
    
    static void mod() {
        out.println("mod:");
        a = new BigInteger("12");
        b = new BigInteger("10");
        out.println(a.mod(b));  // Output 2 
        a = new BigInteger("-12");
        b = new BigInteger("10");
        out.println(a.mod(b));  // Output 8 
    }
    
    static void pow() {
        out.println("pow:");
        a = new BigInteger("2");
        out.println(a.pow(10));  // Output 1024 
    }
    
    static void and() {
        out.println("and:");
        a = new BigInteger("3");  // 11 
        b = new BigInteger("5");  // 101 
        out.println(a.and(b));  // Output 1 
    }
    
    static void or() {
        out.println("or:");
        a = new BigInteger("2");  // 10 
        b = new BigInteger("5");  // 101 
        out.println(a.or(b));  // Output 7 
    }
    
    static void not() {
        out.println("not:");
        a = new BigInteger("2147483647");  // 01111111 11111111 11111111 11111111 
        out.println(a.not());  // Output -2147483648, whose binary representation is: 10000000 00000000 00000000 00000000 
    }
    
    static void xor() {
        out.println("xor:");
        a = new BigInteger("6");  // 110 
        b = new BigInteger("5");  // 101 
        out.println(a.xor(b));  // 011, output 3 
    }
    
    static void shiftLeft() {
        out.println("shiftLeft:");
        a = new BigInteger("1");
        out.println(a.shiftLeft(10));  // Output 1024 
    }
    
    static void shiftRight() {
        out.println("shiftRight:");
        a = new BigInteger("1024");
        out.println(a.shiftRight(8));  // Output 4 
    }
    
    static void max() {
        out.println("max:");
        a = new BigInteger("6");
        b = new BigInteger("5");
        out.println(a.max(b));  // Output 6 
    }
    
    static void min() {
        out.println("min:");
        a = new BigInteger("6");
        b = new BigInteger("5");
        out.println(a.min(b));  // Output 5 
    }
    
    static void bitCount() {
        out.println("bitCount:");
        a = new BigInteger("6");  // 110 
        out.println(a.bitCount());  // Output 2 
    }
    
    static void bitLength() {
        out.println("bitLength:");
        a = new BigInteger("6");  // 110 
        out.println(a.bitLength());  // Output 3 
    }
    
    static void getLowestSetBit() {
        out.println("getLowestSetBit:");
        a = new BigInteger("8");  // 1000 
        out.println(a.getLowestSetBit());  // Output 3 
    }
    
    static void compareTo() {
        out.println("compareTo:");
        a = new BigInteger("8");
        b = new BigInteger("9");
        out.println(a.compareTo(b));  // Output -1 
        a = new BigInteger("8");
        b = new BigInteger("8");
        out.println(a.compareTo(b));  // Output 0 
        a = new BigInteger("8");
        b = new BigInteger("7");
        out.println(a.compareTo(b));  // Output 1 
    }
    
    static void toStringTest() {
        out.println("toString:");
        a = new BigInteger("15");
        out.println(a.toString());  // Output 15 
        out.println(a.toString(16));  // Output f 
    }
    
    public static void main(String[] args) {
        abs();
        negate();
        add();
        subtract();
        multiply();
        divide();
        remainder();
        mod();
        pow();
        and();
        or();
        not();
        xor();
        shiftLeft();
        shiftRight();
        max();
        min();
        bitCount();
        bitLength();
        getLowestSetBit();
        compareTo();
        toStringTest();
        out.close();
    }
}

Mathematical operations

In the following, this denotes the current BigIntger:

Example:

import java.io.PrintWriter;
import java.math.BigInteger;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static BigInteger a, b, p;
    
    static void gcd() {  // Greatest common divisor 
        a = new BigInteger("120032414321432144212100");
        b = new BigInteger("240231431243123412432140");
        out.println(String.format("gcd(%s,%s)=%s", a.toString(), b.toString(), a.gcd(b).toString()));  // gcd(120032414321432144212100,240231431243123412432140)=20 
    }
    
    static void isPrime() {  // Use Miller-Rabin to determine whether the number is prime; a larger parameter gives higher accuracy and complexity. Accuracy is (1-1/(val*2)) 
        a = new BigInteger("1200324143214321442127");
        out.println("a:" + a.toString());
        out.println(a.isProbablePrime(10) ? "a is prime" : "a is not prime");  // a is not prime 
    }
    
    static void nextPrime() {  // Find the next prime after this number 
        a = new BigInteger("1200324143214321442127");
        out.println("a:" + a.toString());
        out.println(String.format("a nextPrime is %s", a.nextProbablePrime().toString()));  // a nextPrime is 1200324143214321442199 
    }
    
    static void modPow() {  // Fast exponentiation, faster than the ordinary version; mathematical optimizations are used internally 
        a = new BigInteger("2");
        b = new BigInteger("10");
        p = new BigInteger("1000");
        out.println(String.format("a:%s b:%s p:%s", a, b, p));
        out.println(String.format("a^b mod p:%s", a.modPow(b, p).toString()));//  24 
    }
    
    static void modInverse() {  // Multiplicative inverse 
        a = new BigInteger("10");
        b = new BigInteger("3");
        out.println(a.modInverse(b));  // a ^ (p-2) mod p = 1 
    }
    
    public static void main(String[] args) {
        gcd();
        isPrime();
        nextPrime();
        modPow();
        modInverse();
        out.close();
    }
}

For related knowledge about Miller-Rabin, see Miller–Rabin primality test.

Primitive and wrapper data types

Introduction

Because primitive types do not have object-oriented characteristics, Java provides corresponding wrapper classes for its eight primitive types so that they can participate in object-oriented development: Byte, Double, Float, Integer, Long, Short, Character, and Boolean. Their correspondence is as follows:

Differences

Here int and Integer are used as examples:

1. Integer is the wrapper class for int, while int is a primitive data type in Java.
2. An instance must be created before an Integer can be used, while an int does not need this.
3. Integer corresponds to a reference. When an Integer is newed, an object is actually created, whereas int stores data directly.
4. The default value of Integer is null, and it can accept null and int data; the default value of int is 0, and it cannot accept data of type null.
5. Using == to determine whether two Integer variables are equal may produce an incorrect result; only equals() should be used, while int can use == directly.

Boxing and unboxing

Here int and Integer are used as examples:

Integer is essentially an object, while int is a primitive type, so the two types cannot be assigned directly to each other. When conversion is needed, converting a primitive type to a wrapper type is called boxing, and the reverse is called unboxing.

// Primitive type
int value1 = 1;
// Box into a wrapper type
Integer integer = Integer.valueOf(value1);
// Unbox into a primitive type
int value2 = integer.intValue();

Java 5 introduced automatic boxing and unboxing:

Integer integer = 1;
int value = integer;

Integer integer = Integer.valueOf(null);
integer.intValue();  // Throws a java.lang.NumberFormatException

Integer integer = null;
integer.intValue();  // Throws a java.lang.NullPointerException

Inheritance

Inheritance in object-oriented programming is the creation of a new design based on an existing design. In inheritance, a new class is not created from nothing; it is defined based on an existing class. Through inheritance, a new class automatically obtains all members of the base class, including member variables and methods and members with all kinds of access attributes, whether public or private. Clearly, defining a new class through inheritance is much simpler, faster, and more convenient than writing a new class from scratch. Inheritance is one of the important means of supporting code reuse.

In Java, the keyword for inheritance is extends. Java supports only single inheritance, but multiple interfaces can be implemented.

In Java, all classes are subclasses of the Object class.

A subclass inherits from its superclass. All members of the superclass, including variables and methods, become members of the subclass, except constructors. Constructors are unique to the superclass because their names are the names of the class, so the superclass's constructors do not exist in the subclass. Apart from this, the subclass inherits all members of the superclass.

Each member has a different access attribute. A subclass inherits all members of its superclass, but different access attributes make those members behave differently when used by the subclass: some superclass members directly become part of the subclass's public interface, while others are deeply hidden and cannot be accessed directly even by the subclass itself.

The following table lists the access attributes of superclass members in the subclass:

Polymorphism

In Java, when an object is assigned to a variable, the object's type must match the variable's type. However, because Java has inheritance, this can be redefined as a variable can hold an object of its declared type or any subtype of that type.

If a type implements an interface, it can also be called a subtype of that interface.

A variable that holds an object type in Java is a polymorphic variable. The term "polymorphism" (literally, many forms) means that a variable can hold objects of different types (that is, its declared type or any subtype).

Polymorphic variables:

1. Java's object variables are polymorphic; they can hold objects of more than one type.
2. They can hold an object of the declared type or an object of a subclass of the declared type.
3. When an object of a subclass is assigned to a superclass variable, an upcast occurs.

Generics

Generics means that the concrete types of attributes or method parameters in a class are not set when the class is defined; types are defined later when the class is used (or an object is created). Generics are essentially parameterized types: the data type being operated on is specified as a parameter.

Generics provide a mechanism for compile-time type-safety checking, which allows illegal types to be detected at compile time.

Interfaces

Introduction

An interface is an abstract type in Java and a collection of abstract methods, usually declared with interface. A class inherits an interface's abstract methods by implementing the interface.

An interface is not a class. The way an interface is written is similar to that of a class, but they are different concepts. A class describes an object's attributes and methods, while an interface contains methods that a class must implement.

Unless the class implementing an interface is abstract, it must define all methods in the interface.

An interface cannot be instantiated, but it can be implemented. A class implementing an interface must implement all methods described in the interface, or it must be declared abstract. In Java, an interface type can also be used to declare a variable; such a variable can be a null pointer or bound to an object that implements the interface.

Differences from classes

1. An interface cannot be used to instantiate an object.
2. An interface has no constructor.
3. All methods in an interface must be abstract methods; after Java 8, an interface may contain non-abstract methods modified with the default keyword.
4. An interface cannot contain member variables, except static and final variables.
5. An interface is not inherited by a class; it is implemented by a class.
6. Interfaces support multiple inheritance, while classes do not.

Declaration

[visibility] interface InterfaceName [extends OtherInterface] {
        // Declare variables
        // Abstract methods
}

Implementation

...implements InterfaceName[, OtherInterface, AnotherInterface, ...] ...

Lambda expressions

Introduction

Lambda expressions, also called closures, are one of the most important new features of Java 8.

Lambda expressions allow a function to be used as a method parameter (a function is passed into a method as an argument).

Using lambda expressions can make code more concise and compact.

Syntax

• Optional type declaration: parameter types do not need to be declared; the compiler can identify parameter values uniformly.
• Optional parentheses around parameters: parentheses are unnecessary for one parameter but required for multiple parameters.
• Optional braces: if the body contains one statement, braces are unnecessary.
• Optional return keyword: if the body has only one expression as its return value, the compiler returns it automatically; with braces, the expression returning a value must be specified.

Lambda expressions are declared as follows:

// 1. No parameters; return value is 5
() -> 5

// 2. Receive one parameter (numeric type) and return twice its value
x -> 2 * x

// 3. Receive two parameters (numbers) and return their difference
(x, y) -> x – y

// 4. Receive two int values and return their sum
(int x, int y) -> x + y

// 5. Receive a String object and print it to the console without returning a value (it appears to return void)
(String s) -> System.out.print(s)

Taking a custom comparator that sorts a string array by length as an example, a lambda expression can be applied as follows.

import java.util.Arrays;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    
    public static void main(String[] args) {
        String[] plants = {"Mercury", "venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus", "Neptune"};
        Arrays.sort(plants, (String first, String second) -> (first.length() - second.length()));
        for (String word : plants) {
            out.print(word + " ");
        }
        out.close();
    }
}

Multiple statements can also be used in a lambda expression, as in the following example.

import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    
    public static void main(String[] args) {
        String[] plants = {"Mercury", "venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus", "Neptune"};
        Arrays.sort(plants, (first, second) ->
        {
            // The parameter types are omitted and can be inferred from the context
            int result = first.length() - second.length();
            return result;
        });
        for (String word : plants) {
            out.print(word + " ");
        }
        out.close();
    }
}

Here, -> is a deduction symbol: it means that the parentheses receive the parameters and the return value is deduced afterward (in fact, the method is passed through).

Functional interfaces

1. It is an interface that conforms to the Java interface definition.
2. It is an interface containing only one abstract method.
3. Because there is only one unimplemented method, a lambda expression can fill it in automatically.

Functional interfaces are used as follows:

import java.io.PrintWriter;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        String[] plants = {"Mercury", "venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus", "Neptune"};
        Test test = s -> {  // A lambda expression as an instance of a functional interface
            if (s.length() % 2 == 0) {
                return true;
            }
            return false;
        };
        for (String word : plants) {
            if (test.check(word)) {
                out.print(word + " ");
            }
        }
        out.close();
    }
}

interface Test {
    public boolean check(String s);
}

import java.io.PrintWriter;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    public static double calc(double a, double b, Calculator util) {
        return util.operation(a, b);
    }

    public static void main(String[] args) {
        Calculator util[] = new Calculator[4];  // Define an array of functional interfaces
        util[0] = (a, b) -> a + b;
        util[1] = (a, b) -> a - b;
        util[2] = (a, b) -> a * b;
        util[3] = (a, b) -> a / b;
        double a = 20, b = 15;
        for (Calculator c : util) {
            System.out.println(calc(a, b, c));
        }
        out.close();
    }
}

interface Calculator {
    public double operation(double a, double b);
}

Collection

Collection is an interface in Java implemented by multiple generic container interfaces. Here, Collection refers to a data structure that stores objects.

The element type of a Java Collection must be an object type, not a primitive data type.

The following usage is based on polymorphism in Java and appears in the form of interface implementations.

Common interfaces include List, Queue, Set, and Map.

Container definition

When defining a generic container class, specify the data type at definition time. If no data type is specified and data is added freely as type Object, Java 8 can still compile it, but there are many risks of warnings.

For example, the following definition is safe: the container accepts only Integer values.

List<Integer> list1 = new LinkedList<>();

The following definition produces warnings.

List list = new ArrayList<>();
list.add(1);
list.add(true);
list.add(1.01);
list.add(1L);
list.add("I am String");

Therefore, unless there is a special need, the second approach is not recommended: the compiler cannot check whether the stored data is safe. When list.get(index) retrieves a value, its type cannot be determined (all retrieved values have type Object), so it must be manually converted back to its original type, and a slight mistake may cause a ClassCastException.

If the type is specified, such as List<Integer>, the compiler checks the type of inserted data, and only integer data can be inserted. When declaring a collection variable, use a wrapper type such as List<Integer> or a custom Class, not a primitive type such as List<int>.

List

ArrayList

ArrayList is an array that can grow dynamically as needed. Its initial length defaults to 10; if the current length is exceeded, it expands by a factor of $\dfrac{3}{2}$.

Initialization

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    
    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>();  // Create an automatically growing array named list1 with the default initial length (10)
        List<Integer> list2 = new ArrayList<>(30);  // Create an automatically growing array named list2 with an initial length of 30
        List<Integer> list3 = new ArrayList<>(list2);  // Create an automatically growing array named list3, using the elements and size of list2 as its initial value
    }
}

LinkedList

LinkedList is a doubly linked list.

Initialization

import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.List;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    
    public static void main(String[] args) {
        List<Integer> list1 = new LinkedList<>();  // Create a doubly linked list named list1
        List<Integer> list2 = new LinkedList<>(list1);  // Create a doubly linked list named list2 and add all elements from list1
    }
}

Common methods

In the following table, this denotes the current List<Integer>:

Usage example and comparison:

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static List<Integer> array = new ArrayList<>();
    static List<Integer> linked = new LinkedList<>();
    
    static void add() {
        array.add(1);  // Time complexity is O(1) 
        linked.add(1);  // Time complexity is O(1) 
    }
    
    static void get() {
        array.get(10);  // Time complexity is O(1) 
        linked.get(10);  // Time complexity is O(11) 
    }
    
    static void addIdx() {
        array.add(0, 2);  // Worst-case time complexity is O(n)
        linked.add(0, 2);  // Worst-case time complexity is O(n)
    }
    
    static void size() {
        array.size();  // Time complexity is O(1)
        linked.size();  // Time complexity is O(1)
    }
    
    static void set() {  // This method returns the original value at that position
        array.set(0, 1);  // Time complexity is O(1)
        linked.set(0, 1);  // Worst-case time complexity is O(n)
    }

}

Traversal

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static List<Integer> array = new ArrayList<>();
    static List<Integer> linked = new LinkedList<>();
    
    static void function1() {  // naive traversal
        for (int i = 0; i < array.size(); i++) {
            out.println(array.get(i));  // traverse the dynamic array, with complexity O(n)
        }
        for (int i = 0; i < linked.size(); i++) {
            out.println(linked.get(i));  // traverse the doubly linked list, with complexity O(n^2)，because LinkedList get(i) has complexity O(i)
        }
    }
    
    static void function2() {  // enhanced for-loop traversal 
        for (int e : array) {
            out.println(e);
        }
        for (int e : linked) {
            out.println(e);  // the complexity is O(n) for both O(n) 
        }
    }
    
    static void function3() {  // iterator traversal 
        Iterator<Integer> iterator1 = array.iterator();
        Iterator<Integer> iterator2 = linked.iterator();
        while (iterator1.hasNext()) {
            out.println(iterator1.next());
        }
        while (iterator2.hasNext()) {
            out.println(iterator2.next());
        }  // the complexity is O(n) for both O(n) 
    }

}

Queue

LinkedList

A normal queue can be implemented with LinkedList, whose underlying structure is a linked list.

Initialization

Queue<Integer> q = new LinkedList<>();

LinkedList implements both the List and Deque interfaces. Since Deque extends Queue, LinkedList can be used as both a List and a Queue.

ArrayDeque

A normal queue can be implemented with ArrayDeque, whose underlying structure is an array.

Initialization

Queue<Integer> q = new ArrayDeque<>();

ArrayDeque implements Deque, and Deque extends Queue, so ArrayDeque can be used as a Queue.

Differences between LinkedList and ArrayDeque as Queue Implementations

1. Data structure: ArrayDeque and LinkedList both implement Java's Deque interface. However, ArrayDeque does not implement Java's List interface, so it cannot perform index-based operations.
2. Thread safety: neither ArrayDeque nor LinkedList performs synchronization, so neither is thread-safe.
3. Implementation: ArrayDeque is backed by a dynamic array, whereas LinkedList is backed by a doubly linked list.
4. Traversal speed: ArrayDeque occupies contiguous memory and benefits from locality when using the CPU cache, while LinkedList uses scattered memory and is less cache-friendly.
5. Operation speed: stack and queue operations on both have $O(1)$ time complexity. Pushing and enqueuing into ArrayDeque may trigger resizing, but the amortized complexity is still $O(1)$. The ArrayDeque implementation is backed by a dynamic array.
6. Extra memory: ArrayDeque keeps unused space around the head and tail of its array, while LinkedList stores predecessor and successor pointers in each LinkedList node.

PriorityQueue

PriorityQueue is a priority queue that is a min-heap by default.

Initialization

Queue<Integer> q1 = new PriorityQueue<>();  // min-heap
Queue<Integer> q2 = new PriorityQueue<>((x, y) -> {return y - x;});  // max-heap

Common Methods

In the table below, the queue is declared as Queue<Integer>.

Example comparing their use and behavior:

import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Queue<Integer> q1 = new LinkedList<>();
    static Queue<Integer> q2 = new PriorityQueue<>();
    
    static void add() {  // add and offer have the same function; the difference is whether an exception is thrown 
        q1.add(1);  // time complexity is O(1) 
        q2.add(1);  // time complexity is O(logn) 
    }
    
    static void isEmpty() {
        q1.isEmpty();  // time complexity is O(1) 
        q2.isEmpty();  // space complexity is O(1) 
    }
    
    static void size() {
        q1.size();  // time complexity is O(1) 
        q2.size();  // returns the length of q2 
    }
    
    static void peek() {
        q1.peek();  // time complexity is O(1) 
        q2.peek();  // time complexity is O(logn) 
    }
    
    static void poll() {
        q1.poll();  // time complexity is O(1) 
        q2.poll();  // time complexity is O(logn) 
    }
}

Traversal

import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Queue<Integer> q1 = new LinkedList<>();
    static Queue<Integer> q2 = new PriorityQueue<>();
    
    static void test() {
        while (!q1.isEmpty()) {  // complexity is O(n) 
            out.println(q1.poll());
        }
        while (!q2.isEmpty()) {  // complexity is O(nlogn) 
            out.println(q2.poll());
        }
    }

}

Deque

Deque is Java's double-ended queue. It is commonly used for both queue and stack operations.

Main Functions

In the table below, the deque is declared as Deque<Integer>.

Stack Operations

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static Deque<Integer> stack = new ArrayDeque<>();
    static int[] a = {1, 2, 3, 4, 5};
    
    public static void main(String[] args) {
        for (int v : a) {
            stack.push(v);
        }
        while (!stack.isEmpty()) { //prints 5 4 3 2 1
            System.out.println(stack.pop()); 
        }
    }
}

Deque Operations

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static Deque<Integer> deque = new ArrayDeque<>();
    
    static void insert() {
        deque.addFirst(1);
        deque.addFirst(2);
        deque.addLast(3);
        deque.addLast(4);
    }
    
    public static void main(String[] args) {
        insert();
        while (!deque.isEmpty()) { //prints 2 1 3 4
            System.out.println(deque.poll());
        }
        insert();
        while (!deque.isEmpty()) { //prints 4 3 1 2
            System.out.println(deque.pollLast());
        }
    }
}

Set

A Set is a data structure that keeps all elements in a container distinct.

HashSet

A Set with insertion at arbitrary positions.

Initialization

Set<Integer> s1 = new HashSet<>();

LinkedHashSet

A Set that preserves insertion order.

Initialization

Set<Integer> s2 = new LinkedHashSet<>();

TreeSet

A Set that keeps its elements ordered, in ascending order by default.

Initialization

Set<Integer> s3 = new TreeSet<>();
Set<Integer> s4 = new TreeSet<>((x, y) -> {return y - x;});  // descending order 

More Uses of TreeSet

These methods are newly provided by TreeSet. They cannot be called through the Set interface, so create the object as follows:

TreeSet<Integer> s3 = new TreeSet<>();
TreeSet<Integer> s4 = new TreeSet<>((x, y) -> {return y - x;});  // descending order 

In the table below, this denotes the current TreeSet<Integer>.

Code example:

import java.util.TreeSet;

public class Main {
    static int[] a = {4,7,1,2,3,6};
    
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        for(int v:a) {
            set.add(v);
        }
        Integer a2 = set.first();
        System.out.println(a2); //returns 1
        Integer a3 = set.last();
        System.out.println(a3); //returns 7
        Integer a4 = set.floor(5);
        System.out.println(a4); //returns 4
        Integer a5 = set.ceiling(6);
        System.out.println(a5); //returns 6
        Integer a6 = set.higher(7);
        System.out.println(a6); //returns null
        Integer a7 = set.lower(2);
        System.out.println(a7); //returns 1
        Integer a8 = set.pollFirst();
        System.out.println(a8); //returns 1
        Integer a9 = set.pollLast();
        System.out.println(a9); //returns 7
    }
}

Common Set Methods

import java.io.PrintWriter;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Set<Integer> s1 = new HashSet<>();
    static Set<Integer> s2 = new LinkedHashSet<>();
    
    static void add() {
        s1.add(1);
    }
    
    static void contains() {  // check whether set contains the value 2; return true if so and false otherwise 
        s1.contains(2);
    }
    
    static void test1() {  // s1 and s2 's union 
        Set<Integer> res = new HashSet<>();
        res.addAll(s1);
        res.addAll(s2);
    }
    
    static void test2() {  // s1 and s2 's intersection 
        Set<Integer> res = new HashSet<>();
        res.addAll(s1);
        res.retainAll(s2);
    }
    
    static void test3() {  // difference set：s1 - s2 
        Set<Integer> res = new HashSet<>();
        res.addAll(s1);
        res.removeAll(s2);
    }
}

Traversal

import java.io.PrintWriter;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Set<Integer> s1 = new HashSet<>();
    static Set<Integer> s2 = new LinkedHashSet<>();
    
    static void test() {
        for (int key : s1) {
            out.println(key);
        }
        out.close();
    }
}

Map

A Map stores key-value pairs <Key, Value>, with each Key unique.

HashMap

A Map with arbitrary insertion order.

Initialization

Map<Integer, Integer> map1 = new HashMap<>();

LinkedHashMap

A Map that preserves insertion order.

Initialization

Map<Integer, Integer> map2 = new LinkedHashMap<>();

TreeMap

A Map that keeps its keys ordered, in ascending order by default.

Initialization

Map<Integer, Integer> map3 = new TreeMap<>();
Map<Integer, Integer> map4 = new TreeMap<>((x, y) -> {return y - x;});  // descending order

Common Methods

In the following table, this denotes the current Map<Integer, Integer>.

Example:

import java.io.PrintWriter;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    
    static Map<Integer, Integer> map1 = new HashMap<>();
    static Map<Integer, Integer> map2 = new LinkedHashMap<>();
    static Map<Integer, Integer> map3 = new TreeMap<>();
    static Map<Integer, Integer> map4 = new TreeMap<>((x,y)->{return y-x;});
    
    static void put(){  // return the element with key 1 and value 1
        map1.put(1, 1);
    }
    static void get(){  // return the value for key 1
        map1.get(1);
    }
    static void containsKey(){  // check whether there is a key-value pair with key 1
        map1.containsKey(1);
    }
    static void KeySet(){
        map1.keySet();
    }
}

Traversal

import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    
    static Map<Integer, Integer> map1 = new HashMap<>();
    
    static void print() {
        for (int key : map1.keySet()) {
            out.println(key + " " + map1.get(key));
        }
    }
}

The key and value types can of course also be changed. For example, a Map can be declared as follows:

Map<String, Set<Integer>> map = new HashMap<>();

Arrays

Arrays is a utility class in java.util for array operations. Its methods are static and can be called directly through the class name.

Arrays.sort()

Arrays.sort() sorts arrays. Its main overloads are as follows:

import java.util.Arrays;
import java.util.Comparator;

public class Main {
    static int[] a = new int[10];
    static Integer[] b = new Integer[10];
    static int firstIdx, lastIdx;
    
    public static void main(String[] args) {
        Arrays.sort(a);  // 1 
        Arrays.sort(a, firstIdx, lastIdx);  // 2 
        Arrays.sort(b, new Comparator<Integer>() {  // 3 
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        Arrays.sort(b, firstIdx, lastIdx, new Comparator<Integer>() {  // 4 
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        // Since Java 8 supports lambda expressions, overloads 3 and 4 can also be written as 
        Arrays.sort(b, (x, y) -> {  // 5 
            return y - x;
        });
        Arrays.sort(b, (x, y) -> {  // 6 
            return y - x;
        });
    }
}

The overloads corresponding to the numbers mean:

1. Sort array a in ascending order by default.
2. Sort a specified range of a in ascending order by default; the range is left-closed and right-open, [firstIdx, lastIdx).
3. Sort a with a custom comparator. With the second argument - the first argument is sorted in descending order; with the first argument - the second is sorted in ascending order. A custom comparator requires an object element type.
4. Apply a custom sort to a specified range of a, [firstIdx, lastIdx). A custom comparator again requires an object element type.
5. As in 3, but with a lambda expression to shorten the code.
6. As in 4, but with a lambda expression to shorten the code.

This can be verified with the following code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static class FastReader {
        StringTokenizer st;
        BufferedReader br;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    static PrintWriter out = new PrintWriter(System.out);
    static FastReader in = new FastReader();

    static void solve() {
        int n = in.nextInt();
        // Changing the array type here from Integer to int causes TLE
        Integer[] a = new Integer[n + 10];
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
        }
        Arrays.sort(a, 1, n + 1);
        long left = a[1];
        long right = 0;
        int x = n;
        for (int i = 2; i < x; i++, x--) {
            left = left + a[i];
            right = right + a[x];
            if (right > left) {
                out.println("YES");
                return;
            }
        }
        out.println("NO");
    }

    public static void main(String[] args) {
        int t = in.nextInt();
        while (t-- > 0) {
            solve();
        }
        out.close();
    }
}

Arrays.binarySearch()

Arrays.binarySearch() performs binary search over a contiguous range of an array. The array must be sorted first, and the time complexity is $O(\log_n)$. Its main overloads are as follows:

import java.util.Arrays;

public class Main {
    static int[] a = new int[10];
    static Integer[] b = new Integer[10];
    static int firstIdx, lastIdx;
    static int key;
    
    public static void main(String[] args) {
        Arrays.binarySearch(a, key);  // 1 
        Arrays.binarySearch(a, firstIdx, lastIdx, key);  // 2 
    }
}

The source code is as follows:

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
    int low = fromIndex;
    int high = toIndex - 1;
    
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];
        
        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

The overloads corresponding to the numbers mean:

1. Binary-search array a for key; return its index if found, or a negative number otherwise.
2. Binary-search the left-closed, right-open range [firstIdx,lastIdx) of array a for key; return its index if found, or a negative number otherwise.

Arrays.fill()

Arrays.fill() assigns the same value to a contiguous range of an array. It takes the array, fromIndex, toIndex, and the value to fill. After it runs, every element in the left-closed, right-open range [firstIdx,lastIdx) has the fill value.

Collections

Collections is a utility class in java.util for collection operations. Its methods are static and can be called directly through the class name.

Collections.sort()

Internally, Collections.sort() converts all elements to an array, calls Arrays.sort(), and then writes the sorted elements back to the original collection. Since elements of a Java Collection are object types, merge sort is always used.

This method cannot sort a specified range of a collection.

The underlying source code:

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

Collections.binarySearch()

Collections.binarySearch() performs binary search over a specified range of a collection and has the same function as Arrays.binarySearch().

Collections.binarySearch(list, key);

This method cannot search a specified range.

Collections.swap()

Collections.swap() exchanges the elements at two specified positions in a collection.

 Collections.swap(list, i, j);

Other Topics

Numeric Comparison

In Java, -0.0 = 0.0 for primitive numeric types, but -0.0 != 0.0 for object types. This can cause trouble when using a Set to count slopes. A workaround is to add 0.0 to every slope before inserting it into the Set.

import java.io.PrintWriter;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    
    static void A() {
        Double a = 0.0;
        Double b = -0.0;
        out.println(a.equals(b));  // false 
    }
    
    static void B() {
        Double a = 0.0;
        Double b = -0.0 + 0.0;
        out.println(a.equals(b));  // true 
    }
    
    static void C() {
        double a = 0.0;
        double b = -0.0;
        out.println(a == b);  // true 
    }
    
    
    public static void main(String[] args) {
        A();
        B();
        C();
        out.close();
    }
}

References