You are previewing Advanced Topics in Java: Core Concepts in Data Structures.
O'Reilly logo
Advanced Topics in Java: Core Concepts in Data Structures

Book Description

Java is one of the most widely used programming languages today. It was first released by Sun Microsystems in 1995. Over the years, its popularity has grown to the point where it plays an important role in most of our lives. From laptops to data centers, game consoles to scientific supercomputers, cell phones to the Internet, Java is everywhere! There are tons of applications and heaps of websites that will not work unless you have Java installed, and more are created every day. And, of course, Java is used to power what has become the world's most dominant mobile platform, Android.

Advanced Topics In Java teaches the algorithms and concepts that any budding software developer should know. You'll delve into topics such as sorting, searching, merging, recursion, random numbers and simulation, among others. You will increase the range of problems you can solve when you learn how to create and manipulate versatile and popular data structures such as binary trees and hash tables.

This book assumes you have a working knowledge of basic programming concepts such as variables, constants, assignment, selection (if..else) and looping (while, for). It also assumes you are comfortable with writing functions and working with arrays. If you study this book carefully and do the exercises conscientiously, you would become a better and more agile software developer, more prepared to code today's applications - no matter the language.

What you'll learn

  • What are and how to use some advanced algorithms, implemented in Java

  • How to create, manipulate and use linked lists, stacks and queues

  • How to use random numbers to program games and simulations

  • How to work with files, binary trees and hash tables

  • Sophisticated sorting methods such as heapsort, quicksort and mergesort

  • How to implement all of the above in Java

Who this book is for

This book is for those with a working knowledge of basic software development topic concepts, such as variables, constants, assignment, selection (if..else) and looping (while, for). It also assumes you are comfortable with writing functions and working with arrays.

Table of Contents

  1. Title Page
  2. Dedication
  3. Contents at a Glance
  4. Contents
  5. About the Author
  6. About the Technical Reviewers
  7. Preface
  8. CHAPTER 1: Sorting, Searching, and Merging
    1. 1.1 Sorting an Array: Selection Sort
    2. 1.2 Sorting an Array: Insertion Sort
    3. 1.3 Inserting an Element in Place
    4. 1.4 Sorting a String Array
    5. 1.5 Sorting Parallel Arrays
    6. 1.6 Binary Search
    7. 1.7 Searching an Array of Strings
    8. 1.8 Example: Word Frequency Count
    9. 1.9 Merging Ordered Lists
  9. CHAPTER 2: Introduction to Objects
    1. 2.1 Objects
    2. 2.2 Defining Classes and Creating Objects
    3. 2.3 Constructors
    4. 2.4 Data Encapsulation, Accessor, and Mutator Methods
    5. 2.5 Printing an Object’s Data
    6. 2.6 The Class Part
    7. 2.7 How to Name Your Java Files
    8. 2.8 Working with Objects
    9. 2.9 The null Pointer
    10. 2.10 Passing an Object as an Argument
    11. 2.11 Array of Objects
    12. 2.12 Searching an Array of Objects
    13. 2.13 Sorting an Array of Objects
    14. 2.14 Using a Class to Group Data: Word Frequency Count
    15. 2.15 How to Return More Than One Value: Voting
  10. CHAPTER 3: Linked Lists
    1. 3.1 Defining Linked Lists
    2. 3.2 Basic Operations on a Linked List
    3. 3.3 Building a Linked List: Adding a New Item at the Tail
    4. 3.4 Insertion Into a Linked List
    5. 3.5 Building a Linked List: Adding a New Item at the Head
    6. 3.6 Deletion from a Linked List
    7. 3.7 Building a Sorted Linked List
    8. 3.8 A Linked List Class
    9. 3.9 How to Organize Java Files
    10. 3.10 Expanding the LinkedList Class
    11. 3.11 Example: Palindrome
    12. 3.12 Saving a Linked List
    13. 3.13 Arrays vs. Linked Lists
    14. 3.14 Storing a Linked List Using Arrays
    15. 3.15 Merging Two Sorted Linked Lists
    16. 3.16 Circular and Two-Way Linked Lists
  11. CHAPTER 4: Stacks and Queues
    1. 4.1 Abstract Data Types
    2. 4.2 Stacks
    3. 4.3 A General Stack Type
    4. 4.4 How to Convert from Infix to Postfix
    5. 4.5 Queues
  12. CHAPTER 5: Recursion
    1. 5.1 Recursive Definition
    2. 5.2 Writing Recursive Functions in Java
    3. 5.3 Converting a Decimal Number to Binary Using Recursion
    4. 5.4 Printing a Linked List in Reverse Order
    5. 5.5 Towers of Hanoi
    6. 5.6 Writing Power Functions
    7. 5.7 Merge Sort
    8. 5.8 Counting Organisms
    9. 5.9 Finding a Path Through a Maze
  13. CHAPTER 6: Random Numbers, Games, and Simulation
    1. 6.1 Random Numbers
    2. 6.2 Random and Pseudorandom Numbers
    3. 6.3 Generating Random Numbers by Computer
    4. 6.4 A Guessing Game
    5. 6.5 Drills in Addition
    6. 6.6 Nim
    7. 6.7 Nonuniform Distributions
    8. 6.8 Simulation of Real-Life Problems
    9. 6.9 Simulating a Queue
    10. 6.10 Estimating Numerical Values Using Random Numbers
  14. CHAPTER 7: Working with Files
    1. 7.1 Input/Output in Java
    2. 7.2 Text and Binary Files
    3. 7.3 Internal vs. External File Name
    4. 7.4 Example: Comparing Two Files
    5. 7.5 The try . . . catch Construct
    6. 7.6 Input/Output for Binary File
    7. 7.7 Random Access Files
    8. 7.8 Indexed Files
    9. 7.9 Updating a Random Access File
  15. CHAPTER 8: Introduction to Binary Trees
    1. 8.1 Trees
    2. 8.2 Binary Trees
    3. 8.3 Traversing a Binary Tree
    4. 8.4 Representing a Binary Tree
    5. 8.5 Building a Binary Tree
    6. 8.6 Binary Search Trees
    7. 8.7 Building a Binary Search Tree
    8. 8.8 Building a Binary Tree with Parent Pointers
    9. 8.9 Level-Order Traversal
    10. 8.10 Some Useful Binary Tree Functions
    11. 8.11 Binary Search Tree Deletion
    12. 8.12 An Array as a Binary Tree Representation
  16. CHAPTER 9: Advanced Sorting
    1. 9.1 Heapsort
    2. 9.2 Building a Heap Using siftUp
    3. 9.3 Analysis of Heapsort
    4. 9.4 Heaps and Priority Queues
    5. 9.5 Sorting a List of Items with Quicksort
    6. 9.6 Shell (Diminishing Increment) Sort
  17. CHAPTER 10: Hashing
    1. 10.1 Hashing Fundamentals
    2. 10.2 Solving the Search and Insert Problem by Hashing
    3. 10.3 Resolving Collisions
    4. 10.4 Example: Word Frequency Count
  18. Index