Data structures and Algorithms

This gist contains some useful data structure and algorithm implementations. Note that some of these are not optimized enough for real use cases. The purpose of these snippets are to demonstrate the algorithm. There are better guides and tutorials out there: w3schools, tutorialspoint, geeksforgeeks. Please refer to them for better knowledge. This is just an all in one place cheatsheet.

Data structures

• Stack [see example]
• Queue [see example]
• LinkedList [see example]
• Tree [see example]

Algorithms

• Searching algorithms
  • Linear search [see example]
  • Binary search [see example]
• Sorting algorithms
  • Bubble sort [see example]
  • Selection sort [see example]
  • Insertion sort [see example]
  • Quick sort [see example]
  • Merge sort [see example]
  • Heap sort [see example]
• Miscellaneous
  • Naive String Matching Algorithm [see example]
  • Rabin-Karp Algorithm [see example]

Examples

Stack

	Access	Search	Insertion	Deletion
Best case	O(1)	O(n)	O(1)	O(1)
Worst case	O(1)	O(n)	O(1)	O(1)

Stack<Integer> stack = new Stack<Integer>(10);
// push elements to the stack
stack.push(1);
stack.push(2);
stack.push(3);
// peek the top most element
System.out.println(stack.peek()); // 3
// pop elements from the stack
System.out.println(stack.pop()); // 3
System.out.println(stack.pop()); // 2
System.out.println(stack.pop()); // 1

Classic string reverse problem

String str = "seniru";
Stack<Character> stack = new Stack<Character>(str.length());
// add characters to the aarray one by one
for (Character c : str.toCharArray()) {
    stack.push(c);
}

// reverse the string
while (!stack.isEmpty()) {
    System.out.print(stack.pop()); // urines
}
System.out.println();

Queue

	Access	Search	Insertion	Deletion
Best case	O(1)	O(n)	O(1)	O(1)
Worst case	O(1)	O(n)	O(1)	O(1)

Queue<Integer> queue = new Queue<Integer>(10);
// insert items to the queue
queue.insert(1);
queue.insert(2);
queue.insert(3);
// peek the front of the queue
System.out.println(queue.peek()); // 1
// remove items from the queue
System.out.println(queue.remove()); // 1
System.out.println(queue.remove()); // 2
System.out.println(queue.remove()); // 3

LinkedList

	Access	Search	Insertion	Deletion
Best case	O(1)	O(1)	O(1)	O(1)
Worst case	O(n)	O(n)	O(1)	O(1)

LinkedList<Integer> list = new LinkedList<Integer>();
// inserting items
list.insertFirst(1); // [1]
list.insertFirst(2); // [2, 1]
list.insertLast(3); // [2, 1, 3]
list.insertAt(1, 4); // [2, 4, 1, 3]
System.out.println(list);
// Output: [2, 4, 1, 3]
// accessing and searching
System.out.println(list.indexOf(4)); // 1
System.out.println(list.getNode(1)); // Node[data: 4]
System.out.println(list.get(1)); // 4
System.out.println(list.find(1); // 2
// deleting items
list.deleteAt(1); // [2, 1, 3]
list.deleteFirst(); // [1, 3]
list.deleteLast(); // [1]
System.out.println(list);
// Output: [1]

Tree (Binary Search Tree)

	Access	Search	Insertion	Deletion
Best case	O(log n)	O(log n)	O(log n)	O(log n)
Worst case	O(n)	O(n)	O(n)	O(n)

Tree<Integer, String> s = new Tree<Integer, String>();
// insertion
s.insert(1, "v1");
s.insert(5, "v2");
s.insert(3, "v3");
s.insert(4, "v4");
s.insert(10, "v5");
// transveral
s.inOrder(s.getRoot());
System.out.println();
// Outputs: 1: v1, 3: v3, 4: v4, 5: v2, 10: v5, 

s.preOrder(s.getRoot());
System.out.println();
// Outputs: 1: v1, 5: v2, 3: v3, 4: v4, 10: v5, 

s.postOrder(s.getRoot());
System.out.println();
// Outputs: 4: v4, 3: v3, 10: v5, 5: v2, 1: v1, 

System.out.println(s.find(3)); // 3; v3
System.out.println(s.findRecursive(s.getRoot(), 3)); // 3: v3

// deletion
s.delete(5);
s.inOrder(s.getRoot());
// Outputs: 1: v1, 4: v4, 3: v3, 10: v5, 

Linear Search

	Best case	Worst case
Time	O(1)	O(n)

arr = [1, 2, 42, 50, 5, 10, 16, 69, 520, 100]
print(linear_search(arr, 5)) # 4
print(linear_search(arr, 9999)) # None

Binary Search

	Best case	Worst case
Time	O(1)	O(log n)

sorted_arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(binarysearch(sorted_arr, 0, len(sorted_arr) -  1, 5)) # 4
print(binarysearch(sorted_arr, 0, len(sorted_arr) -  1, 500)) # -1

Bubble Sort

	Best case	Worst case
Time	O(n)	O(n²)

arr = [3, 2, 6, 1, 76, 5, 35, 86]
bubble_sort(arr) # [1, 2, 3, 5, 6, 35, 76, 86]

Selection Sort

	Best case	Worst case
Time	O(n²)	O(n²)

arr = [3, 2, 6, 1, 76, 5, 35, 86]
selection_sort(arr) # [1, 2, 3, 5, 6, 35, 76, 86]

Insertion Sort

	Best case	Worst case
Time	O(n)	O(n²)

arr = [3, 2, 6, 1, 76, 5, 35, 86]
insertion_sort(arr) # [1, 2, 3, 5, 6, 35, 76, 86]

Quick Sort

	Best case	Worst case
Time	O(n log n)	O(n²)

arr = [3, 2, 6, 1, 76, 5, 35, 86]
quicksort(arr, 0, len(arr) -  1)) # [1, 2, 3, 5, 6, 35, 76, 86]

Merge Sort

	Best case	Worst case
Time	O(n log n)	O(n log n)

arr = [3, 2, 6, 1, 76, 5, 35, 86]
mergesort(arr) # [1, 2, 3, 5, 6, 35, 76, 86]

Heap Sort

	Best case	Worst case
Time	O(n log n)	O(n log n)

arr = [3, 2, 6, 1, 76, 5, 35, 86]
bubblesort(arr) # [1, 2, 3, 5, 6, 35, 76, 86]

Naive String Matching Algorithm

	Best case	Worst case
Time	O(n)	O(nm)

string = "banana"
print(naive_string_matcher(string, "nan")) # 2
print(naive_string_matcher(string, "apple")) # None 

Rabin-Karp Algorithm

	Best case	Worst case
Time	O(n + m)	O(nm)

string = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
print(rabin_karp_string_matcher(string, [3, 4, 5])) # 2
print(rabin_karp_string_matcher(string, [10, 20, 30])) # -1