Test 2 Flashcards
generic type
a class or interface type that has another type as a parameter. Here are some examples:
A list in which all elements are the same type. The element type is the parameter.
An ordered pair in which both elements are the same type. The element type is the parameter.
A key-value pair in which all the keys are the same type and all the values are the same type. There are two parameters, one for the key type and another for the value type.
A comparable type in which two objects of the same type can be compared to determine which is larger.
formal type parameter
For each declaration, the item in braces is the formal type parameter.
actual type argument
An instantiation of a generic type, in which the actual type argument is supplied for the formal type parameter, is called a parameterized type. Here are some instantiations of the types listed above.
MyList
MyList
Important: The actual type must be a class or interface type. You cannot instantiate with primitive types.
code shows how OrderedPair can be instantiated and used.
OrderedPair<>Stringparents = new OrderedPair<>String("mom", "dad");
// Could initialize as parents = new OrderedPair<>("mom", "dad");
String helen = parents.getX();
Notice that the constructor name does show the actual parameter type even though the constructor definition does not. An alternative allows you to use the parameter with just the diamond notation, <>, without specifying the actual parameter type.Parameterized types as method arguments and return types
public double slope(OrderedPair<>Double p1, OrderedPair<>Double p2) {
double numerator = p1.getY() - p2.getY();
double denominator = p1.getX() - p2.getX();
return numerator/denominator;
}
You must specify the type parameter (that is, use a parameterized type) for these kinds of arguments and return types.
interface types is Comparable
public int compareTo(T x)
The compareTo() method should impose a full ordering on all instances of T (allowing any list of instances of T to be sorted). It returns a negative number if this object is less than x, positive if this is greater than x, and 0 if this object and x are the same.
ex. public class StoreProduct implements Comparable<>E{
Wildcards
If you want a generic type argument that is independent of a particular parameterized, you can use a type wildcard, which is indicated by <>?. The following method, which belongs to a class named Driver, prints the data members of its actual argument in reverse order.
public void printReverse(OrderedPair<> ?p) {
Object x = p.getX();
Object y = p.getY();
Generic restrictions
You cannot create a parameterized type from a primitive. You must use a class or interface type. You cannot declare a static member variable of a generic type with the type parameter. You cannot create arrays of parameterized types.
The following section and the code below show how to deal with the first restriction on primitives.
You cannot declare a static member of a generic type because the static member is a class variable. The type would be different for each parameterized type instantiation of the generic type.
You cannot create arrays of parameterized types, but you can work around that restriction. This code illustrates how.
// OrderedPair badPoint; // ILLEGAL
OrderedPair goodPoint; // This is the primitive workaround
// OrderedPair [] badArray // ILLEGAL // = new OrderedPair[30] badArray; // ILLEGAL
Object[] goodArray = new Object[30]; // This is the array workaround
goodArray[0] = new OrderedPair("hello", "goodbye");
Wrapper classes
Each primitive type has an associated wrapper class, whose name reflects the type. For example, Boolean wraps a boolean value, Integer wraps an int, and Double wraps a double.
You can construct a wrapper class type object by using a primitive or by using a string representation of the primitive. The following are examples.
Double dbl = new Double(1.23);
Each wrapper class has methods that returns the value of the primitive equivalent. The following code assigns 567 to both x and y. Note that getInteger() is a static method in the Integer class.
Integer xObject = new Integer("567");
int x = xObject.intValue()
int y = Integer.getInteger("567");
boxing
The Java compiler automatically converts primitives to their corresponding wrapper class types as needed. This conversion is called boxing (automatic = auto boxing).
ex.
// Calling code
ArrayList<>Integer measures = new ArrayList<>();
measures.add(12);
measures.add(7);
measures.add(30);
int sum = measures.get(0) + measures.get(1); // sum is 19
if (measures.contains(7)) {
// You can also add without boxing
measures.add(2, new Integer(22));
printList(measures);
}collection
A collection is an object that holds multiple objects at the same time. The objects in a collection are called elements. The Java API contains several top-level collection interfaces:
Collection
Set: cannot contain duplicate elements.
List: a sequence of elements.
Queue: holds elements awaiting processing.
Map: elements have key-value pairs. The key provides a look-up for its corresponding value. Duplicate keys are not allowed.
When you create a collection object, you should indicate the type of element the collection has.
Elements belonging to collections are objects. They cannot be primitives. In order to have an ArrayList of ints, you need to use the Integer wrapper type instead. The following statement is an example.
ArrayList score = new ArrayList() Can also declare as List (more flexible)
Java collections framework
-Set
HashSet. The most commonly used because it is the most efficient. Hashing computes a unique value for each element of the set, so any particular element is quick to look up even if the set is very large.
TreeSet. Imposes an order on the elements.
LinkedHashSet. A cross between HashSet and TreeSet.
-List
ArrayList. The most commonly used, this list type has indexes to access elements.
LinkedList. List elements are not indexed, so access to elements is not efficient.
-Map
HashMap. The most commonly used, each element (which is a key-value pair) has a hash to determine its location. Hashing makes this an efficient data structure.
TreeMap. Helpful if the keys should be stored in a particular order.
LinkedHashMap. Can change the order of storage of elements depending on when they were last accessed.
-Queue
LinkedList. The most commonly used, elements are removed from the front of the queue (the LinkedList) and added to the rear.
PriorityQueue. Elements are ordered so that the smallest element is always at the front. Removing the smallest element re-orders the rest of the queue to bring the smallest remaining element to the front.
Iterating through collections with for-each loops
Iterating through a collection (or any aggregate data type) means going through the collection, processing one element at a time. When you simply want to examine each element without changing it, the easiest way to iterate through an entire collection is to use a for-each loop.
for (element-type element-name : collection-name) {
do something with element-name
}
iterator
Whenever possible, you should use for-each loops to iterate through collections. That does not work if you want to change the collection while you are going along. In that case, you can use an iterator, which is an object capable of iterating through a collection. An iterator starts at the first element, then can go to each next element in succession.
Iterator is an interface in java.util. It declares three important methods: boolean hasNext() next() void remove()- Removes from the collection the last element returned by the iterator.
The Collection interface declares an iterator method, which is defined in all of the concrete implementing classes:
Iterator iterator()
The return type for this method is an interface type. The actual runtime type of the object returned does not matter. What is critical is that object supports all of the Iterator methods. The object starts its iteration at the beginning of the collection, going to each successive element with each next() message
Collection<>String words = new HashSet<>(); // Add some Strings to word. ... int twoCharacterWords = 0; Iterator<>String iter = words.iterator();
list
A list is a collection whose elements come in a distinct order. In other words, there is a first element, a second element, and so on. (It is easy to define a list recursively. A list is either empty or it consists of an element plus another list.)
Two kinds of lists
Array list: a list in which the elements are stored in contiguous memory (an array).
Linked list: a list in which the information in each element includes the location of the subsequent element.
Choosing list types: The type of list that you choose depends on what kind of operations you want to perform on it. If you want to be able to insert or delete items efficiently, a linked list is likely the way to go. If you want efficient access to elements via their indexes, an array list is probably the better choice.
array list
An array list is a list in which the underlying data structure that holds the elements is an array. The Java class for implementing an array list is the generic type ArrayList<>E, where the parameter E is the type of list elements. The list size is the number of list elements. The length of the underlying array is the capacity of the array list, and it is always at least as large as the list size. The capacity automatically increases if needed as the list size grows.
Vectors:
Java also has a Vector class for implementing array lists. The Vector class and the ArrayList class provide the same kinds of operations, but Vectors are much less efficient than ArrayLists.
You should use Vectors only when your program has multiple threads that need to access the list elements. (Vectors are “thread safe.”)
LinkedLists
Linked lists are lists in which the information in each element includes the location of the next element. The LinkedList class is particularly convenient for creating special list types such as stacks and queues.
LinkedList implements List, so it defines all of the List methods. It also defines methods to get, remove and insert an element at the beginning and end of the list:
Array lists, which are based on arrays, must shift elements in order to do insertions or deletions. Such shifts are not necessary for linked lists. In order to insert or delete an element in a certain position, it is simply necessary to change the location information in the elements immediately before and after the one to be inserted or deleted.
Doubly linked lists:
Java’s LinkedList class is “doubly-linked.” That means information in each element includes the location of the element that follows it as well as the location of the element that precedes it.
Sets
Lists hold their elements in sequences – list elements have indexes. Sets are groups of elements in which there is no sequencing. Furthermore, sets cannot contain duplicate elements.
Set is an interface in Java that extends Collection. The table below lists some of the Set methods.
Method Description void add(E x) Adds x to the set if it is not already in the set. void remove(E x) Removes x from the set if it is an element of the set. boolean contains(E x) true if x is an element of the set. boolean isEmpty() true if the set contains no elements. int size() Number of elements in the set.
For sets, you need to use for-each loops for simple traversals. But those loops are inappropriate if you want to change the elements in the collection. For that task, you need a special object called an iterator. Iterators can go through all the elements of a collection, enabling you to access them one-by-one.
There are two classes that implement Set
HashSet and TreeSet. Since they offer the same basic methods, which of those two you choose to use depends on the performance required. HashSets are more efficient. If you want to sort the elements, however, use a TreeSet.
ConcurrentModificationException
That is not so nice. If you try to remove and element from the underlying set (or any collection) inside the for-each loop, you get a ConcurrentModificationException. Using an iterator avoids that issue.
buffer
With respect to computer programming, the term buffer means a place in main memory to store varying amounts of data. There are StringBuffers, for example, for storing and manipulating string data. Consider this problem:
Maintain statistics on test scores for students in a class.
If the maximum possible class size is 200, then this array can be a buffer to store the scores.
int[] test = new int[200];
And to keep track of the number of test scores, you can do this:
int size = 0;
sentinel value
(Alternatively, you could have a sentinel value such as -1 to mark the end of the list of test scores. The sentinel value would have to be a number that could not possibly be a legitimate score.)
What is a custom list?
A list is an ordered collection of elements. Common list operations include:
add – adds a new element to the list
remove – removes an element from the list (and returns it)
get – returns a list element (from a particular position or satisfying a particular condition)
contains – determines if a particular item belongs to the list
size – number of elements in the list
ArrayList and LinkedList will do. But sometimes you need a custom list to do things such as:
Restrict list elements (such as no null elements or no negative numeric elements) and throw custom exceptions on attempts to add illegal elements.
Support special operations not common to all lists.
Progam efficiently for particular operations (such as add to front).
Create self organizing lists (such as move-to-front lists and move-ahead-one lists, where the order of list items changes dynamically according to the most recent search).
The custom array list requires three attributes:
An array to hold the elements. The type must be E[], where E is the type parameter for the generic list class.
An int for the list size (the actual number of list elements).
An int for the capacity (number of array elements).
