Data Structures and Abstractions with Java

Lessons

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

TestPrep

146+ Pre Assessment Questions | 145+ Post Assessment Questions

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