Arrays/Java
From charlesreid1
Contents
Notes
Arraybased Data Structures
Arrays: main arraybased data containers
ArrayList: dynamically resizable, implements List interface
List of Abstract Data Types:
 Lists (linkbased or arraybased)
 Maps/Dictionaries
 Sets
Java also implements:
 Stacks
 Queues
 Deques
These can be arraybased 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, noninclusive
 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)
Pythonlike dynamic array list
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/pythonlist/PythonList.java
Notes from Sedgewick and Wayne Java Programming
Memory usage estimates and principles
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 R3.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 FisherYates 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 C3.17) A is an array of size n>=2 containing integers from 1 to n1, inclusive, one of which is repeated. Describe an algorithm for finding the integer in A that is repeated.
Question C3.18) Let B be an array of size n>=6 containing integers from 1 to n5, 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:
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 (n1i)
Flags
Data Structures Part of Computer Science Notes
This is the staging ground for computer science notes as part of the 2017 CS Study Plan.
Classes of data structures: Abstract Data Types Arraybased and Linkbased memory management: ArrayLists and Linked Lists Algorithmic Analysis of Data Structures: Algorithmic Analysis of Data Structures Advanced data structures: Advanced Data Structures

Arrays Part of Computer Science Notes
Series on Data Structures Python: Arrays/Python · Arrays/Python/Sizeof · Arrays/Python/AppendCost · Arrays/Python/CaesarCipher · Arrays/Python/CompactArrays · Arrays/Python/DynamicArray Java: Arrays/Java · Arrays/Java/CaesarCipher · Arrays/Java/FisherYates · Arrays/Java/PythonList · Arrays/Java/Repeatedly_Remove Categories: Category:Python Arrays

Stacks and Queues Part of Computer Science Notes
Series on Data Structures
Stacks and Queues: Python StacksQueues/Python · StacksQueues/Python/ArrayStack · StacksQueues/Python/ArrayQueue · StacksQueues/Python/ArrayDeque StacksQueues/Python/LinkedStack
Stacks and Queues: Java StacksQueues/Java · StacksQueues/Java/ArrayStack · StacksQueues/Java/ArrayQueue · StacksQueues/Java/ArrayQueueFS · StacksQueues/Java/ArrayDeque StacksQueues/Java/LinkedStack · StacksQueues/Java/LinkedQueue · StacksQueues/Java/LinkedDeque
Applications Postfix_Expressions#Stacks · StacksQueues/Subsets · StacksQueues/Subsets/Java

Priority Queues and Heaps Part of Computer Science Notes
Series on Data Structures
Java: Priority Queues/Java · Priority Queues/ADT · Priority Queues/Sorted · Priority Queues/Unsorted Performance: Priority Queues/Timing and Performance Applications: Maximum Oriented Priority Queue · Priority Queues/Stack
Priority Queues/Heap · Priority Queues/Java · Priority Queues/Comparators

Linked List Part of Computer Science Notes
Series on Data Structures Java: Linked Lists/Java · Linked Lists/Java/Single · Linked Lists/Java/Double · Linked Lists/Java/Circular Performance: Linked Lists/Java/Timing · Linked Lists/Java/Reverse Python: Linked Lists/Python · Linked Lists/Python/Single

Trees Part of Computer Science Notes
Series on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree · Trees/ArrayTree · SimpleTree
Tree Traversal Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder InOrder traversal: Binary Trees/Inorder BreadthFirst Search: BFS BreadthFirst Traversal: BFT DepthFirst Search: DFS DepthFirst Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP · Tree Traversal/Traversal Method Template Tree operations: Trees/Operations Performance · Trees/Removal
Tree Applications Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree · Binary Trees/ArrayBinTree Binary Trees/Cheat Sheet · Binary Trees/OOP · Binary Trees/Implementation Notes

Search Trees Part of Computer Science Notes
Series on Data Structures
Binary Search Trees · Balanced Search Trees Trees/OOP · Search Trees/OOP · Tree Traversal/OOP · Binary Trees/Inorder
(Note that heaps are also valuesorting trees with minimums at the top. See Template:PriorityQueuesFlag and Priority Queues.)

Maps and Dictionaries Part of Computer Science Notes
Series on Data Structures
Maps/Dictionaries Maps · Maps/ADT · Maps in Java · Maps/OOP · Maps/Operations and Performance Map implementations: Maps/AbstractMap · Maps/UnsortedArrayMap · Maps/SortedArrayMap Dictionary implementations: Dictionaries/LinkedDict · Dictionaries/ArrayDict
Hashes Hash Maps/OOP · Hash Maps/Operations and Performance Hash Maps/Dynamic Resizing · Hash Maps/Collision Handling with Chaining Hash functions: Hash Functions · Hash Functions/Cyclic Permutation Hash map implementations: Hash Maps/AbstractHashMap · Hash Maps/ChainedHashMap
Skip Lists · Java/ConcurrentSkipList · Java implementations: SkipList
Sets Sets · Sets/ADT · Sets in Java · Sets/OOP · Multisets
