Java Collections and Data Structures Flashcards
what are “ad hoc” classes
before java 2 , java provide Dictionary,Vector,Stack and Properties classes.
What is Collection
Collection is an interface that extends Iterable and extended by List , Queue and Set Interfaces.
Collection package
java.util
Collection hierarchy
https://www.tutorialspoint.com/java/images/hierarchy-of-collection-framework.jpg
Or tutorialspoint website in Collections Framework section ( if website not found ).
Some Collections methods
.sort(),shuffle(),max(),min()
Some List interface methods
add(val)/add(i,val)
addAll(i,collection)/addAll(collection),
remove(i),
set(i,val),
get(i)
What is Queue
Queue interface implements FIFO
What is the objective of Queue ?
it’s holding elements before processing them.After the process, the element is deleted from queue and we pass to next one.
Classes that implements Queue
LinkedList
ArrayDeque
PriorityQueue
Interfaces that extends Queue
Deque
BlockingQueue
BlockingDeque
Some Queue methods
.add()
.peek() : give head (1st element ) of queue
.remove()
.size()
What is Map
Map is an interface which has a unique key object and their values
Map and Collection
Map doesn t implements Collection !!!!!!!!!!!!!!!!!
Some Map Exception
*NullPointerException : is thrown when we try to use a null object ( which is not allowed in map )
*ClassCastException : is thrown when an object is incompatible with the map elements type.
Classes that implements Map
HashMap
LinkedHashMap
TreeMap
Interface that implements Map
SortedMap
some Map methods
put(key,val)
remove(key)
getOrDefault(key,defaultValue)
containsKey(key)
containsValue(val)
keySet()
entrySet()
values()
size()
SortedMap Interface
SortedMap extends Map interface , it ensures that entries are maintained in ascending key order.
Some SortedMap Exception
*NoSuchElementException : when no items in the invoking map
*Others exceptions of Map : look above
Class that implements SortedMap
TreeMap
SortedMap Disadvantage
every time we add an item it does resort so it affects performance negatively
Why we use Set Interface ?
Set interface can’t contains duplicates
Some Set methods
contains()
add()
clear()
remove()
size()
isEmpty()
SortedSet
it’s like SortedMap in Map
LinkedHashMap vs TreeMap
LinkedHashSet vs TreeSet
LinkedHashMap maintain in which items are inserted in Map but TreeMap sort entries based on sorting key in ascending order
=> Same goes for LinkedHashSet vs TreeSet
Data Structure
Enumeration ( it’s not a data structure , but important in the context of DS )
BitSet
Stack
Vector
Dictionary
HashTable
Properties
What is Enumeration ?
Enumeration is an interface that is used to retrieve successive elements from DS
Some Enumeration methods
elements()
keys()
hasMoreElements()
nextElement()
What is BitSet ?
BitSet class used for set of Boolean values
What is Vector ?
Vector is a class similar to array except it can increase and decrease its size dynamically depending on how much elements
What is Stack ?
Stack is a class that implements LIFO
What is Dictionary ?
Dictionary is an abstract class for mapping keys to values
What is HashTable ?
HashTable is a class that extends Dictionary.
It is a collection of key value pairs (Entry<K,V>). Each key value pair known as entry
What is Properties ?
Properties is a subclass of HashTable , its key and value type is String
What is Iterator ?
Iterator is an object that implement Iterator() or ListIterator() interface , to pass through elements in collections (or remove elements)
Example of Iterator use
List<String> al = new ArrayList<>();</String>
// Use iterator to display contents of al
Iterator<String> itr = al.iterator();
while(itr.hasNext()) {
Object element = itr.next();
System.out.print(element + " ");
}
What is Comparator ?
Comparator is an interface that defines what sorted order means
Comparator methods
Compare(obj1,obj1)
equals()
What is Comparable ?
Comparable is an interface used for to compare and sort collections objects
Comparable methods
obj.compareTo(obj1)
equals
What is Tree ?
Tree is hierarchichal (non-linear) data structure consisting of nodes connected by edges
What is Key concepts of Tree ?
*node:basic unit of tree that holds values
*root:the higher node in tree , having no parent
*parent: have other nodes connected to it (children).
*child: node under parent
*leaf:a node with no children
*edge: link between two nodes
*subtree:any node and its descendants
*depth: number of edges from root to a specific node
*height: the longest path from root to leaf
What are common types of Tree ? and what is their defs ?
*Binary Tree :all node have at most two children(left and right)
*Binary Search Tree (BST):A binary tree where the left child is smaller and the right one is larger than the parent
*AVL Tree: A balanced binary search tree where the heights of two child subtrees of any node differ at most by one.
*Heap:heap has two concepts :
=> Heap memory: it’s where object are dynamically allocated , and it is managed by JVM
=> Heap Data Structure : it’s a binary tree structure for retrieving min or max element,it is used in algorithms like priority queues
Where we use Tree ?
We use tree in scenarios like data representation(file systems) , search algorithms …
What is Graph ?
Graph is data structure that consists on connecting vertices ( nodes ) with edges.
What are types of Graph ?
Directed graph (unidirectional) : graph with a directed edges , have only one sense.
Undirected graph (bidirectional) : graph wih undirected edges , have two senses
Weighted graph : are graps which have weights on their edges.
What are the two common approaches to represent a Graph ?
*Adjacency 2D :Consist of a 2D array which has nodes/vertices values on their line and column , if their is a connection we put 1 , otherwise 0.
*Adjacency List : consist of a linkedList where each one correspand to a vertex and contains list of all other vertices that is connected to.
Big O notation
How code slows in terms of data size.
*Time Complexity : Describes how the runtime of an algorithm increases with the size of the input.
*Space Complexity :Describes how the memory usage of an algorithm grows with the size of the input.
Common Big O Notations
O(1):Constant time
O(log(n)):Logarithimic time
O(n):Linear time
O(nlog(n)):Linearithmic time
O(n^2):Quadratic time
O(2^n):Exponential time
O(n!):Factoriel time
Bubble Sort
iterate through array comparing between each 2 elements until replacing max at last , repeating until all is sorted
____________________________________
Time complexity : O(n^2)
Space complexity : O(1)
Stable : Yes
Selection Sort
Iterating through array until finding min element and place it first ,repeat until all is sorted ( or search max instead of min )
_____________________________________
Time Complexity: O(n^2)
Space Complexity:O(1)
Stable:Yes
Insertion Sort
We start with comparing first two elements , after that we have a sub array already sorted (of length = 2) , now ,we reached third element , we compare it to the whole precedent array , we sort all elements ( we have array with length 3 sorted ) we continue until the whole array is sorted.
__________________________________
Time Complexity: O(n^2)
Space Complexity:O(1)
Stable:Yes
Merge Sort
Consist on dividing array by 2 until we can’t divide anymore after that we compare left to right and sort then merge sub arrays until it give us the sorted array
=>Merge Sort is a “divide-and-conquer” algorithm.
_____________________________________
Time complexity : O(nlog(n))
Space complexity : O(n)
Stable : Yes
_____________________________________
Code key points :
*left<right
two functions: mergeSort(…)2 then merge(…)
Quick Sort
We use pivot, we choose a random position of pivot , and we use two index (i=-1 and j=0), we iterate through array if arr[j]<arr[pivot] we increment i and swap i and j values , and then increment j , else we ignore things and increment j, once j=pivot we swap arr[pivot] with arr[i+1].after that all values on left small than pivot value and the opposite for the ones on right.
After that we divide array to sub-arrays and we choose a random pivot position again and when all sorted we gather array partitions. this is done recursively .
=> Quick Sort use “divide and conquer” algorithm
_________________________________________
Time Complexity: for average : O(nlog(n)), worst case O(n^2)
Space Complexity:O(log(n))
Stable : No
_________________________________________
Code key points:
*low<high
two functions : partition(return pivot) then quickSort()2
Heap Sort
Consist of heapify array , array will have properties as a heap ( array become like binary tree ) then we sort array by having it each parent value bigger than its children, the last step is to swap root node (max val) with last array value ( like remove it from tree ) and again heapify array then do things recursively until the array is sorted
_________________________________________________
Time Complexity: O(nlog(n))
Space Complexity: O(1)
Stable:No
__________________________________________________
Code key points:
we code on heapSort() method + we add heapify() inside it(called 2 times inside 2 loops separated)
Java’s Built-in Sorting
int[] arr = {5, 3, 8, 4, 2};
Arrays.sort(arr); // Sorts primitive arrays
_______________________________________________
List<Integer> list = Arrays.asList(5, 3, 8, 4, 2);
Collections.sort(list); // Sorts collections</Integer>
Merge Sort vs Quick Sort
*Merge Sort have always always O(nlogn) time complexity but Quick Sort can have O(n^2) because merge sort consist on split and merge element which don t depend on order of element like choosing a bad pivot.
*Quick Sort does not require additional space for merging, making it more space-efficient than Merge Sort, which needs O(n) extra space
Traversal in binary tree
Preorder traversal; root->left->right
Inorder traversal: left -> root -> right
Postorder traversal: left -> right -> root
Depth First Search (DFS)
a search alogrithm that consist on traversing a tree or a graph data structure
=> to traverse from Start to reach End we first pick a route we traverse until “dead end” / “previously visited node”, we go back (Backtrack) to last node that has unvisited adjacent neighbors nodes and repeat the previous process until we reach the end
_______________________________________________
We use Recursion (better) or Stack here.
_______________________________________________
Agorithm:
*We mark the start node as visited
*for all adjacent of current node : We visit all unvisited adjacent neighbors and mark them as visited ( with recursion)
*When all adjacent nodes have been visited , backtrack to the previous node
Breadth First Search (BFS)
a search algorithm that consist on traversing a tree or a graph data structure
This is done one “level” at a time (BFS) instead of one “branch” at a time (DFS) !!!!!!!!!!!!!!
____________________________________________________
we use Queue here.
____________________________________________________
Algorithm:
*Start by marking root or starting node as visited
*Add root node to queue
*while queue still not empty : remove front node from it and add all its unvisited neighbors and mark then as visited one by one
* repeat until all nodes are visited or queue is Empty
Use of BFS
Better for finding shortest path for unweighted graph
Use of DFS
Better for finding cycles and connected components
Graph implementation
numVertices and adjList/adjMatrix as attributes , with a param constructor to fill attributes then addEdge()(+removeEdge() for matrix representation) method and printGraph().
Binary Search
A search algorithm to find index of a target value on a Sorted array. Half the array is eliminated on each step
=> Binary Search is efficient on large Dataset
=> Time Complexity : O(log(n))
Interpolation Search
pos=low+((target-arr[low])/(arr[high]-arr[low]))*(high-low)
_____________________________________________________
if (arr[pos] == target ) : we return pos
if (arr[pos] < target) : low=pos+1;
if (arr[pos] > target): high=pos-1;
______________________________________________________
Time Complexity : O(log(log(n))) , worst case : O(n)
Space Complexity : O(1)
What is ArrayList ?
also dynamic array, is an array with a resizable capacity, it store elements in a “Contiguous” memeory location.
What is LinkedList (singly)
is a data structure, a chain of nodes , where each Node contains 2 parts , data and a next pointer that contains address to the next node. LinkedList doesn t have an index.
LinkedList have a head ( points on 1st node address ) and the address on the last node is null
What is Doubly LinkedList
It is similar to singly LinkedList , except that it contains on each node 3 parts , it adds prevrious pointer which is the address to the previous node.
It has a head and a tail ( points on last node address ).
The previous of head is null like the next of tail is null
What are ArrayList advantages ?
*Read an element by index with O(1) Time complexity
*Contiguous Memory location
*Easy to insert/delete at the end
What are ArrayList disadvantages ?
*Wastes more memory
*Shifting elements is time consuming O(n)
*Expanding/shrinking an array is time consuming O(n)
ArrayList vs LinkedList
*LinkedList always insert/delete elements with O(1) time complexity
*ArrayList have index which read element in a O(1) time complexity not like LinkedList ( O(n) )
What is recursion ?
Recursion is when a thing is defined in terms of itself
What are recursion benefits ?
*Easy to read/write
*Easy to debug
What are recursion disadvantages ?
*Sometimes Slower
*Sometimes Uses more memory
=> Cause : Call Stack, to keeps track of the order of a lot methods.
What is Call Stack ?
Call Stack is a data structure that keeps track of the order in which our program needs to function ( implements LIFO )
How Hashtable insert its element
key.hashCode()%Capacity is equal to index ;
If two hashes calculated to be on the same value , that’s known as a collision.
What we do during collision (for hashtable) ?
Each of the stored location in Hashtable known as bucket, if a bucket have already an entry ,within the first entry we will add an address to the location of the next entry and keep on adding more if there is more entries on this bucket , this will become as a separate linkedlist (this process is known as Chaining). In this case , if we are searching for a key inside a bucket of more than one entry we will iterate through the linkedlist until we find the wanted key.
The less there is a collision , the more efficient a Hashtable will lookup for a value.
How to reduce the number of collision ?
To reduce number of collision , you can increase the size of Hashtable. But then again Hashtable will use more memory.
=>You should find balance between having a hashtable with less possible collision and memory usage.
ArrayList vs Vector
See document table
HashMap vs HashTable
See document table
HashMap vs HashSet
See document table
