Data Structures Using Java

Data Structures Using Java

by Duncan A. Buell
Released December 2011
Publisher(s): Jones & Bartlett Learning
ISBN: 9781449628086

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description


Written in an engaging and informal style, Data Structures Using Java facilitates a student's transition from simple programs in the first semester introductory programming course to more sophisticated, efficient, and effective programs in the second semester Data Structures course. Without delving too deeply into the details of Java, the author emphasizes the importance of effective organization and management of data and the importance of writing programs in a modern, object-oriented style.

Designed to correlate with the curricular guidelines of the ACM/IEEE Computer Science Curriculum 2008, Data Structures Using Java introduces students to the more advanced concepts of writing programs but is still accessible to non-computer science majors. Believing that learning how to design and write programs requires hands-on application of concepts, the author includes labs throughtout the text for students to immediately apply and test the newly learned material.

The accessible writing style and hands-on approach of Data Structures Using Java, will provide your students with the skills necessary to design and use algorithms and data structures in their programming careers in an uncluttered environment, and efficient manner.

Key Features:
-Content correlates to the learning objectives of the curricular guidelines of the 2008 ACM/IEEE Computer Science Curriculum.
-Avoids much of the advanced theory to provide students with the practical skills required to write algorithms and create data structures, in a one-term CS2 course.
-Ideal for students who want to enter the programming profession immediately
-Includes lab exercises throughout for students to apply the newly learned concepts.

Instructor Resources:
-PowerPoint Lecture Outlines
-Solutions to the chapter exercises
-Test Bank
-Source Code needed for the programming exercises.

Table of contents

  1. Cover
  2. Title
  3. Copyright
  4. Dedication
  5. Contents
  6. Preface
  7. Chapter 1 Introduction
    1. 1.1 The Course of This Course
      1. 1.1.1 Layers of Software
      2. 1.1.2 Algorithms and Efficiency
      3. 1.1.3 Sorting
      4. 1.1.4 Maintaining Sorted Order
      5. 1.1.5 Indexing, Search, and Retrieval
      6. 1.1.6 Dynamic Versus Static Behavior
      7. 1.1.7 Memory and Bandwidth
      8. 1.1.8 Heuristics
      9. 1.1.9 Templates, Generics, and Abstract Classes
    2. 1.2 Examples
      1. 1.2.1 Card Catalogs
      2. 1.2.2 Student Records
      3. 1.2.3 Retail Transactions
      4. 1.2.4 Packet Traffic
      5. 1.2.5 Process Queues
      6. 1.2.6 Google
      7. 1.2.7 Game Trees
      8. 1.2.8 Phylogenetics
    3. 1.3 Summary
  8. Chapter 2 A Review of Java
    1. 2.1 The Basic Data Payload Class
    2. 2.2 The Main Program
    3. 2.3 Comments about Style and Documentation
      1. 2.3.1 Javadoc
    4. 2.4 UML
    5. 2.5 Summary
    6. 2.6 Exercises
  9. Chapter 3 Flat Files
    1. 3.1 A Basic Indexed File
      1. 3.1.1 A Basic Program
      2. 3.1.2 The Record Code
      3. 3.1.3 A Driver for the Application
      4. 3.1.4 The Original Flatfile Code
    2. 3.2 An Analysis of the Code
      1. 3.2.1 Sorted Data?
      2. 3.2.2 A Simple but Inefficient Sorting Algorithm
      3. 3.2.3 Searching Through a List
    3. 3.3 A Foreshadowing of Things to Come
      1. 3.3.1 Effective Sorting Techniques
      2. 3.3.2 Effective Search Techniques and Data Structures for Maintaining Priority
      3. 3.3.3 Static Versus Dynamic Storage Structures
      4. 3.3.4 Generic and Abstract Classes
      5. 3.3.5 Arrays Versus ArrayLists
    4. 3.4 Binary Search: Our First Mature Algorithm
    5. 3.5 Summary
    6. 3.6 Exercises
  10. Chapter 4 Arrays and Linked Lists
    1. 4.1 Arrays and ArrayLists
    2. 4.2 Linked Lists
      1. 4.2.1 Linked Lists and Pointers
      2. 4.2.2 A Linked List Class
      3. 4.2.3 Exception Handling
      4. 4.2.4 Linked Lists Using Arrays
      5. 4.2.5 Arrays, ArrayLists, and the Free List
    3. 4.3 Insertionsort
    4. 4.4 Summary
    5. 4.5 Exercises
  11. Chapter 5 Generics, Collections, and Testing
    1. 5.1 Using Generics for the Data Payload
    2. 5.2 Objects and Equality
    3. 5.3 The Java LinkedList
    4. 5.4 Iterators
      1. 5.4.1 The Justification for Iterators
    5. 5.5 Implementing Our Very Own Collection
    6. 5.6 Testing with JUnit
    7. 5.7 Reflection
    8. 5.8 Summary
    9. 5.9 Exercises
  12. Chapter 6 Estimating Asymptotic Efficiency
    1. 6.1 Analysis of Algorithms
      1. 6.1.1 The Definition of a “Logarithm”
      2. 6.1.2 A Few Comments about the Real World
    2. 6.2 Some Rigor
      1. 6.2.1 An Apology for Some Audacity
      2. 6.2.2 Basic Orders of Magnitude, and Some Intuition
      3. 6.2.3 Constants Don’t Matter
      4. 6.2.4 Constant Startup Costs Don’t Matter
      5. 6.2.5 Big Oh Is Transitive
      6. 6.2.6 All Logarithms Are the Same
      7. 6.2.7 All Polynomials of the Same Degree Are the Same
      8. 6.2.8 All Reasonable Cost-of-Work Functions Go Off to Infinity
    3. 6.3 Some More Rigor
      1. 6.3.1 Little oh
      2. 6.3.2 Big Theta, and Some More Simplifying Theorems
      3. 6.3.3 Ignoring Fencepost Issues
      4. 6.3.4 Basic Orders of Magnitude Revisited
    4. 6.4 More Intuition—Common Asymptotics
    5. *6.5 Exponential Orders of Magnitude
      1. 6.5.1 Exponential Orders of Magnitude
    6. *6.6 Big Omega
      1. 6.6.1 Traditional Big Omega (Hardy,about 1915)
      2. 6.6.2 Knuth’s Big Omega (Knuth,about 1975)
    7. 6.7 What Do We Count?
    8. 6.8 Binary Divide and Conquer Is Optimal
    9. 6.9 Summary
    10. 6.10 Exercises
  13. Chapter 7 Stacks and Queues
    1. 7.1 Stacks
      1. 7.1.1 Exception Handling
      2. 7.1.2 Stacks Using Nodes
      3. 7.1.3 Stacks Using Arrays
      4. 7.1.4 Reverse Polish Arithmetic
    2. 7.2 HTML/XML and Stacks
    3. 7.3 Queues
      1. 7.3.1 Queues Using Nodes
      2. 7.3.2 Queues Using Arrays
    4. 7.4 The JCF Classes
      1. 7.4.1 The JCF Stack
      2. 7.4.2 The JCF Queue
      3. 7.4.3 Stacks, Queues, and Deques
    5. 7.5 Priority Queues
      1. 7.5.1 The Heap
      2. 7.5.2 Creating a Heap
      3. 7.5.3 Maintaining the Heap
    6. 7.6 Summary
    7. 7.7 Exercises
  14. Chapter 8 Recursion
    1. 8.1 Factorials and Fibonacci Numbers
    2. 8.2 The Collatz Problem
    3. 8.3 Greatest Common Divisor
    4. 8.4 The Ackermann Function
    5. 8.5 Binary Divide-and-Conquer Algorithms
    6. 8.6 Permutations and Combinations
    7. 8.7 Gaming and Searching Applications
    8. 8.8 Implementation Issues
    9. 8.9 Summary
    10. 8.10 Exercises
  15. Chapter 9 A First Look at Graphs
    1. 9.1 Formal Notions of a Graph
    2. 9.2 Examples of Graphs
    3. 9.3 Transitive Closure
      1. 9.3.1 Facebook Graphs
      2. 9.3.2 Theory
      3. 9.3.3 Applications in Computing
    4. 9.4 Local–Global Questions
    5. 9.5 Greedy Algorithms
    6. 9.6 Summary
    7. 9.7 Exercises
  16. Chapter 10 Trees
    1. 10.1 Trees
    2. 10.2 Spanning Trees
    3. 10.3 Data Structures for Trees
    4. 10.4 Binary Trees
      1. 10.4.1 Implementing Binary Trees with Nodes
      2. 10.4.2 Implementing Binary Trees with Arrays
    5. 10.5 The Heap
    6. 10.6 Traversing a Tree
      1. 10.6.1 Breadth-First and Depth-First Traversal
      2. 10.6.2 Traversal on Parallel Computers
    7. 10.7 Summary
    8. 10.8 Exercises
  17. Chapter 11 Sorting
    1. 11.1 Worst-Case, Best-Case, and Average-Case
    2. 11.2 Bubblesort
    3. 11.3 Insertionsort
    4. 11.4 Improving Bubblesort
    5. 11.5 Heapsort
    6. 11.6 Worst-Case, Best-Case, and Average-Case (Again)
    7. 11.7 Mergesort
      1. 11.7.1 Analysis of Mergesort
      2. 11.7.2 Disk-Based Sorting
    8. 11.8 Quicksort
      1. 11.8.1 The Quicksort Algorithm
      2. 11.8.2 Average-Case Running Time for Quicksort
    9. 11.9 Sorting Without Comparisons
    10. 11.10 Experimental Results
    11. 11.11 Auxiliary Space and Implementation Issues
      1. 11.11.1 Space Considerations
      2. 11.11.2 Memory
      3. 11.11.3 Multilevel Sorts
      4. 11.11.4 Stability
    12. 11.12 The Asymptotics of Sorting
      1. 11.12.1 Lower Bounds on Sorting
      2. 11.12.2 A Proof of Lower Bounds
      3. 11.12.3 Lower Bounds for the Average Case
    13. *11.13 Sorting in Parallel
      1. 11.13.1 Analysis
    14. 11.14 Summary
    15. 11.15 Exercises
  18. Chapter 12 Searching
    1. 12.1 Associative Matching
    2. 12.2 Indexing for Search
    3. 12.3 Binary Search Trees
      1. 12.3.1 Inorder Traversal and Binary Search Trees
      2. 12.3.2 Building a Binary Search Tree
    4. 12.4 Sophisticated Search Trees
    5. 12.5 Hashing
    6. 12.6 Random Numbers and Hash Functions: A Brief Digression
      1. 12.6.1 Random Numbers
      2. 12.6.2 Cryptographic Hash Functions
      3. 12.6.3 Random Numbers in Java
    7. 12.7 The Java Collections Framework
    8. 12.8 The Java HashSet
      1. 12.8.1 A Spell-Checking Program
    9. 12.9 The Java TreeMap
      1. 12.9.1 A Digression on Documentation
    10. 12.10 The Java TreeSet, HashMap, and LinkedList
    11. 12.11 Summary
    12. 12.12 Exercises
  19. Chapter 13 Graphs
    1. 13.1 Graphs and Applications
    2. 13.2 Adjacency Matrices and Linked Lists
      1. 13.2.1 Adjacency Matrices
      2. 13.2.2 Sparse Graphs and Sparse Matrices
      3. 13.2.3 Linked Lists for Sparse Graphs
      4. 13.2.4 A Middle Ground, Somewhat Helped by Java
    3. 13.3 Breadth-First and Depth-First Search
    4. 13.4 Graph Problems
      1. 13.4.1 NP-Completeness
      2. 13.4.2 Eulerian Cycles
      3. 13.4.3 Connected Components
      4. 13.4.4 Spanning Trees
      5. 13.4.5 Shortest Path
      6. 13.4.6 Hamiltonian Cycles
      7. 13.4.7 Traveling Salesman Problem
    5. 13.4.8 Cliques
    6. 13.5 Summary
    7. 13.6 Exercises
  20. Appendix A The Author’s Idiosyncrasies of Coding Style
    1. A.1 Utilities
    2. A.2 Log Files
    3. A.3 Labeling Trace Output
    4. A.4 Naming Conventions
    5. A.5 Use of this in Java
    6. A.6 Labeling Closing Braces
    7. A.7 Keep It Simple
    8. A.8 The Infamous Double Equals
  21. Appendix B File Utilities
    1. B.1 Header, Boilerplate, and a Log File
    2. B.2 Setting Up an Output PrintWriter File
    3. B.3 Setting Up an Input Scanner File
  22. Appendix C Glossary
    1. C.1 The Nature of Jargon
    2. C.2 Terms Used in This Book
  23. Index

Product information

  • Title: Data Structures Using Java
  • Author(s): Duncan A. Buell
  • Release date: December 2011
  • Publisher(s): Jones & Bartlett Learning
  • ISBN: 9781449628086