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 @Override annotation 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
  • O(1)O(1): constant time

  • O(logn)O(log n): logarithmic time (e.g., binary search)

  • O(n)O(n): linear time

  • O(nextlogn)O(n ext{ log } n): efficient sorting algorithms

  • O(n2)O(n^2): nested loops

  • O(2n),O(n!)O(2^n), O(n!): 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 O(1)O(1).

  • Adding or removing in the middle is O(n)O(n).

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 O(1)O(1).

  • Traversal is O(n)O(n).

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 O(1)O(1) 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 O(1)O(1) 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.