Arrays/Java

Notes

Array-based Data Structures

Arrays: main array-based data containers

ArrayList: dynamically resizable, implements List interface

List of Java/Abstract Data Types:

• Lists
• Maps
• Sets

Java also implements:

• Stacks
• Queues
• Deques

These can be array-based but are covered elsewhere: see StacksQueues/Java.

List interface:

• add(e) : adds e to the end of the list
• add(i,e) : adds e to the list at index i
• remove(e) : removes first instance of element e from list
• remove(i) : removes item i from list

convenience methods:

• isEmpty() : returns true if the list is empty
• size() : get the size of a list

This is hard to keep straight, between Java's three notations for strings, arrays, and lists, plus Python's... but here goes:

Java ArrayList<T>:

• add() / remove()
• size()
• resizable array under the hood

List interface docs: http://docs.oracle.com/javase/7/docs/api/java/util/List.html

ArrayList class docs: http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html

Notes from Goodrich et al Data Structures in Java Chapter 4

Basics of Arrays

Building an array to hold a basic object - a GameEntry representing a high score entry in a game.

Link: https://charlesreid1.com:3000/cs/java/src/master/arrays/GameEntry.java

The default array element will be null, so an empty array of GameEntry objects contains null pointers

Java stores references to addresses in memory, so these objects are like remote controls.

Sorting an array

Simple sort method: insertion sort (not the fastest, but simple)

Indexing, algorithm implementation, illustration of god practice

Java Array utilities

Array class static methods:

• equals(A, B)
• fill(A,x)
• copyOf(A, n)
• copyOfRange(A,s,t)
• toString(A)
• sort(A)
• binarySearch(A,x)

Random numbers:

• nextInt() - next random integer somewhere in the range of all possible integers
• nextInt(n) - between 0 and n, non-inclusive
• nextDouble() - uniform, between 0 and 1
• nextGaussian() - gaussian random, mean 0 std 1

Easy way to get a copy of an array:

• A.clone()

Caesar Cipher

Converting between Strings, chars, and ints:

• Caesar cipher and basic cryptography
• String objects have a toCharArray method to turn String into char[]
• Strings have constructor to turn char[] into String: new String(char_arr)
• Simplest and most general way is probably to use 2 Strings, fwd and reverse, and lookup action
• Char/int math, though, allows us to do it just as fast, and with mod math right there.

Implementing a Caesar Cipher class:

• What are the inputs? Constructor taking a key
• What are the private variables? encryption string, decryption string
• Encrypt takes String parameter, return transform(message, encryption string)
• Decrypt takes String parameter, return transform(ciphertext, decryption string)
• Transform takes orig, alphabet, does char ops on it.

Random numbers

Random number generation methods:

• nextBoolean()
• nextDouble()
• nextInt()
• nextInt(n)
• setSeed(s)

Tic Tac Toe

Illustrates good design principles:

• Design of program, choosing implementation details and data structure, public/private methods, making it functional
• Design was centered around a choice of a 2D array for a board
• Interface is just, put(row,col)

Notes from Sedgewick and Wayne Java Programming

Memory usage estimates and principles

Java/Memory

Primitive tyeps:

• boolean - 1 byte
• byte - 1 byte
• char - 2 bytes
• int - 4 bytes
• float - 4 bytes
• long - 8 bytes
• double - 8 bytes

An integer has 2^32 different values, with 32 bits or 4 bytes (since there are 8 bits per byte)

Objects:

• Object overhead is 16 bytes of object overhead for each object
• References to objects typically use 8 bytes of memory.
• Data types can contain references to objects. The data type automatically incurs 16 bytes overhead for each object instance, plus 8 more bytes for each object's reference to another object.

Arrays:

• Arrays are implemented in Java as objects, with two instance variables - a pointer to the memory location of the first array element, and the length of the array.
• Primitive types - arrays use 24 bytes of header information, plus n times number of bytes to store each element

Example: int array

• int = 4 bytes
• int[] = 4n + 24 ~ 4n bytes

Example: double array 1D

• double = 8 bytes
• double[] = 8n + 24 ~ 8n bytes
• double[][] = 8n^2 + 32n + 24 ~ 8n^2

Questions

Questions from Sedgewick

ThreeSum

What is the runtime of the following code fragment?

int count = 0;
for(int i = 0; i < n; i++ ) {
  for( int j = i+1; i < n; j++) { 
    for( int k=j+1; j<n; k++) { 
      count++;
    }
  }
}

O(n^3), yes, but what else?

$ \binom{n,3} = \dfrac{n(n-1)(n-2)}{6} $