Computer Science Final Review

Default Access Modifier

Variable/class is only available to the current package

Public Access Modifier

Variable/class is visible to all packages

Private Access Modifier

Variable/class is only visible to the class/package that contains it.

Protected

Variable is only accessible by subclasses.

Objects

Have properties (variables) and functions (methods).

Class

A blueprint to make objects.

Constructor

Simplifies the creation of one object by combining it into one method call. Passes parameters. Has no return type. Has the same name as the object.

Copy Constructor

Passes an object as its parameter. Used to copy values of one object to another without using the same address for both objects. Manually copies properties from one object to another.

Getter and Setter Functions are used for…

Objects with private properties.

abstract

Keyword used to define abstract classes and methods

Abstract Classes

Can’t be instantiated directly. They contains abstract methods and concrete methods. Abstract methods must be implemented by its children. Concrete methods are automatically inherited.

extends

Keyword used for classes that extend from the abstract class.

Linked List

Data structure for storing a collection of items. Can be visualized as nodes connected to each other. Goes in one direction, left to right. Stores the location of first and last nodes (head/tail nodes). Can be treated as a stack/queue.

Head

First node

Node Properties in a Linked List

2 Attributes; data and the next node.

Doubly Linked List

Each node keeps track of the next node as well as the previous node.

Tail

Last node

Create a linked list of string objects

LinkedList<String> linkedList = new LinkedList<>();

Add the element “A” onto the linked list via stack

linkedList.push"(“A”); // puts at the start of linked list

Remove an element of the linked list via stack

linkedList.pop();

Print out the linked list

System.out.println(linkedList);

Add the element “A” onto the linked list via queue

linkedList.offer(“A”); // puts at the end of the linked list

Remove an element of the linked list via queue

linkedList.poll();

Add the element “E” at index 4 for linked list

linkedList.add(4, “E”);

Remove the element “G” from linked list

linkedList.remove(“"G”);

Find the index of “F” in a linked list

linkedList.indexOf(“F”);

Peek at the first item in the linked list

linkedList.peekFirst();

Peek at the last item in the linked list

linkedList.peekLast();

Remove the first item in the linked list

linkedLast.removeFirst();

Remove the last item in the linked list

linkedLast.removeLast();

Add “0” to the start of the linkedList

linkedList.addFirst(“0”);

Add “G” to the end of the linkedList

linkedList.addLast(“G”);

Arraylist

Dynamic, their sizes can change.

Create an arraylist of integers

Arraylist<Integer> list = new ArrayList<>();

Add 1 into the arraylist

list.add(1);

Remove 2 from the arraylist

list.remove(2);

Set index 2 of the arraylist to 4

list.set(2, 4);

Get the item at index 3 of an arraylist

list.get(3);

Get the size of the arraylist

list.size();

Stack

LiFo, has push(), pop(), peek(), empty(), search(). Takes O(1) to push and pop.

Create a stack of string objects

Stack<String> stack = new Stack<String>();

Push “Minecraft” into the stack

stack.push(“Minecraft”);

Pop off the stack

stack.pop();

Check if the stack is empty

stack.empty();

Peek at the top most item of the stack

stack.peek();

Search for “DOOM” in the stack

stack.search(“DOOM”);

Create a queue of strings

Queue<String> queue = new LinkedList<String>();

Add “Karen” to the queue

queue.offer(“Karen”);

Remove from the queue

queue.poll();

Find the size of the queue

queue.size();

Check if the queue contains “Harold”

queue.contains(“Harold”);

Check if queue is empty

queue.isEmpty();

Hashtable

Stores key-value pairs. Search, insert, and deleting each takes O(1) time

Chaining

If a new element collides with one in a hashtable, the pre-existing element in the hashtable links to the new element via a linkedlist.

Open Addressing

Linear probing; if a collsion, check for space on the right of the pre-existing element. Keep going until it’s empty.

Double Hashing

Randomly chooses how far to go to check for an empty space when there’s a collision.

Adjacency Matrix

O(1) time complexity, O(V²) space complexity. Has unique nodes along columns and rows. If a 1, edge exists between those nodes.

Adjacency List

O(V) time complexity, O(V + E) space complexity. Uses an array/arraylist of linkedlists. Travel the linked list to identify which nodes are connected to which.

Depth First Search

A search algorithm for traversing a tree/graph data structure. Travels by branches and uses a stack.

Breath First Search

A search algorithm for traversing a tree/graph data structure. Checks one level at a time using a queue.

Time complexity of one for loop

O(n)

Time complexity of double for loop

O(n²)

Binary Search Tree

A tree where each node has at most 2 children. Values are arranged in a certain order. The root is greater than the left child and less than the right child. Remaining structure follows the same pattern.

In Order Tree Traversal

Left-most child, root, right
private void traverseTree(Node root) {
traverseTree(root.left);
System.out.println(root.data);

traverseTree(root.right);

}

Pre Order Tree Traversal

Print as you go left and right; root, left, right
private void traverseTree(Node root) {
System.out.println(root.data);
traverseTree(root.left);

traverseTree(root.right);

}

Post Order Tree Traversal

Print children before parent; Left, right, root
private void traverseTree(Node root) {
traverseTree(root.left);

traverseTree(root.right);

System.out.println(root.data);

}

Queue

FiFo, has offer(), poll(), peek(). O(1) to offer and poll.

Selection Sort Time Complexity

O(n²)

Bubble Sort Time Complexity

O(n²)

Insertion Sort Time Complexity

O(n²)

Merge Sort Time Complexity

O(nlogn)

Quick Sort Time Complexity

O(nlogn)

Insertion Sort

Compare the the value at index 1 to the values on the left. If it’s in the incorrect position, shift values. Then move to index 2. Compare to left. Shift if incorrect, repeat until the end.

Merge Sort

Recursively divides the array into sub arrays. Stop when the size is 1. Using a helper function, it merges the sub arrays in order into the bigger one. It continues merging until it reaches the original aray size and is completely sorted.

Quick Sort

Uses a pivot and finds the final place of that pivot. Compare the pivot to the values in the array. All items to the left are smaller than the pivot and all items to the right are bigger than the pivot. After the pivot is in the right place, partition the array up until the pivot from the left and right sides. Pass the partitions into another recursive step of quick sort.

Bubble Sort

Compares 2 values. Highest value bubbles to the top. Continue until array is sorted.

Selection Sort

Compares 2 values. Smallest number by default is at the start. Find the smallest number and swap with the first position. Continue until array is sorted.