Part 1 | Abstract data types, Complexity, Java Collections; Stacks, queues and linked lists

• Objectives
• To read
• Exercises A
  • Abstract Data Types: Interface vs. Class
  • Stack at the End of a Singly Linked List
  • Stack Implementations and java.util.Stack
  • Implement a Stack with Two Queues
  • Iterating Over a LinkedList vs. ArrayList
  • Asymptotic Notations: Tilde vs. Big-Oh, Omega, Theta
  • The Doubling Ratio Test
  • JVM Memory: Stack, Heap, and Garbage Collector
  • Unit Testing, Edge Cases, and Complexity Verification
  • SegmentedList and Iterators
• Exercises B
  • Circular Linked List
  • Implement a Stack with an Array
  • Reverse Polish Notation Evaluation
  • Functional Lists
  • Complexity of List, Stack, and Queue Implementations
  • Java Collections and Common Implementation Pitfalls
• Complexity
  • Big-Oh Notation (𝒪)
  • Big-Omega Notation (Ω)
  • Big-Theta Notation (Θ)
  • Tilde Notation (~)
  • Best case, worst case, average case
  • Amortized Complexity
  • Frequent complexities