book

Data Structures and Algorithms Using Java

Name: Data Structures and Algorithms Using Java
Author: William McAllister
ISBN: 9781449612863

by William McAllister

December 2008

Intermediate to advanced

580 pages

15h 33m

English

Jones & Bartlett Learning

Read now

Unlock full access

Cover Page
Title Page
Copyright Page
Dedecation Page
Contents
Preface
Chapter 1 - Overview and Java Review
1.1 - Data Structures1.1.1 - What is Data?1.1.2 - What is a Data Structure?1.2 - Selecting a Data Structure1.2.1 - The Data Structure's Impact on Performance1.2.2 - Determining the Performance of a Data Structure1.2.3 - The Trade-Off Process1.3 - Fundamental Concepts1.3.1 - Terminology1.3.2 - Access Modes1.3.3 - Linear Lists1.3.4 - Data Structure Operations1.3.5 - Implementing a Programmer-Defined Data Structure1.3.6 - Procedural Abstractions and Abstract Data Types (ADTs)1.3.7 - Encapsulation1.4 - Calculating Speed (Time Complexity)1.4.1 - Big-O Analysis(O Standing for Order of Magnitude)1.4.2 - Algorithm Speed1.4.3 - Relative Speed of Algorithms1.4.4 - Absolute Speed of an Algorithm1.4.5 - Data Structure Speed1.5 - Calculating Memory Overhead (Space Complexity)1.6 - Java Review1.6.1 - Arrays of Primitive Variables1.6.2 - Definition of a Class1.6.3 - Declaration of an Object1.6.4 - Accessing Objects1.6.5 - Standard Method Name Prefixes1.6.6 - Shallow and Deep Copies1.6.7 - Declaration of an Array of Objects1.6.8 - Objects that Contain Objects as Data Members1.6.9 - Classes that Extend Classes, Inheritance1.6.10 - Parent and Child References1.6.11 - Generic TypesKnowledge ExercisesProgramming Exercises
Chapter 2 - Array-Based Structures
2.1 - The Built-in Structure Array2.1.1 - Multidimensional Arrays2.2 - Programmer-Defined Array Structures2.2.1 - Unsorted Array2.2.2 - Sorted Array2.2.3 - Unsorted-Optimized Array2.2.4 - Error Checking2.3 - Implementation of the Unsorted-Optimized Array Structure2.3.1 - Baseline Implementation2.3.2 - Utility Methods2.4 - Expandable Array-Based Structures2.5 - Generic Data Structures2.5.1 - Design Considerations2.5.2 - Generic Implementation of the Unsorted-Optimized Array2.5.3 - Client-Side Use of Generic Structures2.5.4 - Heterogeneous Generic Data Structures2.6 - Java's ArrayList ClassKnowledge ExercisesProgramming Exercises
Chapter 3 - Restricted Structures
3.1 - Restricted Structures3.2 - Stack3.2.1 - Stack Operations, Terminology, and Error Conditions3.2.2 - Classical Model of a Stack3.2.3 - A Stack Application: Evaluation of Arithmetic Expressions3.2.4 - Expanded Model of a Stack3.3 - Queue3.3.1 - Queue Operations, Terminology, and Error Conditions3.3.2 - Classical Model of a Queue3.3.3 - Queue Applications3.3.4 - Expanded Model of a Queue3.4 - Generic Implementation of the Classic Stack, a Methodized Approach3.4.1 - Generic Conversion Methodology3.5 - Priority Queues3.6 - Java's Stack ClassKnowledge ExercisesProgramming Exercises
Chapter 4 - Linked Lists and Iterators
4.1 - Noncontiguous Structures4.2 - Linked Lists4.3 - Singly Linked Lists4.3.1 - Basic Operation Algorithms4.3.2 - Implementation4.3.3 - Performance of the Singly Linked List4.3.4 - A Stack Implemented as a Singly Linked List4.4 - Other Types of Linked Lists4.4.1 - Circular Singly Linked List4.4.2 - Double-Ended Singly Linked List4.4.3 - Sorted Singly Linked List4.4.4 - Doubly Linked List4.4.5 - Multilinked List4.5 - Iterators4.5.1 - Implementation of an Iterator4.5.2 - Multiple Iterators4.6 - Java's LinkedList Class and ListIterator InterfaceKnowledge ExercisesProgramming Exercises

Chapter 5 - Hashed Data Structures
5.1 - Hashed Data Structures5.2 - Hashing Access Algorithms5.2.1 - A Hashing Example5.3 - Perfect Hashed Data Structures5.3.1 - Direct Hashed Structure5.4 - Nonperfect Hashed Structures5.4.1 - Primary Storage Area Size5.4.2 - Preprocessing Algorithms5.4.3 - Hashing Functions5.4.4 - Collision Algorithms5.4.5 - The Linear Quotient (LQHashed) Data Structure Implementation5.4.6 - Dynamic Hashed StructuresKnowledge ExercisesProgramming Exercises
Chapter 6 - Recursion
6.1 - What is Recursion?6.2 - Understanding Recursive Algorithms6.2.1 - n Factorial6.2.2 - The Code of a Recursive Algorithm6.2.3 - Tracing a Recursive Method's Execution Path6.3 - Formulating a Recursive Algorithm6.3.1 - Definitions6.3.2 - Methodology6.3.3 - Practice Problems6.4 - Problems with Recursion6.4.1 - Dynamic Programming Applied to Recursion6.5 - Backtracking, an Application of Recursion6.5.1 - A Generalized Backtracking Algorithm6.5.2 - Algorithm Adaptation MethodologyKnowledge ExercisesProgramming Exercises
Chapter 7 - Trees
7.1 - Trees7.1.1 - Graphics and Terminology of Trees7.2 - Binary Trees7.2.1 - Terminology7.2.2 - Mathematics7.3 - Binary Search Trees7.3.1 - Basic Operation Algorithms7.3.2 - Performance7.3.3 - Implementation7.3.4 - Standard Tree Traversals7.3.5 - Balanced Search Trees7.3.6 - Array Implementation of a Binary Search Tree7.3.7 - Performance7.3.8 - Java's TreeMap Data StructureKnowledge ExercisesProgramming Exercises
Chapter 8 - Sorting
8.1 - Sorting8.2 - Sorting Algorithm Speed8.2.1 - Minimum Sort Effort8.2.2 - An Implementation Issue Affecting Algorithm Speed8.3 - Sorting Algorithms8.3.1 - The Binary Tree Sort8.3.2 - The Bubble Sort8.3.3 - The Heap Sort8.3.4 - The Merge Sort8.3.5 - QuicksortKnowledge ExercisesProgramming Exercises
Chapter 9 - Graphs
9.1 - Introduction9.1.1 - Graphics and Terminology of Graphs9.2 - Representing Graphs9.2.1 - Representing Vertices9.2.2 - Representing Edges9.3 - Operations Performed on Graphs9.4 - Implementing Graphs in the Vertex Number Mode9.5 - Traversing Graphs9.5.1 - Depth-First Traversal9.5.2 - Breadth-First Traversal9.6 - Connectivity and Paths9.6.1 - Connectivity of Undirected Graphs9.6.2 - Connectivity of Directed Graphs9.6.3 - Spanning Trees9.6.4 - Shortest PathsKnowledge ExercisesProgramming Exercises
Appendices
Appendix A - ASCII Table
Appendix B - Derivation of the Average Search Length of a Nondirect Hashed Data Structure
Appendix C - Proof That If an Integer, P, is not Evenly Divisible by an Integer Less Than the Square Root of P, It is a Prime Number
Appendix D - Calculations to Show That (n + 1) (log2(n + 1) − 2) is the Minimum Sort Effort for the Binary Tree Sort
Glossary
Index

Content preview from Data Structures and Algorithms Using Java

APPENDIX B

Derivation of the Average Search Length of a Nondirect Hashed Data Structure

The derivation will be based on the following assumptions:

• There are n nodes in the structure, and the size of the primary storage area is N.

• All N primary storage area locations are equally probable to be generated each pass through the collision algorithm.

The easiest way to present the derivation for average search length is to consider the search for an unused location in which to perform an Insert operation. By our first assumption, n of the N locations are used. Therefore, the probability of hashing into an occupied location is n/N. For example, if there are 700 nodes in the structure, and the size of the primary storage area array is 1000, ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9780763757564

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Data Structures and Algorithms Using Java

by William McAllister

APPENDIX B

Derivation of the Average Search Length of a Nondirect Hashed Data Structure

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.