Data Structures and Abstractions with Java

This course includes
Lessons
TestPrep
Lab

Lessons

37+ Lessons | 291+ Exercises | 506+ Quizzes | 523+ Flashcards | 523+ Glossary of terms

TestPrep

146+ Pre Assessment Questions | 145+ Post Assessment Questions |

Here's what you will learn

Download Course Outline

Lessons 1: Introduction 

  • Organizing Data

Lessons 2: Prelude: Designing Classes

  • Encapsulation
  • Specifying Methods
  • Java Interfaces
  • Choosing Classes
  • Reusing Classes
  • Exercises
  • Projects

Lessons 3: Bags

  • The Bag
  • Specifying a Bag
  • Using the ADT Bag
  • Using an ADT Is Like Using a Vending Machine
  • The ADT Set
  • Java Class Library: The Interface Set
  • Java Interlude 1: Generics
  • Lesson Summary
  • Programming Tip
  • Exercises
  • Projects

Lessons 4: Bag Implementations That Use Arrays

  • Using a Fixed-Size Array to Implement the ADT Bag
  • Using Array Resizing to Implement the ADT Bag
  • The Pros and Cons of Using an Array to Implement the ADT Bag
  • Java Interlude 2 Exceptions
  • Lesson Summary
  • Programming Tips
  • Exercises
  • Projects

Lessons 5: A Bag Implementation That Links Data

  • Linked Data
  • A Linked Implementation of the ADT Bag
  • Removing an Item from a Linked Chain
  • A Class Node That Has Set and Get Methods
  • The Pros and Cons of Using a Chain to Implement the ADT Bag
  • Lesson Summary
  • Programming Tip
  • Exercises
  • Projects

Lessons 6: The Efficiency of Algorithms

  • Motivation
  • Measuring an Algorithm’s Efficiency
  • Big Oh Notation
  • Picturing Efficiency
  • The Efficiency of Implementations of the ADT Bag
  • Lesson Summary
  • Exercises
  • Projects

Lessons 7: Stacks

  • Specifications of the ADT Stack
  • Using a Stack to Process Algebraic Expressions
  • The Program Stack
  • Java Class Library: The Class Stack
  • Lesson Summary
  • Programming Tip
  • Exercises
  • Projects

Lessons 8: Stack Implementations

  • A Linked Implementation
  • An Array-Based Implementation
  • A Vector-Based Implementation
  • Java Interlude 3: More About Exceptions
  • Lesson Summary
  • Exercises
  • Projects

Lessons 9: Queues, Deques, and Priority Queues

  • The ADT Queue
  • The ADT Deque
  • The ADT Priority Queue
  • Lesson Summary
  • Programming Tip
  • Exercises
  • Projects

Lessons 10: Queue, Deque, and Priority Queue Implementations

  • A Linked Implementation of a Queue
  • An Array-Based Implementation of a Queue
  • Circular Linked Implementations of a Queue
  • Java Class Library: The Class AbstractQueue
  • A Doubly Linked Implementation of a Deque
  • Possible Implementations of a Priority Queue
  • Lesson Summary
  • Programming Tip
  • Exercises
  • Projects

Lessons 11: Recursion

  • What Is Recursion?
  • Tracing a Recursive Method
  • Recursive Methods That Return a Value
  • Recursively Processing an Array
  • Recursively Processing a Linked Chain
  • The Time Efficiency of Recursive Methods
  • Tail Recursion
  • Using a Stack Instead of Recursion
  • Lesson Summary
  • Programming Tips
  • Exercises
  • Projects

Lessons 12: Lists

  • Specifications for the ADT List
  • Using the ADT List
  • Java Class Library: The Interface List
  • Java Class Library: The Class ArrayList
  • Lesson Summary
  • Exercises
  • Projects

Lessons 13: A List Implementation That Uses an Array

  • Using an Array to Implement the ADT List
  • The Efficiency of Using an Array to Implement the ADT List
  • Lesson Summary
  • Exercises
  • Projects

Lessons 14: A List Implementation That Links Data

  • Operations on a Chain of Linked Nodes
  • Beginning the Implementation
  • Continuing the Implementation
  • A Refined Implementation
  • The Efficiency of Using a Chain to Implement the ADT List
  • Java Class Library: The Class LinkedList
  • Java Interlude 4: Iterators
  • Lesson Summary
  • Exercises
  • Projects

Lessons 15: Iterators for the ADT List

  • Ways to Implement an Iterator
  • A Separate Class Iterator
  • An Inner Class Iterator
  • Why Are Iterator Methods in Their Own Class?
  • An Array-Based Implementation of the Interface ListIterator
  • Lesson Summary
  • Programming Tip
  • Exercises
  • Projects

Lessons 16: Problem Solving with Recursion

  • A Simple Solution to a Difficult Problem
  • A Poor Solution to a Simple Problem
  • Languages and Grammars
  • Indirect Recursion
  • Backtracking
  • Java Interlude 5: More About Generics
  • Lesson Summary
  • Exercises
  • Projects

Lessons 17: An Introduction to Sorting

  • Organizing Java Methods That Sort an Array
  • Selection Sort
  • Insertion Sort
  • Shell Sort
  • Comparing the Algorithms
  • Lesson Summary
  • Programming Tip
  • Exercises
  • Projects

Lessons 18: Faster Sorting Methods

  • Merge Sort
  • Quick Sort
  • Radix Sort
  • Comparing the Algorithms
  • Java Interlude 6: Mutable and Immutable Objects
  • Lesson Summary
  • Exercises
  • Projects

Lessons 19: Sorted Lists

  • Specifications for the ADT Sorted List
  • A Linked Implementation
  • An Implementation That Uses the ADT List
  • Java Interlude 7: Inheritance and Polymorphism
  • Lesson Summary
  • Exercises
  • Projects

Lessons 20: Inheritance and Lists

  • Using Inheritance to Implement a Sorted List
  • Designing a Base Class
  • An Efficient Implementation of a Sorted List
  • Lesson Summary
  • Programming Tips
  • Exercises
  • Projects

Lessons 21: Searching

  • The Problem
  • Searching an Unsorted Array
  • Searching a Sorted Array
  • Searching an Unsorted Chain
  • Searching a Sorted Chain
  • Choosing a Search Method
  • Java Interlude 8: Generics Once Again
  • Lesson Summary
  • Programming Tip
  • Exercises
  • Projects

Lessons 22: Dictionaries

  • Specifications for the ADT Dictionary
  • Using the ADT Dictionary
  • Java Class Library: The Interface Map
  • Lesson Summary
  • Programming Tips
  • Exercises
  • Projects

Lessons 23: Dictionary Implementations

  • Array-Based Implementations
  • Linked Implementations
  • Lesson Summary
  • Programming Tips
  • Exercises
  • Projects

Lessons 24: Introducing Hashing

  • What Is Hashing?
  • Hash Functions
  • Resolving Collisions
  • Lesson Summary
  • Exercises
  • Projects

Lessons 25: Hashing as a Dictionary Implementation

  • The Efficiency of Hashing
  • Rehashing
  • Comparing Schemes for Collision Resolution
  • A Dictionary Implementation That Uses Hashing
  • Java Class Library: The Class HashMap
  • Java Class Library: The Class HashSet
  • Lesson Summary
  • Exercises
  • Projects

Lessons 26: Trees

  • Tree Concepts
  • Traversals of a Tree
  • Java Interfaces for Trees
  • Examples of Binary Trees
  • Examples of General Trees
  • Lesson Summary
  • Exercises
  • Projects

Lessons 27: Tree Implementations

  • The Nodes in a Binary Tree
  • An Implementation of the ADT Binary Tree
  • An Implementation of an Expression Tree
  • General Trees
  • Using a Binary Tree to Represent a General Tree
  • Java Interlude 9: Cloning
  • Lesson Summary
  • Programming Tips
  • Exercises
  • Projects

Lessons 28: A Binary Search Tree Implementation

  • Getting Started
  • Searching and Retrieving
  • Traversing
  • Adding an Entry
  • Removing an Entry
  • The Efficiency of Operations
  • An Implementation of the ADT Dictionary
  • Lesson Summary
  • Exercises
  • Projects

Lessons 29: A Heap Implementation

  • Reprise: The ADT Heap
  • Using an Array to Represent a Heap
  • Adding an Entry
  • Removing the Root
  • Creating a Heap
  • Heap Sort
  • Lesson Summary
  • Exercises
  • Projects

Lessons 30: Balanced Search Trees

  • AVL Trees
  • 2-3 Trees
  • 2-4 Trees
  • Red-Black Trees
  • B-Trees
  • Lesson Summary
  • Exercises
  • Projects

Lessons 31: Graphs

  • Some Examples and Terminology
  • Traversals
  • Topological Order
  • Paths
  • Java Interfaces for the ADT Graph
  • Lesson Summary
  • Exercises
  • Projects

Lessons 32: Graph Implementations

  • An Overview of Two Implementations
  • Vertices and Edges
  • An Implementation of the ADT Graph
  • Lesson Summary
  • Exercises
  • Projects

Appendix A: Documentation and Programming Style

  • Naming Variables and Classes
  • Indenting
  • Comments

Appendix B: Java Classes

  • Objects and Classes
  • Using the Methods in a Java Class
  • Defining a Java Class
  • Enumeration as a Class
  • Packages

Appendix C: Creating Classes from Other Classes

  • Composition
  • Inheritance
  • Type Compatibility and Superclasses

Lessons 36: Supplement 1: Java Basics

  • Introduction
  • Elements of Java
  • Simple Input and Output Using the Keyboard and Screen
  • The if-else Statement
  • The switch Statement
  • Enumerations
  • Scope
  • Loops
  • The Class String
  • The Class StringBuilder
  • Using Scanner to Extract Pieces of a String
  • Arrays
  • Wrapper Classes

Lessons 37: Supplement 2: File Input and Output

  • Preliminaries
  • Text Files
  • Binary Files

Hands-on LAB Activities (Performance Labs)

Bags

  • Counting the Occurrence of Each Item in a Bag
  • Performing Matrix Multiplication
  • Transposing a Matrix
  • Finding the Intersection of Two Arrays

Bag Implementations That Use Arrays

  • Handling an Exception

A Bag Implementation That Links Data

  • Counting the Entries in a Bag
  • Adding a Node at the End of a Doubly Linked Chain
  • Removing First Node from a Doubly Linked Chain

The Efficiency of Algorithms

  • Adding Nodes to the Beginning of a Doubly Linked Chain
  • Searching an Entry in a Bag
  • Rearranging the Integers in an Array

Stacks

  • Creating a Stack and Adding Five Elements to it
  • Removing an Element from a Stack
  • Searching an Element in a Stack
  • Transferring the Elements of One Stack to Another
  • Transforming an Infix Expression to a Postfix Expression
  • Evaluating a Postfix Expression
  • Evaluating an Infix Expression
  • Testing an Input String for Palindrome Using a Stack

Stack Implementations

  • Creating an Array-Based Stack to Retrieve the Topmost Entry
  • Creating a Vector-Based Stack to Retrieve the Topmost Entry
  • Creating Custom Exception Class

Queues, Deques, and Priority Queues

  • Creating a Queue
  • Creating a Deque
  • Creating a Priority Queue

Queue, Deque, and Priority Queue Implementations

  • Removing the First Element from a Circular Linked Queue
  • Removing the First Element from a Doubly Linked Deque

Recursion

  • Creating a Recursive Void Method to Print First Five Natural Numbers
  • Traversing the Elements of a Linked List in Reverse Order
  • Creating a Recursive Method to Return the Factorial of a Number

Lists

  • Replacing an Element in the Linked List

A List Implementation That Uses an Array

  • Removing an Element from the Specified Position in a Linked List
  • Locating an Element in the Linked List

A List Implementation That Links Data

  • Adding an Element at the Specified Position in a Linked List
  • Converting an ArrayList to an Array

Iterators for the ADT List

  • Working with a List
  • Traversing a List
  • Removing Duplicates from the List

Problem Solving with Recursion

  • Evaluating a Prefix Expression

An Introduction to Sorting

  • Sorting an Array using Selection Sort
  • Sorting an Array using Insertion Sort
  • Sorting an Array using Shell Sort

Faster Sorting Methods

  • Sorting an Array using Merge Sort
  • Sorting an Array using Quick Sort
  • Sorting an Array using Radix Sort
  • Replacing a Word Using the StringBuilder Class

Sorted Lists

  • Inserting an Element into a Sorted Array
  • Using Polymorphism
  • Using the Abstract Class

Inheritance and Lists

  • Sorting a List using Inheritance

Searching

  • Performing Sequential Search
  • Performing Binary Search

Dictionaries

  • Implementing a Dictionary
  • Implementing a Map

Dictionary Implementations

  • Searching for a Key in a Dictionary

Introducing Hashing

  • Using Linear Probing in a Hash Table

Hashing as a Dictionary Implementation

  • Implementing HashMap

Trees

  • Traversing a Binary Tree using Inorder Traversal
  • Traversing a Binary Tree using Preorder Traversal
  • Traversing a Binary Tree Using Postorder Traversal

Tree Implementations

  • Counting the Nodes of a Binary Tree
  • Computing the Height of a Binary Tree

A Binary Search Tree Implementation

  • Searching a Node in the Binary Search Tree
  • Removing a Node from a Binary Search Tree

A Heap Implementation

  • Adding Nodes to a Max Heap
  • Removing the Maximum Value Node from a Max Heap
  • Sorting an Array using Heap Sort

Balanced Search Trees

  • Adding Nodes to an AVL Tree

Graphs

  • Using the DFS Traversal
  • Using the BFS Traversal
  • Using Topological Sort
  • Using Dijkstra's Algorithm

Graph Implementations

  • Printing an Adjacency List
  • Printing an Adjacency Matrix