CSC 201 — Data Structures Condensed Course Notes v1
CSC 201 — Data Structures Condensed Course Notes
These notes condense the original lecture slides into a compact, text-only format suitable for studying and uploading to Knowt. Repetitions, animations, and purely visual slides have been removed.
1. Abstract Data Types (ADTs)
Definition: An Abstract Data Type (ADT) is a logical description of a data type, defined by its behavior rather than its implementation.
An ADT specifies what operations are supported, not how they are carried out.
Key Idea: Users interact with an ADT using public methods and do not need to know how data is stored internally.
Examples of ADTs: Lists, stacks, and queues.
ADTs and Java Interfaces
In Java, an ADT is commonly represented using an interface.
Interfaces: Define method names, parameters, and return types, but no implementations.
Classes such as ArrayList or LinkedList implement interfaces and provide concrete implementations of ADTs.
Data Structures vs ADTs
An ADT provides a logical view of data, while a data structure provides a physical representation.
Multiple data structures may implement the same ADT.
2. Object-Oriented Programming Review
Definition: Object-Oriented Programming (OOP) organizes programs using objects that combine data fields and methods.
Major OOP Concepts: Encapsulation, inheritance, polymorphism, and abstraction.
Inheritance (Is-a Relationship)
Inheritance allows a class to extend another class.
Example: A Notebook is-a Computer.
Has-a Relationship (Aggregation)
A has-a relationship occurs when a class contains another object as a field.
Example: A Computer has-a Memory.
Constructors and super
Subclasses call superclass constructors using the
super(...)keyword.If any constructor is defined, a no-argument constructor must be explicitly provided if needed.
Method Overriding and Overloading
Method Overriding: Occurs when a subclass provides a method with the same signature as one in the superclass.
Method Overloading: Occurs when methods share a name but differ in parameters.
The
@Overrideannotation helps catch errors at compile time.
Polymorphism
Polymorphism allows a superclass reference to refer to a subclass object.
The Java Virtual Machine (JVM) determines which overridden method to call at runtime.
Abstract Classes and Interfaces
Abstract Classes: Cannot be instantiated, may contain abstract methods, concrete methods, and fields.
Interfaces: Define method signatures only.
A class may implement multiple interfaces but can extend only one class.
Packages and Visibility
Java Packages: Group related classes.
Visibility Modifiers: Control access levels: private, default (package), protected, and public.
3. Algorithm Efficiency and Big-O Notation
Algorithm Efficiency: Describes how runtime or memory usage grows as input size increases.
Big-O Notation: Expresses the upper bound of an algorithm's growth rate.
Primitive Operations
Efficiency analysis counts primitive operations such as assignments, comparisons, arithmetic, and array access.
Worst-Case Analysis
Big-O notation typically describes worst-case behavior, which provides a reliable upper bound on performance.
Common Big-O Classes
: constant time
: logarithmic time (e.g., binary search)
: linear time
: efficient sorting algorithms
: nested loops
: exponential and factorial growth
Big-O Rules
Ignore constants and lower-order terms.
Sequential statements add; nested loops multiply.
Choose the dominant term.
4. Lists, Arrays, and ArrayList
A list is an ordered collection of elements, where each element has a position.
Arrays
Arrays store elements contiguously and allow constant-time access by index.
Array size: Fixed; inserting or removing elements requires shifting.
ArrayList
ArrayList: A resizable array implementation of the List ADT.
Tracks size and capacity and resizes when full.
get and set operations are .
Adding or removing in the middle is .
Linked Lists
Linked lists store elements in nodes connected by references.
Singly Linked Lists
Each node stores data and a reference to the next node.
Insertion or removal at the head is .
Traversal is .
Doubly Linked Lists
Each node stores references to both next and previous nodes.
Allows efficient insertion and removal when node references are known.
Circular Linked Lists
The last node links back to the first node.
Useful for round-robin scheduling.
ArrayList vs LinkedList Performance
ArrayList: Fast random access, slow middle insertions.
LinkedList: Fast insertions/removals when location is known, slow access by index.
5. Stacks
A stack is a LIFO (Last-In, First-Out) data structure.
Only the top element is accessible.
Stack Operations
push: Add item to the top.pop: Remove the top item.peek: Inspect the top item.empty: Check if the stack is empty.size: Get the number of items in the stack.
Stack Implementations
Stacks can be implemented using arrays or linked lists.
All stack operations run in time.
Stack Applications
Checking palindromes.
Balanced parentheses and HTML tag matching.
Postfix expression evaluation.
Infix to postfix conversion.
6. Queues
A queue is a FIFO (First-In, First-Out) data structure.
Insertions occur at the rear and removals at the front.
Queue Operations
offer/add: Insert element.poll/remove: Remove front element.peek/element: Inspect front element.
Queue Implementations
LinkedList-based queues support insertion and removal.
Circular arrays efficiently reuse space using modular arithmetic.
Deque
A deque (double-ended queue) allows insertion and removal at both ends.
End of Condensed Notes
These notes are designed to replace the original slides for studying purposes.