Java & Data Structures Review Notes

Notes on Time Complexity and Algorithms

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n)
Selection Sort = O(n^2) consistently swaps biggest and smallest elements and then ignores them
Insertion Sort = O(n^2) creates new list and moves through all elements in array, placing them in new array correctly
Merge Sort = O(n log n)
Linear Search = O(n)
Binary Search = O(log n) starts at beginning and end, computes mid and compares to key => remodulates bounds
Hash table best search = O(1)
Hash table worst search = O(n)
Linked list search = O(n)

More on Sorting Algorithms

Bubble sort O(n^2) passes through an array multiple times, swapping out of order elements until they are sorted
Merge sort O(n log n) divides the array into two halves and applies merge sort on each half recursively
Quick sort O(n log n) selects an element, called the pivot, and splits at that element; recursively calls on each split. Worst case is O(n^2) if essentially the ends are always selected.
Heap sort O(n log n) uses a binary heap (tree), adding all of the elements to a heap and then removing the largest elements successively to obtain a sorted list.
Bucket O(n+t) where t is the number of buckets and radix sorts O(dn) where d is the max number of radix positions are efficient for sorting integers.
Searching through a binary tree is O(log n), similarly with insertion and deletion. All worse cases are O(n)
Note in a BST, nodes of a subtree on the left are strictly less than the base and nodes on the right are strictly greater than the base. This allows for greater searching and insertion efficiency.
Hashing allows for searching in O(1) time by implementing a map or a set to search, insert, or delete an element in O(1) time. The hash function maps some key to a index called a hash value.
A typical hash function coverts a search key to an integer value called a hash code, then compresses the hash code into an index to the hash table.
A map can be efficiently implemented using hashing and a hash set can be implemented using a hash map.

General Language Comments

Java compiles to JVM byte code which is then executed by the architecture-independent virtual machine
Java is a pass by value language
Objects are passed by a copy of the reference
In order to have a function change primitives, a wrapper type is needed
For each loops are implemented with iterators, and can only be used when the Object iterated over has an iterator (arrays, ArrayList, etc.)
When passing an array to a method, a copy of the reference to the array is passed
Each class in a source code file is compiled into a .class file For two ifs followed by an else, the dangling else ambiguity states that no matter the indentation, the else statement corresponds for the last unmatched if statement.

System Input

import java.util.Scanner;
Scanner input = new Scanner(System.in);
System.out.print(“Enter a number for radius: “);
double radius = input.nextDouble();
System.out.print(“Enter three numbers: “);
double number1 = input.nextDouble();
double number2 = input.nextDouble();
double number3 = input.nextDouble();
input.next() reads until the next whitespace character, .nextLine() reads until carriage return
\” is used in strings for printing out quote marks, \\ is backslash, etc.

Error Handling

Try block when a method is called that can throw an exception
To throw exception: throw new ArithmeticException(“message”);
After try block, have catch block with an arg of the expected possible exception and code to print error/take other action
For a function that throws an exception, define method() throws ExceptionType1, ExceptionTypeN { … }
Many catch blocks can be used to catch multiple types of exceptions

File IO

java.io.File is the standard object with a constructor that takes a path. Many methods to see if it exists, r/w permissions, length, type, etc.
java.io.PrintWriter(filename) can be used to create a file and write data to a text file
Scanner can be used to read from a file. See below but use Scanner(new File(filename)) instead of Scanner(System.in)
Invoking scanner or print writer may throw IO exceptions so the main method, for example, must declare throws Exception or IOException
Urls can be loaded with the URL object and scanned with the Scanner(url.openString()), for example

Data Types & Useful Objects

int, double, byte, short, long, float, char, boolean
int i, j, k;
int i = 3, j = 2;
String is the commonly used reference type for char arrays
The java.util.Date class constructs a Date object for the current time, has elapsed time, set, and conversions to String/long
The java.util.Random class seeds with current time. Can specify the seed as a long. Methods to get random ints between 0 and a number, a double, bool, float, long, etc.
BigInteger and BigDecimal classes can be used to represent integers or decimal numbers of any size of precision.
Single inheritance: a Java class may inherit directly from only one superclass but can implement many interfaces
super(args) needs to be called in the subclass constructor to build the superclass with arguments
finally blocks after try/catch blocks are executed under all circumstances, even if there is a return statement prior to reaching the block

Strings

String newString = new String(stringLiteral); such as “Welcome to Luke’s Java notes”
A string can also take an array of characters as the constructor parameter
Note that a string can be initialized from just a string literal without calling new String(stringLiteral)
A String object is immutable. Its contents cannot be changed.
str1.equals(str2) should be used to compare strings
java.lang.String has methods length, charAt(index), and concat(String), which returns a new string that concats this with s1
substring returns a specific range of characters: str.substring(ind0, ind1)
.matches is a very powerful string parsing method, such as “Java is fun”, “Java is cool”, “Java is powerful” all return true for .matches(“Java.*”);
.split splits the string into an array of strings delimited by punctuation marks
The Character class contains a char and has operations such as toUpperCase

Arrays

double[] numbers = new double[SIZE];
double[] numbers = {val1, val2, …, valk};
for each loop: for(double u : numbers) { … }
For passing to a method, a variable number of arguments of the same type can be passed to a method and treated as an array.
public static void printMax(double… numbers) => printMax(new double[]{1,2,3});
java.util.Arrays gives useful methods for common array operations such as sorting and searching
java.util.Arrrays.sort(numbers) or sort(numbers, rangeLow, rangeHigh)
java.util.Arrays.binarySearch(list, key)
Two dimensional arrays: elementType[][] array;
array = new int[5][5]; or array = new int[5][]; if the size of each sub array is not known
Set it with array[0] = new int[3]; and so on
Passing and returning two-dimensional arrays is very easy:
public static int[][] myArrayMethod(int[][] arrray) { … }

Multithreading and Parallel Programming

Tasks are objects. To create a task, have a class that implements Runnable with a constructor and a method public void run()
To execute a task on a thread, create a Thread thread = new Thread(task) and call thread.start();
thread.join() waits for execution to finish, and thread.sleep will wait for a given number of milliseconds
thread.yield() causes the thread to pause temporarily allowing other threads to finish
A method can be declared as synchronized to prevent more than one thread from accessing it simultaneously. Good for avoid critical regions in the code that can’t have multiple access.
Pools for threads such as ForkJoinPools are useful for forking and then joining tasks that need to be executed in parallel.

OO Classes and Inheritance

Constructors can be overloaded, no return type, use same name as the object they are describing
ClassName object = new ClassName();
for member variables, the default value of un-init Strings is null, all primitives are 0
Object-typed variables are really reference variables to the object which is created with the new command
A static variable is shared by all objects of the class. A static method cannot access instance members of the class.
static methods can be called without creating an instance of the class.
static int numberOfObjects = 0; static int getObjects() { return numberOfObjects; }
It is good practice to encapsulate member variables with get/set public methods
Arrays of objects can be defined by: Circle[] circleArray = new Circle[10]; Note that this just creates an array of reference variables that must be initialized with a for loop calling circleArray[i] = new Circle();
Use @Override notation to avoid mistakes in naming/args for a function that is intended to have its implementation overwritten Subclass notation is class newClass extends SuperClass { … }
Dynamic binding means that the first implementation of an overwritten function is called.
myObject instaneof Subclass checks against a reference object’s true type
All classes are automatically derived from the base Object class, with methods such as toString
ArrayList<E> can be used to store a list of objects. Has methods such as add, length, clear, remove, set, etc.
ArrayList<String> myList = new ArrayList<String>();
protected is private but extends access to subclasses
final for a class indicates that a class is final and cannot be a parent class (cannot be extended)
A final method cannot be overridden by subclasses since its implementation is final

Abstract Classes and Interfaces

abstract keyword is used to declare an abstract class, which can be extended but not used as a base class
abstract methods in an abstract class define methods which must be overwritten, unless a subclass is abstract (similar to virtual void in C++)
A subclass can be abstract even if its superclass is concrete An interface is a class-like construct that contains only constants and abstract methods.
Since there are only two possibilities, it is not necessary to include this information. For example:
public static final int K = 1; == int K = 1;
public abstract void func(); == void func();
Use the implements keyword for a class after extends to show which interfaces a class is derived from
The comparable interface defines compareTo<E>, such as public class Integer extends Number implements Comparable<Integer>
Interfaces v. abstract classes: a class can implement multiple interfaces but it can only extend one superclass

Generics

Generics let you parameterize types. Generic types must be reference types; you cannot replace a generic type with a primitive type.
Defining generics: public class myGeneric<E> { … using E as a reference type }
Generic methods can be defined: public static <E> void myFunc(E[] list)
Invoked as class.<refType>myFunc(args), but refType can be omitted if it can be easily resolved (such as list of ints vs doubles etc)
Using objects like GenericStack without a type parameter (passing <Object>) is called a raw type and helps for compatibility with earlier versions of Java.
extends keywords can be used within the <> in order to provide pseudo type checking on the generic type. This is called a bounded generic type, such as GenericMatrix<E extends Number> { … }

Data Structures Objects

Collections: define the common operations for lists, vectors, stacks, queues, priority queues, and sets.
Set: stores a group of non duplicate elements; List: stores an ordered collection of elements; Queues: stores objects that are processed as first-in first-out
Each collection has an iterator that can be used to traverse all of the elements in the collection
ArrayList is an implementation of List that stores elements in an array, which is dynamically created.
Use an Arraylist if random access is needed. If access only at the beginning or end is needed, it is faster and easier to use a linked list
Vector is a synchronized array list that can be used safely across threads without data corruption.
Stack has push, pop, peek, etc. and a way to search for an object
For Queues, offer inserts an element into the queue, and poll, remove, peek, element are accessors for the head of the queue. poll and peek simply return null if there is no element at the start of the queue
A set is essentially a list that contains no duplicate elements, useful particularly for storing indices into another data structure such as a map. The types of sets are HashSet, LinkedHashSet, and TreeSet.
The load factor of a hash set measures how full the set is allowed to be before its capacity is increased
Linked hash set has an imposed order; it maintains the order in which the elements were added
A map is a container object that stores a collection of key/value pairs. It enables fast retrieval, deletion, and updating of the pair through the key.
The hash map class if efficient for locating a value, inserting an entry, and deleting an entry. Linked hash map extends hash map with an ordered retrieval corresponding to insertion ordering, or the order in which they were last accessed, from least recently to most recently (access order).
The tree map is efficient for traversing the keys in a sorted order

Syntax & Operations

final is used to declare constant valued, or immutable objects final datatype CONSTNAME = value;
^ is the exclusive or operator for boolean expressions
y = (expression) ? (val for true) : (val for false)
Common sentinel value for ending input is 0
break breaks out of a loop while continue breaks to the end of an iteration
Math.pow(a, b) computes a^b for doubles. Many other functions exist in the math library such as
Math.sqrt(a), Math.random() gives a random number between 0.0 and 1.0, and Math.sin, etc.