00_data_structures.md

Data Structures

01_arrays.md

Arrays

• same type elements
• array[x] allows random access of elements
• great cache locality (processor accessing the same set of memory locations repetitively over a short Δt)
• fixed size

02_linkedList.md

Linked Lists

• elements not sorted at contiguous (=adjacent) memory locations
• methods: insert, delete, get_size, search_iterative, search_recursive
• elements linked using pointers:

A[ data | next*] ----> B[ data | next*] ----> C[ data | next*] ...
HEAD

• not fixed size
• expensive insertion of new element
• random access is not allowed
• requires extra memory for the pointer
• is not cache friendly (no locality of reference)

Doubly Linked List

• has a previous pointer
• can be traversed both ways
• quicker insert
• more efficient deletion
• but extra space for second pointer
• more maintainance for more

Circular Linked List

• no null at the end (can be singular or doubly linked)
• any node can be starting point
• implementation of queue (doesn't need 2 pointers for start & end, only end since start = end -> next))
• used when CPU cycles many times on the same data pointers

03_stack.md

Stack (linear LIFO or FILO)

• methods (all are O(1)):
  • push (add to start - if full, overflow)
  • pop (remove item in the reverse order as pushed - if empty, underflow)
  • peek/top (return top element)
  • isEmpty
• implementation with array:
  • easy to implement, saves memory (no pointers needed)
  • BUT not dynamic (doesn't shrink or grow depending on runtime needs)
• implementation with linked list:
  • more memory needed
  • BUT dynamic

04_queue.md

Queue (linear FIFO)

• methods (all are O(1)):
  • enqueue (add element)
  • dequeue (remove element)
  • front (return front element)
  • rear (get last element)
• uses:
  • CPU scheduling
  • disk scheduling
  • asynchronous transfer of data
• cons:
  • fixed size

05_tree.md

Trees

trees

06_binaryTree.md

Binary Trees

• a tree with 2 children (left & right)
• hierarchical data structures
• topmost = root
• can be used e.g. for filesystems
• quicker access
• moderate insertion/deletion
• no upper limit of number of nodes

Properties

• maximum number of nodes on level 1: 2ⁱ
• maximum number of nodes on height h: 2^h - i
• for n nodes, minimum possible height = log₂ (n + 1)
• for l leaves, least possible number of levels = log₂(l) + 1

Types

1. full BT: all nodes have 0 or 2 children
2. complete BT: all levels completely filled except possibly last level, with keys as left as possible
3. perfect BT: all internal nodes have 2 children all leaved same level, if height h, it has 2^h - 1 nodes
4. balanced BT:
   • height is O(logn) where n the number of nodes
   • e.g. AVL, red-black
   • good because O(logn) search, insert, delete
5. degenerate/pathological: every internal node has 1 child, basically a linked list

07_bst.md

Binary Search Tree (BST)

• a binary tree where a node's left subtree's nodes are smaller than the node's key, the right subtree's nodes are larger than it and both subtrees are also BST
• used in binary search
• methods:
  • insert
    • always at a leaf node, we search a key from root until leaf and then add
  • delete
    • if a node is leaf, merely delete
    • if it has 1 child, copy child to node & delete child
    • if it has 2 children, find inorder successort, copy it to node, delete inorder successor

08_BST_vs_HT.md

A HashTable has Θ(1) search, insert, delete A self balancing BST has O(logN) search, insert, delete (e.g. RedBlack, AVL)

So why choose BST?

1. Keys are in sorted order by InorderTraversal of BST (not natural in HT)
2. When order statistics, closest lower/greater element or range queries, BST > HT
3. Easier to implement (usually needs libraries for hash functions)
4. self balancing BSTs are O(logn) whereas hashing is Θ(1) but with high cost for table resizing etc

09_heap.md

Heap = complete BT

• Types:
  • max-heap: ascending order
  • min-heap: descending order
• uses:
  • heapsort
  • priority queues
  • binomial heaps and fibonacci heaps

Build a Heap Algorithm

O(n) heapify

# Method input: A
heapsize := size(A)
for i := floor (heapsize/2) downto 1  // whole loop: O(nlogn)
  do HEAPIFY(A,i)                     // this line: O(log(n))
endfoor

10_manual.md

Structure	is good for...
Trees	Ranged search
Hash tables	equality checking, ID based search
Heaps	retrieve k min or max values of dataset

11_ht.md

Hashing Data Structure (HT)

• chaining: linked list for overflow 9same hash function value)
• open addressing: all elements saved in HT

99_sources.md

Sources

1. This FCC article
2. Notes from my studies