book

Object-Oriented Data Structures Using Java, 4th Edition

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

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.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.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.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.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.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.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.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.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.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.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