book

Data Structures Using Java

Name: Data Structures Using Java
Author: Duncan A. Buell
ISBN: 9781449628086

by Duncan A. Buell

December 2011

Intermediate to advanced

392 pages

16h 35m

English

Jones & Bartlett Learning

Read now

Unlock full access

Cover
Title
Copyright
Dedication
Contents
Preface
Chapter 1 Introduction
1.1 The Course of This Course1.1.1 Layers of Software1.1.2 Algorithms and Efficiency1.1.3 Sorting1.1.4 Maintaining Sorted Order1.1.5 Indexing, Search, and Retrieval1.1.6 Dynamic Versus Static Behavior1.1.7 Memory and Bandwidth1.1.8 Heuristics1.1.9 Templates, Generics, and Abstract Classes1.2 Examples1.2.1 Card Catalogs1.2.2 Student Records1.2.3 Retail Transactions1.2.4 Packet Traffic1.2.5 Process Queues1.2.6 Google1.2.7 Game Trees1.2.8 Phylogenetics1.3 Summary
Chapter 2 A Review of Java
2.1 The Basic Data Payload Class2.2 The Main Program2.3 Comments about Style and Documentation2.3.1 Javadoc2.4 UML2.5 Summary2.6 Exercises
Chapter 3 Flat Files
3.1 A Basic Indexed File3.1.1 A Basic Program3.1.2 The Record Code3.1.3 A Driver for the Application3.1.4 The Original Flatfile Code3.2 An Analysis of the Code3.2.1 Sorted Data?3.2.2 A Simple but Inefficient Sorting Algorithm3.2.3 Searching Through a List3.3 A Foreshadowing of Things to Come3.3.1 Effective Sorting Techniques3.3.2 Effective Search Techniques and Data Structures for Maintaining Priority3.3.3 Static Versus Dynamic Storage Structures3.3.4 Generic and Abstract Classes3.3.5 Arrays Versus ArrayLists3.4 Binary Search: Our First Mature Algorithm3.5 Summary3.6 Exercises
Chapter 4 Arrays and Linked Lists
4.1 Arrays and ArrayLists4.2 Linked Lists4.2.1 Linked Lists and Pointers4.2.2 A Linked List Class4.2.3 Exception Handling4.2.4 Linked Lists Using Arrays4.2.5 Arrays, ArrayLists, and the Free List4.3 Insertionsort4.4 Summary4.5 Exercises

Chapter 5 Generics, Collections, and Testing
5.1 Using Generics for the Data Payload5.2 Objects and Equality5.3 The Java LinkedList5.4 Iterators5.4.1 The Justification for Iterators5.5 Implementing Our Very Own Collection5.6 Testing with JUnit5.7 Reflection5.8 Summary5.9 Exercises
Chapter 6 Estimating Asymptotic Efficiency
6.1 Analysis of Algorithms6.1.1 The Definition of a “Logarithm”6.1.2 A Few Comments about the Real World6.2 Some Rigor6.2.1 An Apology for Some Audacity6.2.2 Basic Orders of Magnitude, and Some Intuition6.2.3 Constants Don’t Matter6.2.4 Constant Startup Costs Don’t Matter6.2.5 Big Oh Is Transitive6.2.6 All Logarithms Are the Same6.2.7 All Polynomials of the Same Degree Are the Same6.2.8 All Reasonable Cost-of-Work Functions Go Off to Infinity6.3 Some More Rigor6.3.1 Little oh6.3.2 Big Theta, and Some More Simplifying Theorems6.3.3 Ignoring Fencepost Issues6.3.4 Basic Orders of Magnitude Revisited6.4 More Intuition—Common Asymptotics*6.5 Exponential Orders of Magnitude 6.5.1 Exponential Orders of Magnitude*6.6 Big Omega6.6.1 Traditional Big Omega (Hardy,about 1915)6.6.2 Knuth’s Big Omega (Knuth,about 1975)6.7 What Do We Count?6.8 Binary Divide and Conquer Is Optimal6.9 Summary6.10 Exercises
Chapter 7 Stacks and Queues
7.1 Stacks7.1.1 Exception Handling7.1.2 Stacks Using Nodes7.1.3 Stacks Using Arrays7.1.4 Reverse Polish Arithmetic7.2 HTML/XML and Stacks7.3 Queues7.3.1 Queues Using Nodes7.3.2 Queues Using Arrays7.4 The JCF Classes7.4.1 The JCF Stack7.4.2 The JCF Queue7.4.3 Stacks, Queues, and Deques7.5 Priority Queues7.5.1 The Heap7.5.2 Creating a Heap7.5.3 Maintaining the Heap7.6 Summary7.7 Exercises
Chapter 8 Recursion
8.1 Factorials and Fibonacci Numbers8.2 The Collatz Problem8.3 Greatest Common Divisor8.4 The Ackermann Function8.5 Binary Divide-and-Conquer Algorithms8.6 Permutations and Combinations8.7 Gaming and Searching Applications8.8 Implementation Issues8.9 Summary8.10 Exercises
Chapter 9 A First Look at Graphs
9.1 Formal Notions of a Graph9.2 Examples of Graphs9.3 Transitive Closure9.3.1 Facebook Graphs9.3.2 Theory9.3.3 Applications in Computing9.4 Local–Global Questions9.5 Greedy Algorithms9.6 Summary9.7 Exercises
Chapter 10 Trees
10.1 Trees10.2 Spanning Trees10.3 Data Structures for Trees10.4 Binary Trees10.4.1 Implementing Binary Trees with Nodes10.4.2 Implementing Binary Trees with Arrays10.5 The Heap10.6 Traversing a Tree10.6.1 Breadth-First and Depth-First Traversal10.6.2 Traversal on Parallel Computers10.7 Summary10.8 Exercises
Chapter 11 Sorting
11.1 Worst-Case, Best-Case, and Average-Case11.2 Bubblesort11.3 Insertionsort11.4 Improving Bubblesort11.5 Heapsort11.6 Worst-Case, Best-Case, and Average-Case (Again)11.7 Mergesort11.7.1 Analysis of Mergesort11.7.2 Disk-Based Sorting11.8 Quicksort11.8.1 The Quicksort Algorithm11.8.2 Average-Case Running Time for Quicksort11.9 Sorting Without Comparisons11.10 Experimental Results11.11 Auxiliary Space and Implementation Issues11.11.1 Space Considerations11.11.2 Memory11.11.3 Multilevel Sorts11.11.4 Stability11.12 The Asymptotics of Sorting11.12.1 Lower Bounds on Sorting11.12.2 A Proof of Lower Bounds11.12.3 Lower Bounds for the Average Case*11.13 Sorting in Parallel11.13.1 Analysis11.14 Summary11.15 Exercises
Chapter 12 Searching
12.1 Associative Matching12.2 Indexing for Search12.3 Binary Search Trees12.3.1 Inorder Traversal and Binary Search Trees12.3.2 Building a Binary Search Tree12.4 Sophisticated Search Trees12.5 Hashing12.6 Random Numbers and Hash Functions: A Brief Digression12.6.1 Random Numbers12.6.2 Cryptographic Hash Functions12.6.3 Random Numbers in Java12.7 The Java Collections Framework12.8 The Java HashSet12.8.1 A Spell-Checking Program12.9 The Java TreeMap12.9.1 A Digression on Documentation12.10 The Java TreeSet, HashMap, and LinkedList12.11 Summary12.12 Exercises
Chapter 13 Graphs
13.1 Graphs and Applications13.2 Adjacency Matrices and Linked Lists13.2.1 Adjacency Matrices13.2.2 Sparse Graphs and Sparse Matrices13.2.3 Linked Lists for Sparse Graphs13.2.4 A Middle Ground, Somewhat Helped by Java13.3 Breadth-First and Depth-First Search13.4 Graph Problems13.4.1 NP-Completeness13.4.2 Eulerian Cycles13.4.3 Connected Components13.4.4 Spanning Trees13.4.5 Shortest Path13.4.6 Hamiltonian Cycles13.4.7 Traveling Salesman Problem13.4.8 Cliques13.5 Summary13.6 Exercises
Appendix A The Author’s Idiosyncrasies of Coding Style
A.1 UtilitiesA.2 Log FilesA.3 Labeling Trace OutputA.4 Naming ConventionsA.5 Use of this in JavaA.6 Labeling Closing BracesA.7 Keep It SimpleA.8 The Infamous Double Equals
Appendix B File Utilities
B.1 Header, Boilerplate, and a Log FileB.2 Setting Up an Output PrintWriter FileB.3 Setting Up an Input Scanner File
Appendix C Glossary
C.1 The Nature of JargonC.2 Terms Used in This Book
Index

Content preview from Data Structures Using Java

Searching

Objectives

 An introduction to binary search trees

 An introduction to hash functions and hash tables

 A brief introduction to random number generation

 An introduction to Java Collections Framework structures supporting

search: List, Map, Set, HashSet, TreeMap, TreeSet,andHashMap

Key Terms

associative search

binary search tree

content-addressable search

document authentica-

tion

document integrity

document nonrepudia-

tion

hash collision

hash function

hash table load factor

index

JCF

map

mixed-linear-

congruential

probe

pseudorandom number

Introduction

Much of this course and text have been about the eﬃcient storage and retrieval of

data. The interest ...

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

Object-Oriented Data Structures Using Java, 4th Edition

Publisher Resources

ISBN: 9781449628079

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Data Structures Using Java

by Duncan A. Buell

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.