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