Skip to main content
main-content
Top

About this book

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.

Table of Contents

Chapter 1. Sorting, Searching, and Merging

Abstract
In this chapter, we will explain the following:
  • How to sort a list of items using selection sort
  • How to sort a list of items using insertion sort
  • How to add a new item to a sorted list so that the list remains sorted
  • How to sort an array of strings
  • How to sort related (parallel) arrays
  • How to search a sorted list using binary search
  • How to search an array of strings
  • How to write a program to do a frequency count of words in a passage
  • How to merge two sorted lists to create one sorted list
Noel Kalicharan

Chapter 2. Introduction to Objects

Abstract
In this chapter, we will explain the following:
  • What is a class, an object, a field, and a method
  • That an object variable does not hold an object but, rather, a pointer (or reference) to where the object is actually located
  • The distinction between a class variable (also called a static variable) and an instance variable (also called a non-static variable)
  • The distinction between a class method (also called a static method) and an instance method (also called a non-static method)
  • What the access modifiers public, private, and protected mean
  • What is meant by information hiding
  • How to refer to class and instance variables
  • How to initialize class and instance variables
  • What is a constructor and how to write one
  • What is meant by overloading
  • What is meant by data encapsulation
  • How to write accessor and mutator methods
  • How to print an object’s data in various ways
  • Why the tostring() method is special in Java
  • What happens when we assign an object variable to another
  • What it means to compare one object variable with another
  • How to compare the contents of two objects
  • How a function can return more than one value using an object
Noel Kalicharan

Chapter 3. Linked Lists

Abstract
In this chapter, we will explain the following:
  • The notion of a linked list
  • How to write declarations for working with a linked list
  • How to count the nodes in a linked list
  • How to search for an item in a linked list
  • How to find the last node in a linked list
  • The difference between static storage and dynamic storage allocation
  • How to build a linked list by adding a new item at the end of the list
  • How to insert a node into a linked list
  • How to build a linked list by adding a new item at the head of the list
  • How to delete items from a linked list
  • How to build a linked list by adding a new item in such a way that the list is always sorted
  • How to organize your Java files
  • How to use linked lists to determine whether a phrase is a palindrome
  • How to save a linked list
  • The differences between using linked lists and arrays for storing a list of items
  • How to represent a linked list using arrays
  • How to merge two sorted linked lists
  • The concept of a circular list and a doubly linked list
Noel Kalicharan

Chapter 4. Stacks and Queues

Abstract
In this chapter, we will explain the following:
  • The notion of an abstract data type
  • What a stack is
  • How to implement a stack using an array
  • How to implement a stack using a linked list
  • How to create a header file for use by other programs
  • How to implement a stack for a general data type
  • How to convert an expression from infix to postfix
  • How to evaluate an arithmetic expression
  • What a queue is
  • How to implement a queue using an array
  • How to implement a queue using a linked list
Noel Kalicharan

Chapter 5. Recursion

Abstract
In this chapter, we will explain the following:
  • What a recursive definition is
  • How to write recursive functions in Java
  • How to convert from decimal to binary
  • How to print a linked list in reverse order
  • How to solve Towers of Hanoi
  • How to write an efficient power function
  • How to sort using merge sort
  • How to use recursion to keep track of pending subproblems
  • How to implement backtracking using recursion by finding a path through a maze
Noel Kalicharan

Chapter 6. Random Numbers, Games, and Simulation

Abstract
In this chapter, we will explain the following:
  • Random numbers
  • The difference between random and pseudorandom numbers
  • How to generate random numbers on a computer
  • How to write a program to play a guessing game
  • How to write a program to drill a user in arithmetic
  • How to write a program to play Nim
  • How to simulate the collection of bottle caps to spell a word
  • How to simulate queues in real-life situations
  • How to estimate numerical values using random numbers
Noel Kalicharan

Chapter 7. Working with Files

Abstract
In this chapter, we will explain the following:
  • The difference between text files and binary files
  • The difference between internal and external file names
  • How to write a program to compare two text files
  • The try...catch construct
  • How to perform input/output with binary files
  • How to work with a binary file of records
  • What are random access files
  • How to create and retrieve records from random access files
  • What are indexed files
  • How to update a random access file using an index
Noel Kalicharan

Chapter 8. Introduction to Binary Trees

Abstract
In this chapter, we will explain the following:
  • The difference between a tree and a binary tree
  • How to perform pre-order, in-order, and post-order traversals of a binary tree
  • How to represent a binary tree in a computer program
  • How to build a binary tree from given data
  • What a binary search tree is and how to build one
  • How to write a program to do a word-frequency count of words in a passage
  • How to use an array as a binary tree representation
  • How to write some recursive functions to obtain information about a binary tree
  • How to delete a node from a binary search tree
Noel Kalicharan

Chapter 9. Advanced Sorting

Abstract
In this chapter, we will explain the following:
  • What a heap is and how to perform heapsort using siftDown
  • How to build a heap using siftUp
  • How to analyze the performance of heapsort
  • How a heap can be used to implement a priority queue
  • How to sort a list of items using quicksort
  • How to find the kth smallest item in a list
  • How to sort a list of items using Shell (diminishing increment) sort
Noel Kalicharan

Chapter 10. Hashing

Abstract
In this chapter, we will explain the following:
  • The fundamental ideas on which hashing is based
  • How to solve the search and insert problem using hashing
  • How to delete an item from a hash table
  • How to resolve collisions using linear probing
  • How to resolve collisions using quadratic probing
  • How to resolve collisions using chaining
  • How to resolve collisions using linear probing with double hashing
  • How to link items in order using arrays
Noel Kalicharan
Additional information