Data Structures and Algorithms Topics

  • ✅ Java

    • Syntax, class structure, access modifiers

    • new, constructors, method calls, this

    ✅ Object-Oriented Programming & Polymorphism

    • Inheritance: extends, super()

    • Polymorphism: runtime behavior (method overriding)

    • Casting: upcasting/downcasting, instanceof

    ✅ Bags (Array & Linked Implementations)

    • Unordered collections with duplicates

    • Methods: add, remove, getFrequencyOf, contains, toArray

    • Array: resizing challenges

    • Linked: node manipulation

    ✅ Generics

    • Type safety: Bag<T>

    • Bounded types: <T extends Comparable<T>>

    • Wildcards: <?>, <? extends T>, <? super T>

    ✅ Exceptions

    • Try-catch blocks

    • throw vs. throws

    • Checked vs. unchecked exceptions

    ✅ Efficiency

    • Big-O notation

    • Compare array vs. linked list operations

    • Know sorting/searching complexities

    ✅ Stacks (Array & Linked)

    • LIFO: push, pop, peek, isEmpty

    • Array: top at end

    • Linked: top at head

    ✅ Recursion

    • Base + recursive cases

    • Common problems: factorial, reverse list, tree traversals

    • Stack behavior of recursive calls

    ✅ Sorting

    • Selection Sort: always O(n²), few swaps

    • Insertion Sort: better with partial order

    • Understand algorithm steps and behavior

    ✅ Queues (Array, Circular, Linked)

    • FIFO: enqueue, dequeue, peek

    • Circular array: one empty slot to detect full vs. empty

    • Linked: firstNode, lastNode refs

    ✅ Deques (Array & Linked)

    • Add/remove at both ends: addFront, addBack, removeFront, removeBack

    • Doubly linked: prev and next, head and tail pointers

    ✅ Lists (Array & Linked)

    • Operations: add(index, val), remove(index), get, contains

    • Linked: head/tail refs, singly vs. doubly, dummy nodes

    • Array: resizing and shifting

    ✅ Iterators

    • For traversal without indexing

    • Efficient for linked structures

    • Used with Iterable interface

    ✅ Sorted Lists

    • Maintains sorted order

    • Insert in order using comparator or compareTo

    • Wrapper class vs. inheritance

    ✅ More Inheritance and Polymorphism

    • Use of abstract classes, method overriding

    • Dynamic dispatch (method called depends on object type)

    ✅ Searching

    • Linear Search: unsorted or small data

    • Binary Search: sorted array/list, O(log n)

    ✅ Trees

    • Tree terms: root, child, leaf, internal, height

    • Binary tree structure: left and right children

    ✅ Binary Search Trees (BSTs)

    • Left < root < right

    • Traversals: in-order (sorted), pre-, post-, level-order

    • Operations: add, contains, getHeight, min, max

    ✅ Cloning

    • Shallow vs. deep copy

    • clone() method or custom copy constructors

    ✅ Tracing and Coding

    • Trace recursive calls, pointer movement

    • Write methods: insertAfter, reverse, removeAt

    • Rearranging nodes in lists and trees

    ✅ Ethics

    • 8 Key Questions: Fairness, Outcomes, Responsibilities, Character, Liberty, Empathy, Authority, Rights

    • ACM Code: avoid harm, respect privacy, credit others

    ✅ Data Structure Implementation Approaches

    • Array

    • Circular array (wraparound logic)

    • Singly linked list (with/without tail)

    • Doubly linked list (with/without dummy nodes)