Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

Data Structures and Algorithms in Java (2nd Edition)

by Robert Lafore (Author)

Data Structures and Algorithms in Java (2nd Edition) Cover 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.

Focus Theory Implementation  
Level Elementary Intermediate Advanced
Language Java    

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