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

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.

Tic Tac Toe:

• Design of program, choosing implementation details and data structure, providing functional wrappers, public/private methods around the data structure