A Concise Introduction to Data Structures using Java

Book description

Designed for a CS2 data structures course, this text provides a thorough but concise overview of data structures as well as a gradual introduction to Java. It uses a concise style and includes pseudocode and exercises throughout so that students learn how to write code, rather than just read it. The book covers all of the main areas taught in CS2 courses, including arrays, lists, stacks, queues, recursion, maps, and trees.

Table of contents

  1. Preliminaries
  2. Series
  3. Dedication
  4. Preface
    1. To Instructors
    2. Feedback
    3. Acknowledgments
  5. About the Author
  6. Chapter 1 A Brief Introduction to Java
    1. 1.1 Basics
      1. Classes
      2. Types and Variables
      3. Primitive and Reference Types
      4. Primitive Types
      5. Operators
      6. Increment and Decrement
      7. Statements and Blocks
      8. Assignment
      9. Control Statements
      10. If Statements
      11. While Loops
      12. For Loops
      13. Switch
      14. Output Statements
      15. Methods
      16. Comments
      17. Compiling and Running Java Programs
    2. 1.2 Strings
      1. Concatenation
      2. String Methods
      3. Comparing Strings
    3. 1.3 Arrays
      1. Declaring Array References
      2. Creating Arrays
      3. Accessing Array Elements
      4. Enhanced For-Loop
      5. Linear Search
    4. 1.4 Using Objects
      1. Declaring Object References
      2. Creating Objects
      3. Accessing Fields and Calling Methods
      4. Object References
      5. Using equals()
      6. Destroying Objects
      7. StringBuilders
      8. String Tokenizing
    5. 1.5 Writing Classes
      1. Class Definitions
      2. Visibility
      3. Declaring and Initializing Fields
      4. Writing Methods
      5. Writing Constructors
      6. Overloading Methods and Constructors
      7. Instance and Static Methods
      8. Calling Static Methods from Other Classes
      9. Instance and Static Fields
      10. toString() Methods
      1. Listing 1.1
      2. Listing 1.2
      3. Listing 1.3
      4. Listing 1.4
      5. Listing 1.5
      1. Table 1.1
      2. Table 1.2
      3. Table 1.3
      4. Table 1.4
      5. Table 1.5
      6. Table 1.6
      7. Table 1.7
  7. Chapter 2 Algorithm Analysis
    1. 2.1 Big-O Notation
      1. Big-O Notation
      2. What to Count
      3. Best, Worst, and Average Case
      4. Performance Measurement
    2. 2.2 Sorting: Insertion Sort
      1. Insertion Sort
      2. Implementation
      3. Worst-Case Analysis
      4. Generating Random Data
      5. Using Java Libraries
    3. 2.3 Searching: Binary Search
      1. Implementation
      2. Sample Trace
      3. Analysis of Binary Search
      1. Listing 2.1
      2. Listing 2.2
      3. Listing 2.3
      1. Table 2.1
      2. Table 2.2
      3. Table 2.3
  8. Chapter 3 Integer Stacks
    1. 3.1 Stack Interface
      1. Abstract Data Types
      2. Java Interfaces
      3. Interface Types
      4. Classes Implement Interfaces
      5. Programming to Interfaces
    2. 3.2 Array Implementation
      1. Throwing Exceptions
      2. Resizing the Array
    3. 3.3 Linked Implementation
      1. Linked Lists
      2. Nodes
      3. Insertion at Front
      4. Deletion at Front
      5. Linked Implementation
      6. Nested Classes
      7. Null Pointer Exceptions
      1. Listing 3.1
      2. Listing 3.2
      3. Listing 3.3
      4. Listing 3.4
      1. Table 3.1
      2. Table 3.2
  9. Chapter 4 Generic Stacks
    1. 4.1 Generic Types
      1. Type Parameters
      2. Generic Stack ADT
      3. Type Parameters Inside Interface and Class Definitions
      4. Type Arguments
      5. Wrapper Classes
      6. Automatic Boxing and Unboxing
      7. Creating Generic Objects
    2. 4.2 Generic Stack Implementations
      1. Generic Nested Classes
      2. Generic Arrays
      3. Unchecked Casts
      4. Obsolete References
      5. Generic Array Stack
    3. 4.3 Evaluating Expressions: Background
      1. Binary Operations
      2. Prefix, Infix, and Postfix
      3. Evaluating Postfix Algorithm
      4. Infix to Postfix Algorithm
    4. 4.4 Evaluating Expressions: Implementations
      1. Operator Precedence
      2. toPostfix() Implementation
      3. Using Conditional Boolean Expressions
      4. evalPostfix() Implementation
      1. Listing 4.1
      2. Listing 4.2
      3. Listing 4.3
      4. Listing 4.4
      5. Listing 4.5
      6. Listing 4.6
      7. Listing 4.7
      1. Table 4.1
      2. Table 4.2
      3. Table 4.3
      4. Table 4.4
      5. Table 4.5
  10. Chapter 5 Queues
    1. 5.1 Interface and Linked Implementation
      1. Queue ADT
      2. Linked Implementation
      3. Insertion After a Node
      4. Deletion After a Node
      5. Managing the Tail
    2. 5.2 Array Implementation
      1. Basic Idea
      2. Problem: Drift
      3. Circular Array
      4. Resizing Circular Arrays
    3. 5.3 Inheritance: Fixed-Length Queues
      1. Examples: GPUs and Network Routers
      2. Inheritance
      3. Inheritance Hierarchies
      4. Is-A and Has-A Relationships
      5. Implementation
      6. Java Class Extensions
      7. Subclass Constructors
      8. Overriding Methods
      9. Protected Fields in the Superclass
      10. The Object Class
    4. Project: Fixed-Length Queue Simulation
      1. Model
      2. Clock-Based Simulations
      3. Random Tasks
      1. Listing 5.1
      2. Listing 5.2
      3. Listing 5.3
      4. Listing 5.4
      1. Table 5.1
      2. Table 5.2
      3. Table 5.3
  11. 6 Lists
    1. 6.1 Interface
      1. List Indexing
      2. List ADT
      3. Shifting
      4. Overloading Methods
      5. Arrays and Lists
    2. 6.2 Array Implementation
      1. Index Checking
      2. Shifting in an ArrayList
    3. 6.3 Linked Implementation
      1. Dummy Nodes
      2. Double Links
      3. Deletion with Double Links
      4. Traversals
      5. Indexed Access
      6. Performance
      7. Using Nodes and References
    4. 6.4 Iterators
      1. Iterators
      2. Iterables
      3. Linked List Iterator
      4. Privacy Issues
      5. Inner Classes
      6. Extending Interfaces
      7. Using Iterators
      1. Listing 6.1
      2. Listing 6.2
      3. Listing 6.3
      1. Table 6.1
      2. Table 6.2
      3. Table 6.3
  12. Chapter 7 Recursion
    1. 7.1 Mathematical Functions
      1. Recursive Functions in Java
      2. Tracing Recursive Calls
      3. Natural Recursions
    2. 7.2 Visualizing Recursion
      1. Recursive Call Trees
      2. Analyzing Recursive Functions
      3. Implementing Recursion
      4. Function Call Stack
      5. Visualizing the Call Stack
      6. Stack Traces
    3. 7.3 Recursive and Generalized Searches
      1. Public Wrapper Methods
      2. Generalized Linear Search: Objects
      3. Generalized Binary Search: Comparables
      4. Generic Methods
      5. Integer[] and int[]
    4. 7.4 Applications
      1. Longest Common Subsequence
      2. Towers of Hanoi
      3. Backtracking
      1. Listing 7.1
      2. Listing 7.2
      3. Listing 7.3
      4. Listing 7.4
      5. Listing 7.5
      1. Table 7.1
  13. Chapter 8 Trees
    1. 8.1 Definitions and Examples
      1. Expression Trees
      2. Binary Search Trees
      3. Representing General Trees as Binary Trees
    2. 8.2 Traversals
      1. Depth-First
      2. Breadth-First
    3. 8.3 Binary Tree Abstract Class
      1. Abstract Classes
      2. Binary Tree Class
      3. Project: A Collection Hierarchy
      1. Listing 8.1
      2. Listing 8.2
      1. Table 8.1
  14. Chapter 9 Binary Search Trees
    1. 9.1 Queries
      1. Search
      2. Minimum and Maximum
      3. Predecessor and Successor
      4. Conditional Operator
      5. Performance
    2. 9.2 Insertion
      1. Java Assertions
    3. 9.3 Deletion
      1. Deleting By Hand
      2. Nodes without Two Children
    4. 9.4 Performance
      1. Unsorted Lists
      2. Sorted Lists
      3. Binary Search Trees
      1. Listing 9.1
      2. Listing 9.2
      3. Listing 9.3
      4. Listing 9.4
      1. Table 9.1
  15. Chapter 10 Heaps
    1. 10.1 Priority Queue Interface and Array-Based Heaps
      1. Priority Queue Interface
      2. Heap Data Structure
      3. Complete Binary Trees
      4. Array-Based Binary Trees
      5. Parents and Children
      6. Generic Arrays of Comparable Elements
    2. 10.2 Insertion and Deletion
      1. Insertion and Heapifying Up
      2. Deletion
      3. Heapifying Down
    3. 10.3 Buildheap and Heapsort
      1. Buildheap
      2. Buildheap Performance
      3. Heapsort
      4. Project: Event-Based Simulation
      5. Events
      6. Checkout Line Simulation
      7. Modeling Customer Arrivals: Poisson Processes
      8. Modeling Normal Distributions
      9. Design
      1. Listing 10.1
      2. Listing 10.2
      3. Listing 10.3
      4. Listing 10.4
      5. Listing 10.5
      1. Table 10.1
  16. Chapter 11 Hash Tables
    1. 11.1 Map Interface and Linked Implementation
      1. Maps
      2. Linked Map
      3. Map Entries
    2. 11.2 Hash Tables
      1. Direct Addressing
      2. Hash Tables
      3. Collisions
      4. Hash Functions
      5. Integer Keys
      6. String and Object Keys
      7. Java Hashcodes
    3. 11.3 Chaining
      1. Implementation
      2. Generic Arrays Revisited
      3. Performance
      4. Space-Time Tradeoff
      5. Deletion
    4. 11.4 Linear Probing
      1. Linear Probing
      2. Implementation
      3. Performance
      4. Deletion
      5. Other Probe Sequences
      1. Listing 11.1
      2. Listing 11.2
      1. Table 11.1
  17. Bibliography

Product information

  • Title: A Concise Introduction to Data Structures using Java
  • Author(s): Mark J. Johnson
  • Release date: November 2013
  • Publisher(s): Chapman and Hall/CRC
  • ISBN: 9781498759816