CSCI 211 Test 1 Flashcards
variables declared as “primitive types” ? represent information and are stored on the ?
directly; runtime stack
runtime stack
belongs to the program; keeps track of return addresses for method calls and variables that are local to a method (including method parameters)
variables declared as class types are ? to objects
“references”
objects are stored on the
runtime heap
the reference to an object is on the
runtime stack
pass by value
when calling a method, copies of the argument values are given to the method parameters
pass by references
a copy is given to the method parameters, but the copy of the reference points to the same object as the original (gives you the ability to make changes to the object)
object
a programming construct that consists of a state and set of behaviors; an instance of a class
an object’s state is described by
data members (e.g. int count, boolean full)
class
describes a set of objects of the same type (data members, methods); a blueprint that says how to build an object of that type; contains actual code
interface
a set of methods that are provided by a unit of code; java lets us declare an interface as a set of methods (doesn’t require an implementation)
Java allows us to group a collection of classes into a ?
package; just put “package packagename;” at the top of all files in the package
when application code wants to use a package
import packagename.*; (matches all classes in the package)
API (Application Programming Interface)
the set of public methods supported by the classes in the package (their interfaces) is an example
public
visible to the application
private
only accessible by class
(no access modifier)
default = package access only
protected
visible to child classes and the package
collection
a container that holds of group of objects, often called elements
the Java Collection Framework supports several types of collection:
List, Set, Maps
List
an ordered collection; order can be determined by insertion order or sometimes by the compareTo() method of the Comparable Interface or a Comparator object that’s passed to a sort() method of the collection
Set
usually no guarantee that order will be preserved; null elements are allowed; NO duplicates are allowed (they will be ignored if entered)
Maps
a collection of key-value pairs (each key is associated with one value object - typically use key to look up a value)
List Interface provides methods such as
void add(E, e); void add(int index, E e);
ArrayList vs LinkedList
ArrayList uses an array, which is quick for “random access,” but slow for insertion and deletion
LinkedList uses a “chain” of “Nodes,” each containing an element; slow for finding elements (“random access”) because it has to traverse the list from top to bottom, but quick for insertion and deletion
Stack
a specialist list; elements are added and removed from the top of the stack (behaves like a stack of dinner places); an example of a LIFO data structure
Stack methods
push(E element) - add element to top of stack E pop() - remove the topmost element from the stack, then return element E peek() - returns a reference to the topmost element
how to create an instance of the Stack class
Stack< Integer > s = new Stack<>();
Queue
elements are added to the tail (end) of the queue and removed from the head (beginning), like a bank teller line; FIFO data structure
Queue methods
add(E element) - add element to end of queue (aka enqueue); throws exception on failure boolean offer(E element) - add to end of queue; returns false on failure E remove() - remove element from head of queue (aka dequeue)
how to create an instance of the Queue class
Queue< Integer > q = new LinkedQueue<>();
Deque
can add or remove elements from either end
Deque methods
addFirst(E element)
addLast(E element)
E removeFirst()
E removeLast()
PriorityQueue
order of elements is data dependent; elements are removed in order of priority, as determined by a compareTo() method
We can make our own stack using Linked Lists:
a Node class will proved a reference to the next Node in the linked list, and also a reference to the data being stored (“payload”); the Node class could be an “inner class” - defined inside of another class; also, we should use generics to allow the same stack class to handle a variety of element types
Test Driven Development
write Unit tests for all the cases you can think of at the same time as the code, then write just enough code to pass the test; tests should expose bugs, then you can use the debugger with the tests to diagnose the cause of the bugs; each test should be small and self-contained so they are each run separately
how to write a test that should throw an exception
@Test(expected = NoSuchElementException.class)
void testName() {
//test stuff
}how to write a test
@Test
void testName {
//stuff
}how to write a Stack class
class Stack {
class Node {
T data;
Node next;
}
Node top;
public push(T element) {
Node n = new Node();
n.data = element;
n.next = top;
top = n;
}
public T pop() {
if(top==null) {
throw new NoSuchElementException();
}
T retval = top.data;
top = top.next;
return retval;
}
}Iterators
for Collection classes, we can use a special loop syntax:
MyCollection collection = getCollection();
for(Element e : collection) {
//do something with e
S.o.pl(e);
}
the loop body executes once for each element where the loop variable e takes on each value in the collection in succession
with Java collections, an exception is thrown if the collection is modified (however, the Iterator interface has a remove() method that may be implemented if needed)
to implement an Iterator
in the Collection: class Foo implements Iterable must implement the Iterable interface public Interator iterator();
in the class that implements Iterator: public class FooIterator implements Iterator
public boolean hasNext()
public T next()
growth functions
we can estimate the behavior (execution time/memory consumption) of a program (or algorithm) by counting the number of operations (should be important to the performance) performed for a given problem size (the number of elements in a collection, denoted by n); we can relate n (the problem size) to the number of operations using a growth function (e.g. comparisons = 5n+2)
Big O Notation
a way of characterizing the asymptotic behavior of the growth function for an algorithm; throw away all constants, except for exponents; keep only the term that grows most quickly with increasing n
Big O Notation examples:
a) 5n+2
b) log(n)+n
c) n^2 + 400
d) 17
e) n * log(n)
a) O(n) “linear time”
b) O(n) “linear time”
c) O(n^2) “quadratic time”
d) O(1) “constant time”
e) O(n^2) “quadratic time”
f) O(nlogn) (best sorting algorithms are nlogn)
Getting a growth function from code examples:
a) for(i=0; i < n; i++) {
// do something
}
b) for(i=0; i < 12; i++) {
//do something
}
c) for(i=0; i < n; i++) {
for(j=0; j < n; j++) {
//do something
}
}a) O(n) because the loop body executes n times
b) O(1) because the loop body executes 12 times no matter what
c) O(n^2) because the outer loop runs n times and the inner loop runs n times
Logarithms
log base 2 of x tells how many times we can (recursively) divide x into two halves (e.g. binary search)
public void push ( T element )
Node n = new Node(); n.data = element; n.next = top; top = n;
public T pop ( )
if ( top == null ) {
throw new NoSuchElementException();
}
T retval = top.data;
top = top.next;
return retval;class Node
T data;
Node next;
public void add ( E e )
Node n = new Node;
n.element = e;
if ( front == null ) {
front = back = n;
}
else {
back.next = n;
back = n;
}public E remove ( )
if ( front == null ) {
throw new NoSuchElementException();
}
E retval = front.element;
front = front.next;
return retval;Use an iterator to traverse a list and remove any occurrence of the number 5
Iterator < Integer > iter = list.iterator();
while ( iter.hasNext()) {
Integer i = iter.next();
if(i == 5) {
iter.remove;
}
}Write code that prints all the elements in a Bag containing Items
Bag < Item > theBag = foo.getRelevantItems();
for ( Item i : theBag) {
S.o.pl(i);
}
public boolean hasNext ( )
if ( next == null) {
return false;
}
else {
return true;
}public E next ( )
if ( hasNext() == false ) {
return null;
}
E retval = next.element;
next = next.next;
return retval;
