Lucas V. Schuermann
March 2015
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)
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.
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.
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
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 fileScanner
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
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 interfacessuper(args)
needs to be called in the subclass constructor to build the superclass with argumentsfinally
blocks after try
/catch
blocks are executed under all circumstances, even if there is a return
statement prior to reaching the block
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 stringsjava.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
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 searchingjava.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) { … }
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 millisecondsthread.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.
Constructors can be overloaded, no return type, use same name as the object they are describingClassName 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[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 subclassesfinal
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
keyword is used to declare an abstract class, which can be extended but not used as a base classabstract
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 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> { … }
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 collectionArrayList
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 listVector
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
final
is used to declare constant valued, or immutable objects final datatype CONSTNAME = value;
^
is the exclusive or operator for boolean expressionsy = (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 iterationMath.pow(a, b)
computes a^b for doubles. Many other functions exist in the math library such asMath.sqrt(a)
, Math.random()
gives a random number between 0.0 and 1.0, and Math.sin
, etc.
Last updated Jan 27, 2016