book

Object-Oriented Data Structures Using Java, 4th Edition

Name: Object-Oriented Data Structures Using Java, 4th Edition
ISBN: 9781284089103

by Nell Dale, Daniel T. Joyce, Chip Weems

August 2016

Intermediate to advanced

694 pages

19h 29m

English

Jones & Bartlett Learning

Read now

Unlock full access

Cover Page
Title Page
Copyright Page
Dedication
Contents
Preface
1 Getting Organized
1.1 Classes, Objects, and ApplicationsClassesThe Unified MethodObjectsApplications1.2 Organizing ClassesInheritancePackages1.3 Exceptional SituationsHandling Exceptional SituationsExceptions and Classes: An Example1.4 Data StructuresImplementation-Dependent StructuresImplementation-Independent StructuresWhat Is a Data Structure?1.5 Basic Structuring MechanismsMemoryReferencesArrays1.6 Comparing Algorithms: Order of Growth AnalysisMeasuring an Algorithm’s Time EfficiencyComplexity CasesSize of InputComparing AlgorithmsOrder of GrowthSelection SortCommon Orders of GrowthSummaryExercises
2 The Stack ADT
2.1 AbstractionInformation HidingData AbstractionData LevelsPreconditions and PostconditionsJava InterfacesInterface-Based Polymorphism2.2 The StackOperations on StacksUsing Stacks2.3 Collection ElementsGenerally Usable Collections2.4 The Stack InterfaceExceptional SituationsThe InterfaceExample Use2.5 Array-Based Stack ImplementationsThe ArrayBoundedStack ClassDefinitions of Stack OperationsThe ArrayListStack Class2.6 Application: Balanced ExpressionsThe Balanced ClassThe ApplicationThe Software Architecture2.7 Introduction to Linked ListsArrays Versus Linked ListsThe LLNode ClassOperations on Linked Lists2.8 A Link-Based StackThe LinkedStack ClassThe push OperationThe pop OperationThe Other Stack OperationsComparing Stack Implementations2.9 Application: Postfix Expression EvaluatorDiscussionEvaluating Postfix ExpressionsPostfix Expression Evaluation AlgorithmError ProcessingThe PostFixEvaluator ClassThe PFixCLI Class2.10 Stack VariationsRevisiting Our Stack ADTThe Java Stack Class and the Collections FrameworkSummaryExercises
3 Recursion
3.1 Recursive Definitions, Algorithms, and ProgramsRecursive DefinitionsRecursive AlgorithmsRecursive ProgramsIterative Solution for Factorial3.2 The Three QuestionsVerifying Recursive AlgorithmsDetermining Input ConstraintsWriting Recursive MethodsDebugging Recursive Methods3.3 Recursive Processing of ArraysBinary Search3.4 Recursive Processing of Linked ListsRecursive Nature of Linked ListsTraversing a Linked ListTransforming a Linked List3.5 TowersThe AlgorithmThe MethodThe Program3.6 FractalsA T-Square FractalVariations3.7 Removing RecursionHow Recursion WorksTail Call EliminationDirect Use of a Stack3.8 When to Use a Recursive SolutionRecursion OverheadInefficient AlgorithmsClaritySummaryExercises
4 The Queue ADT
4.1 The QueueOperations on QueuesUsing Queues4.2 The Queue InterfaceExample Use4.3 Array-Based Queue ImplementationsThe ArrayBoundedQueue ClassThe ArrayUnboundedQueue Class4.4 An Interactive Test DriverThe General ApproachA Test Driver for the ArrayBoundedQueue ClassUsing the Test Driver4.5 Link-Based Queue ImplementationsThe Enqueue OperationThe Dequeue OperationA Circular Linked Queue DesignComparing Queue Implementations4.6 Application: PalindromesThe Palindrome ClassThe Applications4.7 Queue VariationsExceptional SituationsThe GlassQueueThe Double-Ended QueueDoubly Linked ListsThe Java Library Collection Framework Queue/Deque4.8 Application: Average Waiting TimeProblem Discussion and ExampleThe Customer ClassThe SimulationTesting Considerations4.9 Concurrency, Interference, and SynchronizationThe Counter ClassJava ThreadsInterferenceSynchronizationA Synchronized QueueConcurrency and the Java Library Collection ClassesSummaryExercises

5 The Collection ADT
5.1 The Collection InterfaceAssumptions for Our CollectionsThe Interface5.2 Array-Based Collection Implementation5.3 Application: Vocabulary Density5.4 Comparing Objects RevisitedThe equals MethodThe Comparable Interface5.5 Sorted Array-Based Collection ImplementationComparable ElementsThe ImplementationImplementing ADTs “by Copy” or “by Reference”Sample Application5.6 Link-Based Collection ImplementationThe Internal RepresentationThe OperationsComparing Collection Implementations5.7 Collection VariationsThe Java Collections FrameworkThe Bag ADTThe Set ADTSummaryExercises
6 The List ADT
6.1 The List InterfaceIterationAssumptions for Our ListsThe Interface6.2 List ImplementationsArray-Based ImplementationLink-Based Implementation6.3 Applications: Card Deck and GamesThe Card ClassThe CardDeck ClassApplication: Arranging a Card HandApplication: Higher or Lower?Application: How Rare Is a Pair?6.4 Sorted Array-Based List ImplementationThe Insertion SortUnsupported OperationsComparator InterfaceConstructorsAn Example6.5 List VariationsJava Library ListsLinked List VariationsA Linked List as an Array of Nodes6.6 Application: Large IntegersLarge IntegersThe Internal RepresentationThe LargeIntList classThe LargeInt ClassAddition and SubtractionThe LargeIntCLI ProgramSummaryExercises
7 The Binary Search Tree ADT
7.1 TreesTree Traversals7.2 Binary Search TreesBinary TreesBinary Search TreesBinary Tree Traversals7.3 The Binary Search Tree InterfaceThe Interface7.4 The Implementation Level: Basics7.5 Iterative Versus Recursive Method ImplementationsRecursive Approach to the size MethodIterative Approach to the size MethodRecursion or Iteration?7.6 The Implementation Level: Remaining ObserversThe contains and get OperationsThe Traversals7.7 The Implementation Level: TransformersThe add OperationThe remove Operation7.8 Binary Search Tree PerformanceText Analysis Experiment RevisitedInsertion Order and Tree ShapeBalancing a Binary Search Tree7.9 Application: Word Frequency CounterThe WordFreq ClassThe Application7.10 Tree VariationsApplication-Specific VariationsBalanced Search TreesSummaryExercises
8 The Map ADT
8.1 The Map Interface8.2 Map ImplementationsUnsorted ArraySorted ArrayUnsorted Linked ListSorted Linked ListBinary Search TreeAn ArrayList-Based Implementation8.3 Application: String-to-String Map8.4 HashingCollisions8.5 Hash FunctionsArray SizeThe Hash FunctionJava’s Support for HashingComplexity8.6 A Hash-Based MapThe ImplementationUsing the HMap class8.7 Map VariationsA Hybrid StructureJava Support for MapsSummaryExercises
9 The Priority Queue ADT
9.1 The Priority Queue InterfaceUsing Priority QueuesThe Interface9.2 Priority Queue ImplementationsUnsorted ArraySorted ArraySorted Linked ListBinary Search Tree9.3 The Heap9.4 The Heap ImplementationA Nonlinked Representation of Binary TreesImplementing a HeapThe enqueue MethodThe dequeue MethodA Sample UseHeaps Versus Other Representations of Priority QueuesSummaryExercises
10 The Graph ADT
10.1 Introduction to Graphs10.2 The Graph Interface10.3 Implementations of GraphsArray-Based ImplementationLinked Implementation10.4 Application: Graph TraversalsDepth-First SearchingBreadth-First Searching10.5 Application: The Single-Source Shortest-Paths ProblemSummaryExercises
11 Sorting and Searching Algorithms
11.1 SortingA Test Harness11.2 Simple SortsSelection SortBubble SortInsertion Sort11.3 O(N log2N) SortsMerge SortQuick SortHeap Sort11.4 More Sorting ConsiderationsTestingEfficiencyObjects and ReferencesComparing ObjectsStability11.5 SearchingSequential SearchingHigh-Probability OrderingSorted CollectionsHashingSummaryExercises
Appendix A: Java Reserved Words
Appendix B: Operator Precedence
Appendix C: Primitive Data Types
Appendix D: ASCII Subset of Unicode
Glossary
Index

Content preview from Object-Oriented Data Structures Using Java, 4th Edition

Index

Note: Italicized page locators indicate a figure; tables are noted with a t.

A

ABListIterator, iterator class, 352–353
abstract data types defined, 70
abstract keyword, 73
abstract methods
- declaring, 73
- defined, 72
abstraction, 68–78
- data abstraction, 69–70
- data levels, 70–71
- defined, 68
- information hiding, 68–69
- Java interfaces, 72–76
access modifiers
- Java, 5t
- purpose and use of, 5–6
activation record (stack frame), defined, 193
addresses, references as, 34
adjacency lists
- defined, 596
- representation of graphs with, 597
adjacency matrix, 591
- defined, 591
- representing edges in graph with, advantages, 596
adjacent vertices, defined, 588
ADTs. See abstract data types
algorithms
- comparing, 43–54
- inefficient, recursive ...

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

Data Structures and Algorithms Using Java

Publisher Resources

ISBN: 9781284089103

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Object-Oriented Data Structures Using Java, 4th Edition

by Nell Dale, Daniel T. Joyce, Chip Weems

Index

A

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.