Java Basic to Learn the Algo Notes

Tips

Starting from 2024/8/10, all articles and exercises on this site have been manually calibrated to correct chatGPT translation errors. However, if you have time, it is still recommended to learn the basic syntax of Java.

I recommend learning algorithms using the Java language for several reasons:

1. Java is a strongly-typed language. Since we are learning to use various data structures to write algorithms, it is important to clearly know the type of each variable. This makes debugging easier and allows the IDE to perform syntax checks. In contrast, dynamic languages like Python have less apparent variable types, which might hinder understanding.

2. Java is straightforward and lacks unnecessary complex language features. Even if you haven't learned Java before, you can easily understand the logic by looking at the code.

Moreover, beyond algorithms, I suggest learning multiple programming languages, especially widely-used ones like Java. No one's career will solely involve a single programming language. Typically, a job change also means a change in the technology stack, so understanding the basic syntax of mainstream programming languages will greatly assist your future work.

All solution codes on this site avoid Java's advanced language features and are written in the simplest and most readable way.

Below, I will guide you through the basic Java usage needed for learning my algorithm tutorials, so those unfamiliar with Java can smoothly follow along.

Firstly, there are many online resources for basic Java knowledge, so I won't reinvent the wheel. I'll just share a random Chinese tutorial. If you have a preferred Java tutorial, feel free to use it:

https://www.runoob.com/java/java-tutorial.html

I've highlighted the basic Java usage section that you should review. Of course, this site also contains other Java fundamentals that you can quickly browse through if you have time:

Next, I will specifically introduce the Java standard library data structures and some language features that might be tricky in the tutorials.

Basic Usage of Java Standard Library Data Structures

In Java, the most basic data types are called Primitive Types, such as int, char, long, and boolean, which use lowercase keywords. Most of you should be familiar with these from learning C language, as C mainly comprises primitive types, and even strings are represented using char[] character arrays, manipulated only through pointers, making it quite inconvenient.

However, as a high-level programming language, Java provides many advanced data types encapsulated as classes (class names in Java start with an uppercase letter). For instance, strings in Java are represented by the String class, which includes methods like length() and substring(). This means we don't have to worry about underlying operations, making usage much more convenient.

Here are some basic Java types.

1. Array.

Initialization method:

int m = 5, n = 10;

// initialize an int array of size 10
// where values are initialized to 0 by default
int[] nums = new int[n]

// initialize a 2D boolean array of size m * n
// where elements are initialized to false by default
boolean[][] visited = new boolean[m][n];

As a primitive type, this is similar to the int array in C language. If more complex operations are involved, it can be cumbersome to use. Therefore, we often use the dynamic array ArrayList.

2. Strings String

Handling strings in Java is quite troublesome because it doesn't support direct access to characters using [], and strings cannot be modified directly. You need to convert them to char[] type to modify them. Here are some features of String that we will use:

String s1 = "hello world";
// get the character at s1[2] which is 'l'
char c = s1.charAt(2);

char[] chars = s1.toCharArray();
chars[1] = 'a';
String s2 = new String(chars);
// output: hallo world
System.out.println(s2);

// note, always use the equals method to check if strings are the same
if (s1.equals(s2)) {
    // s1 and s2 are the same
} else {
    // s1 and s2 are not the same
}

// strings can be concatenated using the plus sign
String s3 = s1 + "!";
// output: hello world!
System.out.println(s3);

In Java, strings cannot be modified directly. You need to convert the string to a char[] array using toCharArray, make the modifications, and then convert it back to a String.

Additionally, although strings support concatenation using the + operator, it is not very efficient and is not recommended for use within a for loop. If you need to perform frequent string concatenations, it is recommended to use StringBuilder or StringBuffer:

StringBuilder sb = new StringBuilder();

for (char c = 'a'; c <= 'f'; c++) {
    sb.append(c);
}

// append method supports concatenating characters, strings, numbers, etc.
sb.append('g').append("hij").append(123);

String res = sb.toString();
// Output: abcdefghij123
System.out.println(res);

Another important issue is the comparison of string equality. This issue involves language features. Simply put, you must use the equals method to compare whether two strings are the same. Do not use == for comparison, as this may cause subtle bugs.

3. Dynamic Array ArrayList

ArrayList is essentially a wrapper around Java's built-in array type. Here is the initialization method:

// initialize a dynamic array to store String type
ArrayList<String> strings = new ArrayList<>();

// initialize a dynamic array to store int type
ArrayList<Integer> nums = new ArrayList<>();

// common methods are as follows (E represents element type):
// check if the array is empty
boolean isEmpty()

// return the number of elements in the array
int size()

// return the element at index
E get(int index)

// add element e to the end of the array
boolean add(E e)

When solving algorithm problems, these simple methods are usually sufficient, and you should be able to understand them at a glance.

In the basic data structure section, I will guide you through the implementation of an ArrayList in Implementing a Dynamic Array, so you can understand the underlying principles of this common data structure.

4. Doubly Linked List - LinkedList

The ArrayList is implemented with an array underneath, while the LinkedList is implemented with a doubly linked list. The initialization methods are also similar:

// Initialize a doubly linked list to store int type
LinkedList<Integer> nums = new LinkedList<>();

// Initialize a doubly linked list to store String type
LinkedList<String> strings = new LinkedList<>();

// In general algorithm problems, we use the following methods (`E` represents element type):
// Check if the linked list is empty
boolean isEmpty()

// Return the number of elements in the linked list
int size()

// Check if an element o exists in the linked list
boolean contains(Object o)

// Add element e to the end of the linked list
boolean add(E e)

// Add element e to the end of the linked list
void addLast(E e)

// Add element e to the beginning of the linked list
void addFirst(E e)

// Remove the first element from the beginning of the linked list
E removeFirst()

// Remove the last element from the end of the linked list
E removeLast()

These are the simplest methods. Unlike ArrayList, we often use LinkedList for operations on the head and tail elements because the underlying data structure is a linked list, making such operations more efficient. However, the contains method has a time complexity of $O(N)$, as it requires traversing the entire list to check for the presence of an element.

In the foundational data structure section, I will guide you in implementing a LinkedList in Hands-on LinkedList Implementation to understand the underlying principles of this common data structure.

5. Hash Table HashMap

A hash table is a very common data structure used for storing key-value pairs, initialized as follows:

// hashmap mapping integers to strings
HashMap<Integer, String> map = new HashMap<>();

// hashmap mapping strings to arrays
HashMap<String, int[]> map = new HashMap<>();

// In algorithm problems, we will only use the following basic methods (where `K` represents the key type, `V` represents the value type):
// check if the hashmap contains the key
boolean containsKey(Object key)

// get the value corresponding to the key, return null if key doesn't exist
V get(Object key)

// put the key, value pair into the hashmap
V put(K key, V value)

// if the key exists, remove the key and return the corresponding value
V remove(Object key)

6. Hash Set HashSet

Initialization method:

// create a new hash set to store Strings
Set<String> set = new HashSet<>();

// methods we might use in algorithm problems (`E` represents element type):
// add e to the hash set if it does not exist
boolean add(E e)

// check if element o exists in the hash set
boolean contains(Object o)

// remove element o if it exists
boolean remove(Object o)

Once you implement MyHashMap, you will understand that the underlying mechanism of HashSet is actually the same as that of HashMap.

Basic Usage of Java Classes

Let's first talk about generic programming. Generics are a feature provided by Java that allow the implementation of data structures to be decoupled from the data types.

For example, when we use a LinkedList (doubly-linked list), we can freely set the type of elements it contains. However, it is important to note that only classes can be used in generics, not primitive types:

// a doubly linked list of integers
LinkedList<Integer> list1 = new LinkedList<>();
// error, cannot use primitive type int as a generic
LinkedList<int> list2 = new LinkedList<>();

// a doubly linked list of strings
LinkedList<String> list3 = new LinkedList<>();

When implementing our own data structure classes, we also need to use generics so that our data structures can hold any type.

For example, in the article Hand-by-Hand Guide to Implementing LinkedList, the MyLinkedList class uses a generic type E. When you create a new instance, whatever type you pass in will become the type for E:

public class MyLinkedList<E> {

    // add element to the end of the linked list
    public void addLast(E e) {
        // ...
    }
}

// usage:
MyLinkedList<Integer> list1 = new MyLinkedList<>();
MyLinkedList<String> list2 = new MyLinkedList<>();

Of course, some special data structures have requirements for the types of data they store. For example, the TreeMap data structure uses a BST (Binary Search Tree) to store key-value pairs. Therefore, TreeMap requires that the keys inserted into it must be "comparable", meaning that for any two keys, it must be possible to determine which one is greater or smaller.

In Java, you can add extends to a generic variable to specify certain characteristics of the generic type:

// MyTreeMap accepts two generics K and V, where K must implement the Comparable interface
// that is, it must implement the compareTo method so that comparisons can be made
public class MyTreeMap<K extends Comparable<K>, V> {
    public V put(K key, V val) {
        // ...
    }
}

// usage:
MyTreeMap<Integer, Integer> map1 = new MyTreeMap<>();
MyTreeMap<String, Integer> map2 = new MyTreeMap<>();

The Comparable is an interface provided by the Java standard library, implemented as follows:

public interface Comparable<T> {
    public int compareTo(T o);
}

So K extends Comparable<K> means that the generic type K implements this interface, which means the type K has the compareTo method. This allows two K type data to be compared.

Additionally, let's clarify Java interfaces to avoid confusion for some readers. Sometimes we see the following syntax:

Queue<String> q = new LinkedList<>();
List<String> list = new LinkedList<>();

In practice, the newly created object is of type LinkedList, but why do we use Queue and List types to receive it? This is because Queue and List are interface types in the Java standard library:

public interface Queue<E> extends Collection<E> {
    boolean offer(E e);
    E poll();
    E peek();
    // there are several other methods...
}

public interface List<E> extends Collection<E> {
    // several methods...
}

An interface is a collection of methods. As long as a class declares that it implements all the methods in the interface using the implements keyword, the type of this interface can be used to receive instances of this class.

Specifically, the standard library provides the LinkedList class, which implements all the methods in the List interface:

// Deque is a subinterface of Queue, which includes all methods of the Queue interface, so implementing Deque is equivalent to implementing the Queue interface
// There are several other interfaces, omitted here
public class LinkedList<E> implements List<E>, Deque<E> {
    // ...

    // Several methods declared in the Queue interface will be implemented
    boolean offer(E e) {...}
    E poll() {...}
    E peek() {...}
    // ...

    // Several methods of the List interface will also be implemented
    // ...
}

Therefore, you can use the List interface to accept the LinkedList type, and similarly, use the Queue interface.

Of course, there are many in-depth design methods and principles related to interfaces and inheritance in programming languages. If you are interested, you can research and learn more on your own. Since our current focus is on data structures and algorithms, mastering these fundamental concepts is sufficient for you to understand the Java algorithm code I write.