Data Structures Hacks
Jupyter Notebook on data structures hacks
Definitions and Details
In object-oriented programming, a class is a blueprint or template for creating objects that share common properties and behaviors. It defines the properties and methods that an object of that class can have. In this article, we will explore the details of a class, including access modifiers, constructors, modifiers/setters, getters, and more, based on the College Board and AP exam standards.
Access Modifiers
Access modifiers are keywords that determine the accessibility of a class, its members, and its methods. There are four access modifiers in Java: public, protected, private, and package-private (default).
Public: A public class or member is accessible from any other class in any package.
Protected: A protected class or member is accessible within its own package or by a subclass in a different package.
Private: A private class or member is accessible only within the same class.
Package-Private: A package-private class or member is accessible only within its own package.
Constructors
A constructor is a special method that is called when an object of a class is created. It is used to initialize the object's properties or set up its environment. A constructor has the same name as the class and no return type. It can have parameters or no parameters.
Modifiers/Setters
Modifiers or setters are methods used to modify or set the value of an object's properties. They are typically used to ensure data encapsulation and data integrity. Modifiers can be public, private, protected, or package-private, and they can have any return type.
Getters
Getters are methods used to retrieve the value of an object's properties. They are used to access private or protected properties of an object. Getters should be public and have a return type that matches the type of the property they are getting.
Here's an example of a class that incorporates access modifiers, constructors, modifiers/setters, and getters:
public class Student {
private String name;
private int id;
public Student(String name, int id) {
this.name = name;
this.id = id;
}
public void setName(String name) {
this.name = name;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public int getId() {
return id;
}
}
In this example, the class is named "Student." It has two private properties: name and id. The class has one constructor that takes two parameters: name and id. It also has two modifier methods: setName and setId, and two getter methods: getName and getId.
public class Node<T> {
private T value;
private Node<T> next;
public Node(T value) {
this.value = value;
this.next = null;
}
public T getValue() {
return this.value;
}
public Node<T> getNext() {
return this.next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
public class LinkedList<T> {
private Node<T> head;
public LinkedList() {
this.head = null;
}
public void add(T value) {
Node<T> newNode = new Node<>(value);
if (head == null) {
head = newNode;
} else {
Node<T> current = head;
while (current.getNext() != null) {
current = current.getNext();
}
current.setNext(newNode);
}
}
public void remove(T value) {
if (head == null) {
return;
}
if (head.getValue().equals(value)) {
head = head.getNext();
return;
}
Node<T> current = head;
while (current.getNext() != null) {
if (current.getNext().getValue().equals(value)) {
current.setNext(current.getNext().getNext());
return;
}
current = current.getNext();
}
}
public void print() {
Node<T> current = head;
while (current != null) {
System.out.print(current.getValue() + " ");
current = current.getNext();
}
System.out.println();
}
}
public class Queue<T> {
private LinkedList<T> list;
public Queue() {
this.list = new LinkedList<>();
}
public void enqueue(T value) {
list.add(value);
}
public T dequeue() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
T value = list.getValue();
list.remove(value);
return value;
}
public boolean isEmpty() {
return list == null || list.getValue() == null;
}
}
/* This is wrapper class...
Objective would be to push more functionality into this Class to enforce consistent definition
*/
public abstract class Generics {
public final String masterType = "Generic";
private String type; // extender should define their data type
// generic enumerated interface
public interface KeyTypes {
String name();
}
protected abstract KeyTypes getKey(); // this method helps force usage of KeyTypes
// getter
public String getMasterType() {
return masterType;
}
// getter
public String getType() {
return type;
}
// setter
public void setType(String type) {
this.type = type;
}
// this method is used to establish key order
public abstract String toString();
// static print method used by extended classes
public static void print(Generics[] objs) {
// print 'Object' properties
System.out.println(objs.getClass() + " " + objs.length);
// print 'Generics' properties
if (objs.length > 0) {
Generics obj = objs[0]; // Look at properties of 1st element
System.out.println(
obj.getMasterType() + ": " +
obj.getType() +
" listed by " +
obj.getKey());
}
// print "Generics: Objects'
for(Object o : objs) // observe that type is Opaque
System.out.println(o);
System.out.println();
}
}
public class Alphabet extends Generics {
// Class data
public static KeyTypes key = KeyType.title; // static initializer
public static void setOrder(KeyTypes key) {Alphabet.key = key;}
public enum KeyType implements KeyTypes {title, letter}
private static final int size = 26; // constant used in data initialization
// Instance data
private final char letter;
/*
* single letter object
*/
public Alphabet(char letter)
{
this.setType("Alphabet");
this.letter = letter;
}
/* 'Generics' requires getKey to help enforce KeyTypes usage */
@Override
protected KeyTypes getKey() { return Alphabet.key; }
/* 'Generics' requires toString override
* toString provides data based off of Static Key setting
*/
@Override
public String toString()
{
String output="";
if (KeyType.letter.equals(this.getKey())) {
output += this.letter;
} else {
output += super.getType() + ": " + this.letter;
}
return output;
}
// Test data initializer for upper case Alphabet
public static Alphabet[] alphabetData()
{
Alphabet[] alphabet = new Alphabet[Alphabet.size];
for (int i = 0; i < Alphabet.size; i++)
{
alphabet[i] = new Alphabet( (char)('A' + i) );
}
return alphabet;
}
/*
* main to test Animal class
*/
public static void main(String[] args)
{
// Inheritance Hierarchy
Alphabet[] objs = alphabetData();
// print with title
Alphabet.setOrder(KeyType.title);
Alphabet.print(objs);
// print letter only
Alphabet.setOrder(KeyType.letter);
Alphabet.print(objs);
}
}
Alphabet.main(null);
public class Cupcake extends Generics {
// Class data
public static KeyTypes key = KeyType.title; // static initializer
public static void setOrder(KeyTypes key) {Cupcake.key = key;}
public enum KeyType implements KeyTypes {title, flavor, frosting, sprinkles}
// Instance data
private final String frosting;
private final int sprinkles;
private final String flavor;
// Constructor
Cupcake(String frosting, int sprinkles, String flavor)
{
this.setType("Cupcake");
this.frosting = frosting;
this.sprinkles = sprinkles;
this.flavor = flavor;
}
/* 'Generics' requires getKey to help enforce KeyTypes usage */
@Override
protected KeyTypes getKey() { return Cupcake.key; }
/* 'Generics' requires toString override
* toString provides data based off of Static Key setting
*/
@Override
public String toString() {
String output="";
if (KeyType.flavor.equals(this.getKey())) {
output += this.flavor;
} else if (KeyType.frosting.equals(this.getKey())) {
output += this.frosting;
} else if (KeyType.sprinkles.equals(this.getKey())) {
output += "00" + this.sprinkles;
output = output.substring(output.length() - 2);
} else {
output = super.getType() + ": " + this.flavor + ", " + this.frosting + ", " + this.sprinkles;
}
return output;
}
// Test data initializer
public static Cupcake[] cupcakes() {
return new Cupcake[]{
new Cupcake("Red", 4, "Red Velvet"),
new Cupcake("Orange", 5, "Orange"),
new Cupcake("Yellow", 6, "Lemon"),
new Cupcake("Green", 7, "Apple"),
new Cupcake("Blue", 8, "Blueberry"),
new Cupcake("Purple", 9, "Blackberry"),
new Cupcake("Pink", 10, "Strawberry"),
new Cupcake("Tan", 11, "Vanilla"),
new Cupcake("Brown", 12, "Chocolate"),
};
}
public static void main(String[] args)
{
// Inheritance Hierarchy
Cupcake[] objs = cupcakes();
// print with title
Cupcake.setOrder(KeyType.title);
Cupcake.print(objs);
// print flavor only
Cupcake.setOrder(KeyType.flavor);
Cupcake.print(objs);
}
}
Cupcake.main(null);
public class Stage extends Generics {
// Class data
public static KeyTypes key = KeyType.name; // static initializer
public static void setOrder(KeyTypes key) { Stage.key = key; }
public enum KeyType implements KeyTypes { name, difficulty, question }
// Instance data
private final String name;
private final int difficulty;
private final String question;
// Constructor
public Stage(String name, int difficulty, String question) {
this.setType("Stage");
this.name = name;
this.difficulty = difficulty;
this.question = question;
}
/* 'Generics' requires getKey to help enforce KeyTypes usage */
@Override
protected KeyTypes getKey() { return Stage.key; }
/* 'Generics' requires toString override
* toString provides data based off of Static Key setting
*/
@Override
public String toString() {
String output = "";
if (KeyType.name.equals(this.getKey())) {
output += this.name;
} else if (KeyType.difficulty.equals(this.getKey())) {
output += "Difficulty: " + this.difficulty;
} else if (KeyType.question.equals(this.getKey())) {
output += "Question: " + this.question;
} else {
output = super.getType() + ": " + this.name + ", Difficulty: " + this.difficulty + ", Question: " + this.question;
}
return output;
}
// Test data initializer
public static Stage[] stages() {
return new Stage[]{
new Stage("Jungle Jump", 1, "What data structure uses a LIFO (last in, first out) approach?"),
new Stage("Coconut Climb", 2, "What data structure is made up of a series of nodes, each containing data and a reference to the next node?"),
new Stage("Vine Swing", 3, "What data structure has a hierarchical structure with a root, branches, and leaves?"),
new Stage("Banana Bounce", 4, "What data structure is made up of nodes and edges that connect the nodes?"),
new Stage("Mango Maze", 5, "What data structure is a collection of elements of the same type, accessed by an index or a subscript?"),
new Stage("Papaya Peak", 6, "What data structure uses a hash function to map keys to values, allowing for efficient lookup and insertion?"),
new Stage("Durian Dive", 7, "What data structure is a binary tree with the property that the value of each node is greater than or equal to its children?"),
new Stage("Guava Glide", 8, "What algorithm sorts a list by repeatedly swapping adjacent elements that are in the wrong order?"),
new Stage("Passionfruit Plunge", 9, "What algorithm searches for an element in a sorted list by repeatedly dividing the search interval in half?"),
new Stage("Dragonfruit Dash", 10, "What technique solves a problem by breaking it down into smaller subproblems of the same type?"),
};
}
public static void main(String[] args) {
// Inheritance Hierarchy
Stage[] objs = stages();
// print with title
Stage.setOrder(KeyType.name);
Generics.print(objs);
// print difficulty only
Stage.setOrder(KeyType.difficulty);
Generics.print(objs);
// print question only
Stage.setOrder(KeyType.question);
Generics.print(objs);
}
}
Stage.main(null);