Linear Data Structures

 

  • Static Array in C/C++ and in Java

  • Resizeable Array: C++ STL <vector> (Java ArrayList)

  • Linked List: C++ STL <list> (Java LinkedList)
    (Not used in competition programming due to speed...)

  • Stack: C++ STL <stack> (Java Stack)

  • Queue: C++ STL <queue> (Java Queue)

Efficient Sorting and Searching in Static/Resize-able Array

 

  • O(n2) comparison-based sorting algorithms: Bubble/Selection/Insertion Sort.

  • O(n log n) comparison-based sorting algorithms: Merge/Heap/Random Quick Sort

  • O(n) special purpose sorting algorithms: Radix Sort, Bucket Sort, Counting Sort

  • O(n) Linear Search from index 0 to index n-1 (avoid this in programming contests)

  • O(log n) Binary Search: use lower bound in C++ STL <algorithm> (or Java Collections.binarySearch).

  • O(1) hashing