Generic Types and Collections Post
Generic types and collections blog post for AP CSA
Classes and Objects:
- A class is like a "blueprint" for creating objects.
- Class attributes are variables within a class, and class methods are methods within a class.
- Constructors:
- A constructor is essentially a special method that is ran whenever an object of a class is initialized, and is typically used to set initial object attribute values.
- The constructor name has to match the class name.
- All classes have constructors by default. The default constructor does not set any values in the class.
- Access Modifiers:
- Access modifiers control the access level of classes, their attributes, and their methods.
- Class Access Modifiers:
- public - class is accessible by any other class.
- default - class is only accessible by any classes in the same package.
- Attribute, Method, and Constructor Access Modifiers:
- public - Code is accessible for all classes.
- private - Code is only accessible within the class.
- default - Code is only accessible in the same package.
- protected - Code is accessible in the same package and any subclasses.
- Modifiers:
- Non-access modifiers provide different kinds of functionality regarding the behavior of classes, attributes, and methods.
- Class Non-Access Modifiers:
- final - Class cannot be inherited by other classes.
- abstract - Objects cannot be created from the class, as it can only be accessed from a subclass that inherits it.
- Attribute, Method, and Constructor Non-Access Modifier:
- final - Code cannot be modified.
- static - Code belongs to the class instead of an object.
- abstract (methods) - Code can only be located in an abstract class. Body of code is provided in the subclass.
- transient - Code is skipped over when the object containing it is serialized.
- synchronized (methods) - Code is accessed one thread at a time.
- volatile (attributes) - The value of code is not cached thread-locally, but is stored in the main memory.
- Getters and Setters:
- Getters and Setters are typically used to provide access to private variables.
- Encapsulation is basically the process of keeping sensitive data hidden or "private" from users.
- get and set methods are typically public, allowing us to access private variables from outside the class.
- Getters return the variable value, while Setters set the variable value.
- get method:
- private String name;
- public String getName() { return name; }
- set method:
- private String name;
- public void setName(String newName) { this.name = newName; }
Linked List:
- In Java, a LinkedList is very similar to an ArrayList.
- A LinkedList is essentially a collection that can contain multiple variables or objects of the same type.
- Since LinkedList implements the same interface (List) as ArrayList, it has similar methods.
- The main difference between an ArrayList and a LinkedList:
- An ArrayList contains an array that stores items. If new variables are added and the array is not big enough, a new one is created to replace it.
- A LinkedList basically saves items in containers, in which it has a link to the first container, and each container has a link to the next container in order. Whenever a new item is added to the list, it is placed into a new container, which is linked a container already in the list.
- To initialize LinkedList:
- LinkedList
<Type>linkedListName = new LinkedList<>(); - or: LinkedList
<Type>linkedListName = new LinkedList<Type>(); - Notice how the object instantiation of LinkedList does not have a type parameter.
- LinkedList
- LinkedList methods:
- addFirst() - self-explanatory.
- addLast() - self-explanatory.
- removeFirst() - self-explanatory.
- removeLast() - self-explanatory.
- getFirst() - self-explanatory.
- getLast() - self-explanatory.
- A LinkedList is a linear data structure, meaning within in it, each node is connected to the previous and next node. Each node has 3 fundamental fields: prev (address of previous element), next (address of next element), and data (actual data of current element).
- Elements in a LinkedList are not stored sequentially, but rather scattered and connected with links. This means a LinkedList stores 3 values in an element position. Whenever a new element is added to LinkedList, prev and next addresses are changed for some elements.
Queue:
- A queue is a type of collection that implements the First In First Out (FIFO) element ordering system. It is essentially an order list of variables or objects where elements are inserted at the end of the list and elements are deleted at the start of the list.
- Generics in Java allow variable types (e.g. Strings and integers) to be parameters in methods, interfaces, and classes. Generic classes can take variable types as parameters, separated by commas.
- Since Queue is an interface, we need other classes in order to directly implement it (e.g. ArrayDeque, LinkedList, and PriorityQueue).
- To initialize Queue (3 different ways):
- Queue
<Type>queueName = new LinkedList<>(); - or: Queue
<Type>queueName = new LinkedList<Type>(); - Queue
<Type>queueName = new ArrayDeque<>(); - or: Queue
<Type>queueName = new ArrayDeque<Type>(); - Queue
<Type>queueName = new PriorityQueue<>(); - or: Queue
<Type>queueName = new PriorityQueue<Type>(); - Notice how the instantiations of LinkedList, ArrayDeque, and PriorityQueue do not have type parameters.
- Queue
- Important Queue Methods:
- add(element) - Inserts element into queue.
- offer(element) - Inserts element into queue. Returns false if not successful.
- element() - Returns head of queue.
- peek() - Returns head of queue. Returns null if queue is empty.
- remove() - Returns and removes head of queue.
- poll() - Returns and removes head of queue. Returns null if queue is empty. #### Stack: ####
- A stack is a type of collection that implements the Last In First Out (LIFO) element ordering system, where elements are added to the top of the stack and elements are removed from the top of the stack.
- To initialize a stack:
- Stack
<Type>stackName = new Stack<>(); - or: Stack
<Type>stackName = new Stack<Type>(); - Notice how the object instantiation of Stack does not have a type parameter.
- Stack
- Since Stack inherits the Vector class, it has methods and properties similar to that of Vector.
- Important Stack Methods:
- push() - Add element to top of stack.
- pop() - Remove element from top of stack.
- peek() - Return element at the top of the stack.
- search(element) - Return the index/position of the element from the top of the stack.
- empty() - Check whether or not the stack is empty.
import java.util.*;
public class Examples {
private LinkedList<Integer> linkedListName;
private Queue<Integer> queueName;
private Stack<Integer> stackName;
public Examples(int[] array) {
linkedListName = new LinkedList<>();
queueName = new LinkedList<>();
stackName = new Stack<>();
for (int i = 0; i < array.length; i++) {
linkedListName.add(array[i]);
queueName.add(array[i]);
stackName.push(array[i]);
}
}
public void displayExamples() {
System.out.println("LinkedList:");
System.out.println("-----------");
System.out.println("Implementing get method");
for (int i = 0; i < linkedListName.size(); i++) {
if (i == 9) {
System.out.println("index " + i + ": " + linkedListName.get(i));
} else {
System.out.print("index " + i + ": " + linkedListName.get(i) + ", ");
}
}
System.out.println("Implementing set method");
for (int j = 0; j < linkedListName.size()/2; j++) {
int lastIndex = linkedListName.size() - (j + 1);
int temp = linkedListName.get(j);
linkedListName.set(j, lastIndex);
linkedListName.set(lastIndex, temp);
}
for (int element : linkedListName) {
System.out.print(element + " ");
}
System.out.println("");
System.out.println("Implementing remove method");
for (int i = 0; i < linkedListName.size(); i++) {
if (linkedListName.get(i) % 2 != 0) {
linkedListName.remove(i);
}
}
for (int element : linkedListName) {
System.out.print(element + " ");
}
System.out.println("");
System.out.println("");
System.out.println("Queue:");
System.out.println("------");
System.out.println("Removing every element of the queue then adding it again");
for (int i = 0; i < queueName.size(); i++) {
int temp = queueName.remove();
System.out.print(temp + " ");
queueName.add(temp);
}
System.out.println("");
System.out.println("Queue Size: " + queueName.size());
System.out.println("");
System.out.println("Stack:");
System.out.println("------");
System.out.println("Reversing the order of a stack");
String before = "Before: ";
int[] reverseArray = new int[10];
for (int i = 0; i < reverseArray.length; i++) {
int temp = stackName.pop();
before += temp + " ";
reverseArray[i] = temp;
}
System.out.println(before);
String after = "After: ";
for (int j = 0; j < reverseArray.length; j++) {
after += reverseArray[reverseArray.length - (j + 1)] + " ";
stackName.push(reverseArray[j]);
}
System.out.println(after);
}
public static void main(String[] args) {
int[] exampleArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Examples myObj = new Examples(exampleArray);
myObj.displayExamples();
}
}
Examples.main(null);
import java.util.Queue;
import java.lang.Math;
import java.util.ArrayList;
import java.util.Stack;
public class LinkedListPractice {
public void hack1() {
Queue<String> queue1 = new LinkedList<String>();
String[] words = {"seven", "slimy", "snakes", "sallying", "slowly", "slithered", "southward"};
for (String word : words) {
queue1.add(word);
System.out.println(displayData(queue1, true));
}
for (String word: words) {
String head = "";
for (String item : queue1) {
head += item;
break;
}
System.out.println("Dequeued data: " + head);
queue1.remove();
System.out.println(displayData(queue1, false));
}
}
public String displayData(Queue<String> queueName, boolean enqueue) {
if (enqueue) {
String data = "Enqueued data: ";
String head = "";
String items = "";
if (queueName.size() == 0) {
items = null;
} else {
int index = 0;
for (String item : queueName) {
if (index == queueName.size() - 1) {
head += item;
} else {
index++;
}
items += item + " ";
}
}
data += head + "\n" + "Words count: " + queueName.size() + ", data: " + items;
return data;
} else {
String data = "";
String items = "";
if (queueName.size() == 0) {
items = null;
} else {
for (String item : queueName) {
items += item + " ";
}
}
data += "Words count: " + queueName.size() + ", data: " + items;
return data;
}
}
public void hack2() {
Queue<Integer> queue1 = new LinkedList<Integer>();
Queue<Integer> queue2 = new LinkedList<Integer>();
Queue<Integer> mergedQueue = new LinkedList<Integer>();
queue1.add(1);
queue1.add(4);
queue1.add(5);
queue1.add(8);
queue2.add(2);
queue2.add(3);
queue2.add(6);
queue2.add(7);
System.out.println("1st Sorted Queue:");
for (int item : queue1) {
System.out.print(item + " ");
}
System.out.println("");
System.out.println("2nd Sorted Queue:");
for (int item : queue2) {
System.out.print(item + " ");
}
System.out.println("");
while (queue1.size() != 0 || queue2.size() != 0) {
if (queue1.peek() == null) {
mergedQueue.add(queue2.remove());
} else if (queue2.peek() == null) {
mergedQueue.add(queue1.remove());
} else {
if (queue1.peek() <= queue2.peek()) {
mergedQueue.add(queue1.remove());
} else {
mergedQueue.add(queue2.remove());
}
}
}
System.out.println("Sorted Merged Queue:");
for (int item : mergedQueue) {
System.out.print(item + " ");
}
System.out.println("");
}
public void hack3() {
Queue<Integer> queue1 = new LinkedList<Integer>();
queue1.add(1);
queue1.add(2);
queue1.add(3);
queue1.add(4);
queue1.add(5);
queue1.add(6);
queue1.add(7);
queue1.add(8);
System.out.println("Queue before shuffle:");
for (int item : queue1) {
System.out.print(item + " ");
}
int[] tempValues = new int[queue1.size()];
int index = 0;
for (int item : queue1) {
tempValues[index] = item;
index++;
}
int queueIndex = 0;
for (int item : queue1) {
int randIndex = (int) (Math.random() * 7);
int temp = tempValues[randIndex];
tempValues[randIndex] = tempValues[queueIndex];
tempValues[queueIndex] = temp;
queueIndex++;
}
while (queue1.size() != 0) {
queue1.remove();
}
for (int value : tempValues) {
queue1.add(value);
}
System.out.println("");
System.out.println("Queue after shuffle:");
for (int item : queue1) {
System.out.print(item + " ");
}
System.out.println("");
}
public void hack4() {
Queue<Integer> queue1 = new LinkedList<Integer>();
Stack<Integer> stack1 = new Stack<Integer>();
queue1.add(1);
queue1.add(2);
queue1.add(3);
System.out.println("Queue before reverse:");
for (int item : queue1) {
System.out.print(item + " ");
}
System.out.println("");
while (queue1.size() != 0) {
stack1.push(queue1.remove());
}
while (stack1.size() != 0) {
queue1.add(stack1.pop());
}
System.out.println("Queue after reverse:");
for (int item : queue1) {
System.out.print(item + " ");
}
System.out.println("");
}
public static void main(String[] args) {
LinkedListPractice myObj = new LinkedListPractice();
System.out.println("Hack 1:");
System.out.println("-------");
myObj.hack1();
System.out.println("");
System.out.println("Hack 2:");
System.out.println("-------");
myObj.hack2();
System.out.println("");
System.out.println("Hack 3:");
System.out.println("-------");
myObj.hack3();
System.out.println("");
System.out.println("Hack 4:");
System.out.println("-------");
myObj.hack4();
}
}
LinkedListPractice.main(null);