Arrays/Java

Notes

Array-based Data Structures

Arrays: main array-based data containers

ArrayList: dynamically resizable, implements List interface

List of Abstract Data Types:

• Lists (link-based or array-based)
• Maps/Dictionaries
• 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

Abstract Data Types

The Abstract Data Types page has more information about what kind of data structures implement what kind of interfaces.

• List interface Java API docs: http://docs.oracle.com/javase/7/docs/api/java/util/List.html
• ArrayList class Java API 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.

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

Arrays/Java/CaesarCipher

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)

Python-like dynamic array list

Main article: Arrays/Java/PythonList

Defining a data structure that uses a dynamically resized array to store underlying data, and works similar to a Python list:

https://git.charlesreid1.com/cs/java/src/master/arrays/python-list/PythonList.java

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 Goodrich et al Data Structures in Java Chapter 3

Question R-3.2) Write Java method that repeatedly selects and removes a random entry from an array until the array holds no more entries.

See Arrays/Java/Repeatedly Remove for an algorithm to repeatedly select and remove entries from an array using the Fisher-Yates shuffle.

See Arrays/Java/FisherYates for more info about the Fisher Yates shuffle method.

Two questions, both related, about finding values in an array:

Question C-3.17) A is an array of size n>=2 containing integers from 1 to n-1, inclusive, one of which is repeated. Describe an algorithm for finding the integer in A that is repeated.

Question C-3.18) Let B be an array of size n>=6 containing integers from 1 to n-5, inclusive. Five of the integers are repeated. Describe an algorithm for finding the five integers in B that are repeated.

See Arrays/Java/Finding Duplicates

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?

The book makes the following statement:

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

But the book does not explain anything about where the binomial equivalency came from.

Any Kind You'd Like

Which would you prefer: a quadratic, linearithmic, or linear algorithm?

It depends. What's the scaling constant, what's the problem size, what are the tradeoffs?

Linear time reversal of string

Turn it into a char array

Make an empty new char array, and copy one char at a time.

Or, do it in place: swap (i) with (n-1-i)