Generics Types and Collections
Reviewing generics and other data structures
Hacks
College Board Video
- Classes: templates used to create object variables which can handle all sorts of user-defined methods and attributes
- Attributes: Class specific variables that are (in most cases) different for every object instantiated
- Methods: Class specific methods that often take advantage of the class' attributes or given parameters
- Static: Special modifier that allows the given attribute/method to be accessed without having to create an object. Note that a static attribute will be the same for all object instances of a class.
- Access modifiers: changes how code outside of a given class can access the elements in the class
- Public: any outside code can access the given attribute/method by directly calling it
- Protected: only code that is either inside the class itself or is in a class that inherits from the specific class can directly access the attribute/method
- Private: only code that is inside the class itself can directly access the attribute/method
- Note - Classes can also have access modifiers, although giving a top-level class anything other than public would render it useless. Only giving nested classes (classes inside other classes) such modifiers (private, protected) would still give them some use.
- Constructurs: called when a new object variable is created, usually used to instantiate all of its specific attributes, but can also be used for other things
- Getters: public method used for outside code to access private attributes
- Setters: public method used for outside code to change private attributes
- Inheritance: Classes can inherit attributes and methods from other classes by extending from them
- super(): used to access methods from a parent class
import java.util.Iterator;
public class LinkedList<T> {
private T data;
private LinkedList<T> prevNode, nextNode;
// Create new node with T data and reference to previous LinkedList<T> node
public LinkedList(T data, LinkedList<T> node) {
setData(data);
setPrevNode(node);
setNextNode(null);
}
// Create new node using copy
public LinkedList(LinkedList<T> node) {
setData(node.data);
setPrevNode(node.prevNode);
setNextNode(node.nextNode);
}
// Getters
public T getData() {
return this.data;
}
public LinkedList<T> getPrev() {
return this.prevNode;
}
public LinkedList<T> getNext() {
return this.nextNode;
}
// Setters
public void setData(T data) {
this.data = data;
}
public void setPrevNode(LinkedList<T> node) {
this.prevNode = node;
}
public void setNextNode(LinkedList<T> node) {
this.nextNode = node;
}
}
/**
* Queue Iterator
*
* 1. "has a" current reference in Queue
* 2. supports iterable required methods for next that returns a generic T Object
*/
class QueueIterator<T> implements Iterator<T> {
LinkedList<T> current; // current element in iteration
// QueueIterator is pointed to the head of the list for iteration
public QueueIterator(LinkedList<T> head) {
current = head;
}
// hasNext informs if next element exists
public boolean hasNext() {
return current != null;
}
// next returns data object and advances to next position in queue
public T next() {
T data = current.getData();
current = current.getNext();
return data;
}
}
/**
* Queue: custom implementation
* @author John Mortensen
*
* 1. Uses custom LinkedList of Generic type T
* 2. Implements Iterable
* 3. "has a" LinkedList for head and tail
*/
public class Queue<T> implements Iterable<T> {
LinkedList<T> head = null, tail = null;
/**
* Add a new object at the end of the Queue,
*
* @param data, is the data to be inserted in the Queue.
*/
public void add(T data) {
// add new object to end of Queue
LinkedList<T> tail = new LinkedList<>(data, null);
if (this.head == null) // initial condition
this.head = this.tail = tail;
else { // nodes in queue
this.tail.setNextNode(tail); // current tail points to new tail
this.tail = tail; // update tail
}
}
/**
* Returns the data of head.
*
* @return data, the dequeued data
*/
public T delete() {
try {
T data = this.peek();
if (this.tail != null) { // initial condition
this.head = this.head.getNext(); // current tail points to new tail
if (this.head != null) {
this.head.setPrevNode(tail);
}
}
return data;
} catch (Exception E) {
return null;
}
}
/**
* Returns the data of head.
*
* @return this.head.getData(), the head data in Queue.
*/
public T peek() {
try {
return this.head.getData();
} catch (Exception E) {
return null;
}
}
public int getLength() {
LinkedList<T> current = this.head;
int counter = 0;
while (current != null) {
counter++;
current = current.getNext();
}
return counter;
}
/**
* Returns the head object.
*
* @return this.head, the head object in Queue.
*/
public LinkedList<T> getHead() {
return this.head;
}
public String toString() {
LinkedList<T> current = this.head;
String result = "(start) -> ";
if (current == null) {
result += "NULL -> ";
}
while (current != null) {
result += current.getData() + " -> ";
current = current.getNext();
}
result += "(end)";
return result;
}
/**
* Returns the tail object.
*
* @return this.tail, the last object in Queue
*/
public LinkedList<T> getTail() {
return this.tail;
}
/**
* Returns the iterator object.
*
* @return this, instance of object
*/
public Iterator<T> iterator() {
return new QueueIterator<>(this.head);
}
}
/**
* Queue Manager
* 1. "has a" Queue
* 2. support management of Queue tasks (aka: titling, adding a list, printing)
*/
class QueueManager<T> {
// queue data
private final String name; // name of queue
private int count = 0; // number of objects in queue
public final Queue<T> queue = new Queue<>(); // queue object
/**
* Queue constructor
* Title with empty queue
*/
public QueueManager(String name) {
this.name = name;
}
/**
* Queue constructor
* Title with series of Arrays of Objects
*/
public QueueManager(String name, T[]... seriesOfObjects) {
this.name = name;
this.addList(seriesOfObjects);
}
/**
* Add a list of objects to queue
*/
public void addList(T[]... seriesOfObjects) { //accepts multiple generic T lists
for (T[] objects: seriesOfObjects)
for (T data : objects) {
this.queue.add(data);
this.count++;
}
}
// Challenge 1
public T delete() {
count--;
return this.queue.delete();
}
/**
* Print any array objects from queue
*/
public void printQueue() {
System.out.println(this.name + " count: " + count);
System.out.print(this.name + " data: ");
for (T data : queue)
System.out.print(data + " ");
System.out.println();
}
}
class MergeStack {
public static Queue<Integer> sort(Queue<Integer> q1, Queue<Integer> q2) {
Queue<Integer> q3 = new Queue<Integer>();
while (q1.peek() != null || q2.peek() != null) {
if (q1.peek() == null) {
q3.add(q2.delete());
} else if (q2.peek() == null) {
q3.add(q1.delete());
} else if (q1.peek() <= q2.peek()) {
q3.add(q1.delete());
} else {
q3.add(q2.delete());
}
}
return q3;
}
}
class MergeRandomize<T> {
public Queue<T> randomize(Queue<T> q) {
Queue<T> q2 = new Queue<T>();
ArrayList<T> list = new ArrayList<T>();
LinkedList<T> head = q.getHead();
for (int i = 0; i < q.getLength(); i++) {
list.add(head.getData());
head = head.getNext();
}
while (list.size() != 0) {
// How deep will the program go through the queue
int index = (int)(Math.random() * (list.size()));
q2.add(list.remove(index));
}
return q2;
}
}
class Stack<T> {
LinkedList<T> top = null;
public Stack() {
}
public void push(T data) {
// Could cause problems, not sure???
top = new LinkedList<T>(data, top);
}
public T pop() {
T value = top.getData();
top = top.getPrev();
return value;
}
public T peek() {
return top.getData();
}
public String toString() {
LinkedList<T> current = top;
String result = "(top) -> ";
if (current == null) {
result += "NULL + -> ";
}
while (current != null) {
result += current.getData() + " -> ";
current = current.getPrev();
}
result += "(bottom)";
return result;
}
}
/**
* Driver Class
* Tests queue with string, integers, and mixes of Classes and types
*/
class QueueTester {
public static void main(String[] args)
{
// Create iterable Queue of Words
// Challenge 1
System.out.println("Challenge 1");
String[] words = new String[] { "seven", "slimy", "snakes", "sallying", "slowly", "slithered", "southward"};
QueueManager qWords = new QueueManager("Words", words );
qWords.printQueue();
while (qWords.delete() != null) {
qWords.printQueue();
}
System.out.println("------------------------------------------------------------------------");
System.out.println("Challenge 2");
int[] list1 = {1, 3, 5, 7, 9};
int[] list2 = {2, 4, 6, 8, 10};
Queue<Integer> q1 = new Queue<Integer>();
Queue<Integer> q2 = new Queue<Integer>();
for (int num : list1) {
q1.add(num);
}
for (int num : list2) {
q2.add(num);
}
System.out.print("Queue 1: ");
System.out.println(q1);
System.out.print("Queue 2: ");
System.out.println(q2);
Queue<Integer> mergedQ = MergeStack.sort(q1, q2);
System.out.print("Merged: ");
System.out.println(mergedQ);
System.out.println("------------------------------------------------------------------------");
System.out.println("Challenge 3");
System.out.print("Queue 1: ");
System.out.println(mergedQ);
MergeRandomize randomizer = new MergeRandomize();
Queue<Integer> randomizedQ = randomizer.randomize(mergedQ);
System.out.print("Randomized Queue: ");
System.out.println(randomizedQ);
System.out.println("------------------------------------------------------------------------");
System.out.println("Challenge 4");
Stack wordStack = new Stack();
for (String word : words) {
wordStack.push(word);
}
System.out.println(wordStack);
System.out.println("------------------------------------------------------------------------");
System.out.println("Challenge 5");
Stack team = new Stack();
String[] members = {"Bailey", "Don", "Evan", "Nathan", "Rohit", "Jun", "Hetvi", "Iris", "Ellen", "Sahil", "Samuel", "Everitt"};
for (String member : members) {
team.push(member);
}
System.out.println(team);
team.pop();
team.pop();
team.pop();
System.out.println(team);
}
}
QueueTester.main(null);