Data Structures

Abstract Data Types and Sequentially Allocated Bags

• The Bag
• Specifying a Bag
• Using the ADT Bag
• Using an ADT Is Like Using a Vending Machine
• Bag Implementations That Use Arrays
• Using a Fixed-Size Array to Implement the ADT Bag
• The Pros and Cons of Using an Array to Implement the ADT Bag

Implementing Bags with Linked Allocation

• 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

Introduction to Analysis of Algorithms

• The Efficiency of Algorithms
• Motivation
• Measuring an Algorithm's Efficiency
• Picturing Efficiency
• The Efficiency of Implementations of the ADT Bag

Stacks

• Stacks
• Specifications of the ADT Stack
• Using a Stack to Process Algebraic Expressions
• Stack Implementations
• A Linked Implementation
• An Array-Based Implementation

Queues

• Queues, Deques, and Priority Queues
• The ADT Queue
• Queue, Deque, and Priority Queue Implementations
• A Linked Implementation of a Queue
• An Array-Based Implementation of a Queue

Deques

• The ADT Deque
• A Doubly Linked Implementation of a Deque

Lists

• Lists
• Specifications for the ADT List
• Using the ADT List
• List Implementations That Use Arrays
• Using an Array to Implement the ADT List
• 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

Basic Sorting Algorithms

• An Introduction to Sorting
• Organizing Java Methods That Sort an Array
• Selection Sort
• Insertion Sort

Faster Sorting Algorithms

• Faster Sorting Methods
• Merge Sort
• Quick Sort
• Radix Sort

Sorted Lists

• Specifications for the ADT Sorted List
• A Linked Implementation

Searching a List

• Searching
• The Problem
• Searching an Unsorted Array
• Searching a Sorted Array
• Searching an Unsorted Chain
• Searching a Sorted Chain
• Choosing a Search Method

Dictionary as an Associative ADT

• Dictionaries
• Specifications for the ADT Dictionary
• Using the ADT Dictionary

Sequential Hash Tables

• Introducing Hashing
• What Is Hashing?
• Hash Functions
• Resolving Collisions

Bucket Hashing

Introduction to Trees

• Tree Concepts
• Traversals of a Tree
• Examples of Binary Trees
• Examples of General Trees

Implementation of Binary Trees

• An Implementation of the ADT Binary Tree

Binary Search Trees

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

Appendix A Java Essentials

• Introduction
• Java Basics
• 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

Appendix B Java Classes

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

Appendix C Creating Classes from Other Classes

• Composition
• Inheritance
• Type Compatibility and Superclasses
• Polymorphism

Appendix D Designing Classes

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

Appendix E Handling Exceptions

• The Basics
• Handling an Exception
• Throwing an Exception
• Programmer-Defined Exception Classes
• Inheritance and Exceptions
• The finally Block

Appendix F File Input and Output

• Preliminaries
• Text Files
• Binary Files

Appendix G Documentation and Programming Style

• Naming Variables and Classes
• Indenting
• Comments