Data Structures and Algorithms in Java, 2nd Edition

Data Structures and Algorithms in Java, 2nd Edition

by Robert Lafore
Released September 2017
Publisher(s): Sams
ISBN: 9780134849775

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

Data Structures and Algorithms in Java, Second Edition is designed to be easy to read and understand although the topic itself is complicated. Algorithms are the procedures that software programs use to manipulate data structures. Besides clear and simple example programs, the author includes a workshop as a small demonstration program executable on a Web browser. The programs demonstrate in graphical form what data structures look like and how they operate. In the second edition, the program is rewritten to improve operation and clarify the algorithms, the example programs are revised to work with the latest version of the Java JDK, and questions and exercises will be added at the end of each chapter making the book even more useful.

Educational Supplement

Suggested solutions to the programming projects found at the end of each chapter are made available to instructors at recognized educational institutions. This educational supplement can be found at www.prenhall.com, in the Instructor Resource Center.

Table of contents

  1. Title Page
  2. Copyright Page
  3. Contents at a Glance
  4. Table of Contents
  5. About the Author
  6. Dedication Page
  7. Acknowledgments to the First Edition
  8. Acknowledgments to the Second Edition
  9. We Want to Hear from You!
  10. Introduction
    1. What’s New in the Second Edition
      1. Additional Topics
      2. End-of-Chapter Questions
      3. Experiments
      4. Programming Projects
    2. What This Book Is About
    3. What’s Different About This Book
      1. Easy to Understand
      2. Workshop Applets
      3. Java Example Code
    4. Who This Book Is For
    5. What You Need to Know Before You Read This Book
    6. The Software You Need to Use This Book
    7. How This Book Is Organized
    8. Enjoy Yourself!
  11. 1 Overview
    1. What Are Data Structures and Algorithms Good For?
      1. Real-World Data Storage
      2. Programmer’s Tools
      3. Real-World Modeling
    2. Overview of Data Structures
    3. Overview of Algorithms
    4. Some Definitions
      1. Database
      2. Record
      3. Field
      4. Key
    5. Object-Oriented Programming
      1. Problems with Procedural Languages
      2. Objects in a Nutshell
      3. A Runnable Object-Oriented Program
      4. Inheritance and Polymorphism
    6. Software Engineering
    7. Java for C++ Programmers
      1. No Pointers
      2. Overloaded Operators
      3. Primitive Variable Types
      4. Input/Output
    8. Java Library Data Structures
    9. Summary
    10. Questions
  12. 2 Arrays
    1. The Array Workshop Applet
      1. Insertion
      2. Searching
      3. Deletion
      4. The Duplicates Issue
      5. Not Too Swift
    2. The Basics of Arrays in Java
      1. Creating an Array
      2. Accessing Array Elements
      3. Initialization
      4. An Array Example
    3. Dividing a Program into Classes
      1. Classes LowArray and LowArrayApp
    4. Class Interfaces
      1. Not So Convenient
      2. Who’s Responsible for What?
      3. The highArray.java Example
      4. The User’s Life Made Easier
      5. Abstraction
    5. The Ordered Workshop Applet
      1. Linear Search
      2. Binary Search
    6. Java Code for an Ordered Array
      1. Binary Search with the find() Method
      2. The OrdArray Class
      3. Advantages of Ordered Arrays
    7. Logarithms
      1. The Equation
      2. The Opposite of Raising Two to a Power
    8. Storing Objects
      1. The Person Class
      2. The classDataArray.java Program
    9. Big O Notation
      1. Insertion in an Unordered Array: Constant
      2. Linear Search: Proportional to N
      3. Binary Search: Proportional to log(N)
      4. Don’t Need the Constant
    10. Why Not Use Arrays for Everything?
    11. Summary
    12. Questions
    13. Experiments
    14. Programming Projects
  13. 3 Simple Sorting
    1. How Would You Do It?
    2. Bubble Sort
      1. Bubble Sort on the Baseball Players
      2. The BubbleSort Workshop Applet
      3. Java Code for a Bubble Sort
      4. Invariants
      5. Efficiency of the Bubble Sort
    3. Selection Sort
      1. Selection Sort on the Baseball Players
      2. The SelectSort Workshop Applet
      3. Java Code for Selection Sort
      4. Invariant
      5. Efficiency of the Selection Sort
    4. Insertion Sort
      1. Insertion Sort on the Baseball Players
      2. The InsertSort Workshop Applet
      3. Java Code for Insertion Sort
      4. Invariants in the Insertion Sort
      5. Efficiency of the Insertion Sort
    5. Sorting Objects
      1. Java Code for Sorting Objects
      2. Lexicographical Comparisons
      3. Stability
    6. Comparing the Simple Sorts
    7. Summary
    8. Questions
    9. Experiments
    10. Programming Projects
  14. 4 Stacks and Queues
    1. A Different Kind of Structure
      1. Programmer’s Tools
      2. Restricted Access
      3. More Abstract
    2. Stacks
      1. The Postal Analogy
      2. The Stack Workshop Applet
      3. Java Code for a Stack
      4. Stack Example 1: Reversing a Word
      5. Stack Example 2: Delimiter Matching
      6. Efficiency of Stacks
    3. Queues
      1. The Queue Workshop Applet
      2. A Circular Queue
      3. Java Code for a Queue
      4. Efficiency of Queues
      5. Deques
    4. Priority Queues
      1. The PriorityQ Workshop Applet
      2. Java Code for a Priority Queue
      3. Efficiency of Priority Queues
    5. Parsing Arithmetic Expressions
      1. Postfix Notation
      2. Translating Infix to Postfix
      3. Evaluating Postfix Expressions
    6. Summary
    7. Questions
    8. Experiments
    9. Programming Projects
  15. 5 Linked Lists
    1. Links
      1. References and Basic Types
      2. Relationship, Not Position
    2. The LinkList Workshop Applet
      1. The Insert Button
      2. The Find Button
      3. The Delete Button
    3. A Simple Linked List
      1. The Link Class
      2. The LinkList Class
      3. The insertFirst() Method
      4. The deleteFirst() Method
      5. The displayList() Method
      6. The linkList.java Program
    4. Finding and Deleting Specified Links
      1. The find() Method
      2. The delete() Method
      3. Other Methods
    5. Double-Ended Lists
    6. Linked-List Efficiency
    7. Abstract Data Types
      1. A Stack Implemented by a Linked List
      2. A Queue Implemented by a Linked List
      3. Data Types and Abstraction
      4. ADT Lists
      5. ADTs as a Design Tool
    8. Sorted Lists
      1. Java Code to Insert an Item in a Sorted List
      2. The sortedList.java Program
      3. Efficiency of Sorted Linked Lists
      4. List Insertion Sort
    9. Doubly Linked Lists
      1. Traversal
      2. Insertion
      3. Deletion
      4. The doublyLinked.java Program
      5. Doubly Linked List as Basis for Deques
    10. Iterators
      1. A Reference in the List Itself?
      2. An Iterator Class
      3. Additional Iterator Features
      4. Iterator Methods
      5. The interIterator.java Program
      6. Where Does the Iterator Point?
      7. The atEnd() Method
      8. Iterative Operations
      9. Other Methods
    11. Summary
    12. Questions
    13. Experiments
    14. Programming Projects
  16. 6 Recursion
    1. Triangular Numbers
      1. Finding the nth Term Using a Loop
      2. Finding the nth Term Using Recursion
      3. The triangle.java Program
      4. What’s Really Happening?
      5. Characteristics of Recursive Methods
      6. Is Recursion Efficient?
      7. Mathematical Induction
    2. Factorials
    3. Anagrams
    4. A Recursive Binary Search
      1. Recursion Replaces the Loop
      2. Divide-and-Conquer Algorithms
    5. The Towers of Hanoi
      1. The Towers Workshop Applet
      2. Moving Subtrees
      3. The Recursive Algorithm
      4. The towers.java Program
    6. mergesort
      1. Merging Two Sorted Arrays
      2. Sorting by Merging
      3. The MergeSort Workshop Applet
      4. The mergeSort.java Program
      5. Efficiency of the mergesort
    7. Eliminating Recursion
      1. Recursion and Stacks
      2. Simulating a Recursive Method
      3. What Does This Prove?
    8. Some Interesting Recursive Applications
      1. Raising a Number to a Power
      2. The Knapsack Problem
      3. Combinations: Picking a Team
    9. Summary
    10. Questions
    11. Experiments
    12. Programming Projects
  17. 7 Advanced Sorting
    1. Shellsort
      1. Insertion Sort: Too Many Copies
      2. N-Sorting
      3. Diminishing Gaps
      4. The Shellsort Workshop Applet
      5. Java Code for the Shellsort
      6. Other Interval Sequences
      7. Efficiency of the Shellsort
    2. Partitioning
      1. The Partition Workshop Applet
      2. The partition.java Program
      3. The Partition Algorithm
      4. Efficiency of the Partition Algorithm
    3. Quicksort
      1. The Quicksort Algorithm
      2. Choosing a Pivot Value
      3. The QuickSort1 Workshop Applet
      4. Degenerates to O(N2) Performance
      5. Median-of-Three Partitioning
      6. Handling Small Partitions
      7. Removing Recursion
      8. Efficiency of Quicksort
    4. Radix Sort
      1. Algorithm for the Radix Sort
      2. Designing a Program
      3. Efficiency of the Radix Sort
    5. Summary
    6. Questions
    7. Experiments
    8. Programming Projects
  18. 8 Binary Trees
    1. Why Use Binary Trees?
      1. Slow Insertion in an Ordered Array
      2. Slow Searching in a Linked List
      3. Trees to the Rescue
      4. What Is a Tree?
    2. Tree Terminology
      1. Path
      2. Root
      3. Parent
      4. Child
      5. Leaf
      6. Subtree
      7. Visiting
      8. Traversing
      9. Levels
      10. Keys
      11. Binary Trees
    3. An Analogy
    4. How Do Binary Search Trees Work?
      1. The Binary Tree Workshop Applet
      2. Representing the Tree in Java Code
    5. Finding a Node
      1. Using the Workshop Applet to Find a Node
      2. Java Code for Finding a Node
      3. Tree Efficiency
    6. Inserting a Node
      1. Using the Workshop Applet to Insert a Node
      2. Java Code for Inserting a Node
    7. Traversing the Tree
      1. Inorder Traversal
      2. Java Code for Traversing
      3. Traversing a Three-Node Tree
      4. Traversing with the Workshop Applet
      5. Preorder and Postorder Traversals
    8. Finding Maximum and Minimum Values
    9. Deleting a Node
      1. Case 1: The Node to Be Deleted Has No Children
      2. Case 2: The Node to Be Deleted Has One Child
      3. Case 3: The Node to Be Deleted Has Two Children
    10. The Efficiency of Binary Trees
    11. Trees Represented as Arrays
    12. Duplicate Keys
    13. The Complete tree.java Program
    14. The Huffman Code
      1. Character Codes
      2. Decoding with the Huffman Tree
      3. Creating the Huffman Tree
      4. Coding the Message
      5. Creating the Huffman Code
    15. Summary
    16. Questions
    17. Experiments
    18. Programming Projects
  19. 9 Red-Black Trees
    1. Our Approach to the Discussion
      1. Conceptual
      2. Top-Down Insertion
    2. Balanced and Unbalanced Trees
      1. Degenerates to O(N)
      2. Balance to the Rescue
      3. Red-Black Tree Characteristics
      4. Fixing Rule Violations
    3. Using the RBTree Workshop Applet
      1. Clicking on a Node
      2. The Start Button
      3. The Ins Button
      4. The Del Button
      5. The Flip Button
      6. The RoL Button
      7. The RoR Button
      8. The R/B Button
      9. Text Messages
      10. Where’s the Find Button?
    4. Experimenting with the Workshop Applet
      1. Experiment 1: Inserting Two Red Nodes
      2. Experiment 2: Rotations
      3. Experiment 3: Color Flips
      4. Experiment 4: An Unbalanced Tree
      5. More Experiments
      6. The Red-Black Rules and Balanced Trees
      7. Null Children
    5. Rotations
      1. Simple Rotations
      2. The Weird Crossover Node
      3. Subtrees on the Move
      4. Human Beings Versus Computers
    6. Inserting a New Node
      1. Preview of the Insertion Process
      2. Color Flips on the Way Down
      3. Rotations After the Node Is Inserted
      4. Rotations on the Way Down
    7. Deletion
    8. The Efficiency of Red-Black Trees
    9. Red-Black Tree Implementation
    10. Other Balanced Trees
    11. Summary
    12. Questions
    13. Experiments
  20. 10 2-3-4 Trees and External Storage
    1. Introduction to 2-3-4 Trees
      1. What’s in a Name?
      2. 2-3-4 Tree Organization
      3. Searching a 2-3-4 Tree
      4. Insertion
      5. Node Splits
      6. Splitting the Root
      7. Splitting on the Way Down
    2. The Tree234 Workshop Applet
      1. The Fill Button
      2. The Find Button
      3. The Ins Button
      4. The Zoom Button
      5. Viewing Different Nodes
      6. Experiments
    3. Java Code for a 2-3-4 Tree
      1. The DataItem Class
      2. The Node Class
      3. The Tree234 Class
      4. The Tree234App Class
      5. The Complete tree234.java Program
    4. 2-3-4 Trees and Red-Black Trees
      1. Transformation from 2-3-4 to Red-Black
      2. Operational Equivalence
    5. Efficiency of 2-3-4 Trees
      1. Speed
      2. Storage Requirements
    6. 2-3 Trees
      1. Node Splits
      2. Implementation
    7. External Storage
      1. Accessing External Data
      2. Sequential Ordering
      3. B-Trees
      4. Indexing
      5. Complex Search Criteria
      6. Sorting External Files
    8. Summary
    9. Questions
    10. Experiments
    11. Programming Projects
  21. 11 Hash Tables
    1. Introduction to Hashing
      1. Employee Numbers as Keys
      2. A Dictionary
      3. Hashing
      4. Collisions
    2. Open Addressing
      1. Linear Probing
      2. Java Code for a Linear Probe Hash Table
      3. Quadratic Probing
      4. Double Hashing
    3. Separate Chaining
      1. The HashChain Workshop Applet
      2. Java Code for Separate Chaining
    4. Hash Functions
      1. Quick Computation
      2. Random Keys
      3. Non-Random Keys
      4. Hashing Strings
      5. Folding
    5. Hashing Efficiency
      1. Open Addressing
      2. Separate Chaining
      3. Open Addressing Versus Separate Chaining
    6. Hashing and External Storage
      1. Table of File Pointers
      2. Non-Full Blocks
      3. Full Blocks
    7. Summary
    8. Questions
    9. Experiments
    10. Programming Projects
  22. 12 Heaps
    1. Introduction to Heaps
      1. Priority Queues, Heaps, and ADTs
      2. Weakly Ordered
      3. Removal
      4. Insertion
      5. Not Really Swapped
    2. The Heap Workshop Applet
      1. The Fill Button
      2. The Change Button
      3. The Remove Button
      4. The Insert Button
    3. Java Code for Heaps
      1. Insertion
      2. Removal
      3. Key Change
      4. The Array Size
      5. The heap.java Program
      6. Expanding the Heap Array
      7. Efficiency of Heap Operations
    4. A Tree-based Heap
    5. Heapsort
      1. Trickling Down in Place
      2. Using the Same Array
      3. The heapSort.java Program
      4. The Efficiency of Heapsort
    6. Summary
    7. Questions
    8. Experiments
    9. Programming Projects
  23. 13 Graphs
    1. Introduction to Graphs
      1. Definitions
      2. Historical Note
      3. Representing a Graph in a Program
      4. Adding Vertices and Edges to a Graph
      5. The Graph Class
    2. Searches
      1. Depth-First Search
      2. Breadth-First Search
    3. Minimum Spanning Trees
      1. GraphN Workshop Applet
      2. Java Code for the Minimum Spanning Tree
      3. The mst.java Program
    4. Topological Sorting with Directed Graphs
      1. An Example: Course Prerequisites
      2. Directed Graphs
      3. Topological Sorting
      4. The GraphD Workshop Applet
      5. Cycles and Trees
      6. Java Code
    5. Connectivity in Directed Graphs
      1. The Connectivity Table
      2. Warshall’s Algorithm
      3. Implementation of Warshall’s Algorithm
    6. Summary
    7. Questions
    8. Experiments
    9. Programming Projects
  24. 14 Weighted Graphs
    1. Minimum Spanning Tree with Weighted Graphs
      1. An Example: Cable TV in the Jungle
      2. The GraphW Workshop Applet
      3. Send Out the Surveyors
      4. Creating the Algorithm
      5. Java Code
      6. The mstw.java Program
    2. The Shortest-Path Problem
      1. The Railroad Line
      2. Dijkstra’s Algorithm
      3. Agents and Train Rides
      4. Using the GraphDW Workshop Applet
      5. Java Code
      6. The path.java Program
    3. The All-Pairs Shortest-Path Problem
    4. Efficiency
    5. Intractable Problems
      1. The Knight’s Tour
      2. The Traveling Salesman Problem
      3. Hamiltonian Cycles
    6. Summary
    7. Questions
    8. Experiments
    9. Programming Projects
  25. 15 When to Use What
    1. General-Purpose Data Structures
      1. Speed and Algorithms
      2. Libraries
      3. Arrays
      4. Linked Lists
      5. Binary Search Trees
      6. Balanced Trees
      7. Hash Tables
      8. Comparing the General-Purpose Storage Structures
    2. Special-Purpose Data Structures
      1. Stack
      2. Queue
      3. Priority Queue
      4. Comparison of Special-Purpose Structures
    3. Sorting
    4. Graphs
    5. External Storage
      1. Sequential Storage
      2. Indexed Files
      3. B-trees
      4. Hashing
      5. Virtual Memory
    6. Onward
  26. A Running the Workshop Applets and Example Programs
    1. The Workshop Applets
    2. The Example Programs
    3. The Sun Microsystem’s Software Development Kit
      1. Command-line Programs
      2. Setting the Path
      3. Viewing the Workshop Applets
      4. Operating the Workshop Applets
      5. Running the Example Programs
      6. Compiling the Example Programs
      7. Editing the Source Code
      8. Terminating the Example Programs
    4. Multiple Class Files
    5. Other Development Systems
  27. B Further Reading
    1. Data Structures and Algorithms
    2. Object-Oriented Programming Languages
    3. Object-Oriented Design (OOD) and Software Engineering
  28. C Answers to Questions
    1. Chapter 1, Overview
      1. Answers to Questions
    2. Chapter 2, Arrays
      1. Answers to Questions
    3. Chapter 3, Simple Sorting
      1. Answers to Questions
    4. Chapter 4, Stacks and Queues
      1. Answers to Questions
    5. Chapter 5, Linked Lists
      1. Answers to Questions
    6. Chapter 6, Recursion
      1. Answers to Questions
    7. Chapter 7, Advanced Sorting
      1. Answers to Questions
    8. Chapter 8, Binary Trees
      1. Answers to Questions
    9. Chapter 9, Red-Black Trees
      1. Answers to Questions
    10. Chapter 10, 2-3-4 Trees and External Storage
      1. Answers to Questions
    11. Chapter 11, Hash Tables
      1. Answers to Questions
    12. Chapter 12, Heaps
      1. Answers to Questions
    13. Chapter 13, Graphs
      1. Answers to Questions
    14. Chapter 14, Weighted Graphs
      1. Answers to Questions
  29. Index

Product information

  • Title: Data Structures and Algorithms in Java, 2nd Edition
  • Author(s): Robert Lafore
  • Release date: September 2017
  • Publisher(s): Sams
  • ISBN: 9780134849775