/data-structures-and-algorithms-in-cpp

Data structures and algorithms in CPP - Study Notes

Primary LanguageC++

Practical Data structures and Algorithms in C++

Array

✔️ Dynamic Array Implementation.

  • Well, I don't think I will implement another Vector in CPP, but let's see ;).

Bitwise

Tree

✔️ Binary Search Tree Implementation.

  • BinarySearchTree::insert() - insert a new node in BST.
  • BinarySearchTree::remove() - remove a node from BST.
  • BinarySearchTree::traverse() - traverse BST in DFS-in/pre/postorder and BFS.
  • BinarySearchTree::erase() - erase all nodes and free the memory.
  • BinarySearchTree::print() - print all nodes and its parents info.
  • BinarySearchTree::count() - count of nodes.
  • BinarySearchTree::getMax() - max number in BST.
  • BinarySearchTree::getMin() - min number in BST.
  • BinarySearchTree::getHeight() - height of the BST.
  • BinarySearchTree::successor() - find inorder successor.
  • BinarySearchTree::isValid() - if BST is valid.
  • BinarySearchTree::contain() - if contain the target element.
  • BinarySearchTree::isEmpty() - if tree is empty.

Priority Queue && Binary Heap

✔️ Priority Queue Implementation with Max Heap.

  • PriorityQueue::insert() - insert a new element to the queue.
  • PriorityQueue::max() - get the max element.
  • PriorityQueue::extractMax() - remove the max element and return it.
  • PriorityQueue::capacity() - queue capacity.
  • PriorityQueue::size() - current size of the queue.
  • PriorityQueue::empty() - if queue is empty.
  • PriorityQueue::full() - if queue is full.
  • PriorityQueue::heapSort() - take an array as input and sort it in place.
  • PriorityQueue::print() - print all queue elements.
  • PriorityQueue::heapify_() - helper for heapSort().
  • PriorityQueue::siftUp_() - sift element up.
  • PriorityQueue::siftDown_() - sift element down.

Linked List

✔️: Singly Linked List Implementation.

  • LinkedList::insertFront() - insert a new element to the front.
  • LinkedList::insertBack() - insert a new element to the end.
  • LinkedList::remove() - remove an element by value.
  • LinkedList::removeFront() - remove the front element and return it.
  • LinkedList::removeEnd() - remove the last element and return it.
  • LinkedList::erase() - erase all elements.
  • LinkedList::reverse() - reverse the list.
  • LinkedList::print() - print all nodes value.
  • LinkedList::empty() - if list is empty.
  • LinkedList::size() - count of element in the list.

Sorting

  • Bubble Sort - bubble sort, Time: best: O(n), average: O(n^2), worst: O(n^2); Space: O(1). Stable.
  • Insertion Sort - insertion sort, Time: best: O(n), average: O(n^2), worst: O(n^2); Space: O(1). Stable.
  • Selection Sort - selection sort, Time: best: O(n^2), average: O(n^2), worst: O(n^2); Space: O(1). Not Stable.
  • Heap Sort - heap sort, Time: best: O(nlogn), average: O(nlogn), worst: O(nlogn); Space: O(1). Not Stable.
  • Merge Sort - merge sort, Time: best: O(nlogn), average: O(nlogn), worst: O(nlogn); Space: O(n). Stable.
  • Quick Sort - quick sort, Time: best: O(nlogn), average: O(nlogn), worst: O(n^2); Space: O(logn). Not Stable.

Graph

Graph representations

  • Objects and Pointers.
  • Adjacency Matrix.
  • Adjacency List.
  • Re-do graphs.