# 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)

### 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.

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 `if`s 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 `int`s 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;` or `array = new int[];` if the size of each sub array is not known
Set it with `array = new int;` and so on
Passing and returning two-dimensional arrays is very easy:
`public static int[][] myArrayMethod(int[][] arrray) { … }`

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 `ForkJoinPool`s 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 `String`s 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;` 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 `Queue`s, `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.

Last updated January 27, 2016