COMP103 Lecture Notes: Data Structures, Java API, and Algorithms

A set of vocabulary flashcards covering key concepts from the lecture notes on abstraction, interfaces, Java API, collections, generics, trees, recursion, and algorithm analysis.

Abstraction

A design principle that allows reasoning at a conceptual level by hiding implementation details.

Separation of concerns

Dividing a software system into distinct features or modules with minimal overlap.

Interface

A contract that defines method signatures without implementations; enables abstraction and polymorphism.

Abstract method

A method declaration without a body in an interface or abstract class; must be implemented by subclasses.

Java API

The standard library of packages and classes provided by the Java platform.

Java Package

A namespace that organizes related classes, e.g., java.util, java.lang.

Object class

Root class of all Java classes; every class implicitly extends it if no other superclass is specified.

toString

A method that returns a string representation of an object; commonly overridden.

equals

A method to compare logical equality between objects; differs from the == operator.

hashCode

An integer used by hash-based collections; must be consistent with equals.

Inheritance

IS-A relationship where a subclass inherits fields and methods from a superclass.

Single inheritance

Java supports only one class inheritance; multiple class inheritance is not allowed.

HAS-A relationship

Composition; a class contains objects as fields to build complex types.

Override

Redefining a superclass method in a subclass to provide specialized behavior.

super

A reference to the superclass, used to access its members or methods.

Java Collections Framework

A set of interfaces and classes for handling groups of objects such as List, Set, Map, Queue.

List

Ordered collection that allows duplicates; implementations include ArrayList and LinkedList.

ArrayList

Resizable-array implementation of List; supports dynamic resizing.

LinkedList

List implemented as a linked list; efficient insertions/removals.

Set

Collection that cannot contain duplicate elements; HashSet, TreeSet, LinkedHashSet.

HashSet

Set implementation based on a hash table; fast contains/add but unordered.

TreeSet

Sorted set backed by a tree structure; ordered by natural order or comparator.

Map

Collection of key-value pairs; keys are unique; implementations include HashMap, TreeMap, LinkedHashMap.

HashMap

Hash-based map; fast access; may allow null keys/values; not a subtype of Collection.

TreeMap

Sorted map; keys ordered by natural order or comparator; may not allow null keys.

LinkedHashMap

Map that preserves insertion order of entries.

ConcurrentHashMap

Thread-safe map implementation for concurrent environments.

Map views

Methods keySet(), values(), and entrySet() provide views of map contents.

Map.Entry

Interface representing a key-value pair in a map.

Generics

Type parameters enabling compile-time type safety, e.g., List, Map

Diamond operator

<> syntax to let the compiler infer generic types; reduces typing.

Raw type

Using a generic type without type parameters; discouraged due to safety risks.

Comparable

Interface defining a natural ordering via compareTo; used by sorted collections.

Comparator

External ordering mechanism; defines how objects should be ordered without modifying the class.

Lambda

Inline function expression in Java 8+ used to implement functional interfaces concisely.

Collections.sort

Static method to sort a list using natural order or a Comparator.

hashCode and equals contract

If equals is overridden, hashCode must be overridden as well to maintain hash-based collection integrity.

Hash collisions

When different keys produce the same hash code; resolved with buckets or probing.

Hash table

Array-based storage where items are located by a hash function; collisions require handling.

Big-O notation

Describes the upper bound of an algorithm’s time/space growth as input size increases.

Asymptotic complexity

Growth rate of an algorithm for large input sizes, dominated by the leading term.

O(1)

Constant time; cost does not grow with input size.

O(log n)

Logarithmic growth; doubling input size increases cost only slightly.

O(n)

Linear growth; cost proportional to input size.

O(n log n)

Growth rate between linear and quadratic; typical of efficient sorts.

O(n^2)

Quadratic growth; often from nested loops.

O(2^n)

Exponential growth; very costly for larger n.

O(n!)

Factorial growth; extremely expensive for larger n.

Tree traversal

Process of visiting all nodes in a tree; includes pre-order, in-order, post-order, level-order.

Binary tree

Tree where each node has at most two children: left and right.

Root/leaf/internal node

Root is the top node; leaves have no children; internal nodes have children.

Depth-first search (DFS)

Tree traversal that explores as far as possible along a branch before backtracking.

Breadth-first search (level-order)

Traversal that visits nodes level by level from the root outward.

Recursion

A method calling itself to solve a problem by solving smaller subproblems.

Base case

Condition under which a recursive function stops calling itself.

Factorial

n! is the product of all integers from n down to 1; 0! = 1 by convention.

Strings are immutable

In Java, String objects cannot be modified after creation; operations create new strings.

Heap memory

Region of memory for dynamic allocation of objects; accessed via references.

NullPointerException

Error raised when dereferencing a null reference.

String tokenization

Splitting a string into tokens, often with String.split.