Advanced Topics in Java Core Concepts in Data Structures

Advanced Topics in Java

Core Concepts in Data Structures

Noel Kalicharan

Advanced Topics in Java: Core Concepts in Data Structures Copyright © 2014 by Noel

Kalicharan This work is subject to copyright. All rights are reserved by the Publisher, whether the

whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of

illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and

transmission or information storage and retrieval, electronic adaptation, computer software, or by

similar or dissimilar methodology now known or hereafter developed. Exempted from this legal

reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied

specifically for the purpose of being entered and executed on a computer system, for exclusive use by

the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the

provisions of the Copyright Law of the Publisher’s location, in its current version, and permission for

use must always be obtained from Springer. Permissions for use may be obtained through RightsLink

at the Copyright Clearance Center. Violations are liable to prosecution under the respective Copyright

Law.

ISBN-13 (pbk): 978-1-4302-6619-8

ISBN-13 (electronic): 978-1-4302-6620-4

Trademarked names, logos, and images may appear in this book. Rather than use a trademark symbol

with every occurrence of a trademarked name, logo, or image we use the names, logos, and images

only in an editorial fashion and to the benefit of the trademark owner, with no intention of

infringement of the trademark.

The use in this publication of trade names, trademarks, service marks, and similar terms, even if they

are not identified as such, is not to be taken as an expression of opinion as to whether or not they are

subject to proprietary rights.

While the advice and information in this book are believed to be true and accurate at the date of

publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for

any errors or omissions that may be made. The publisher makes no warranty, express or implied, with

respect to the material contained herein.

President and Publisher: Paul Manning Lead Editor: Steve Anglin

Development Editor: James Markham Technical Reviewers: Jim Graham, Massimo

Nardone, and Manuel Jordan Editorial Board: Steve Anglin, Mark Beckner, Ewan

Buckingham, Gary Cornell, Louise Corrigan, Jim DeWolf, Jonathan Gennick, Jonathan

Hassell, Robert Hutchinson, Michelle Lowman, James Markham, Matthew Moodie, Jeff

Olson, Jeffrey Pepper, Douglas Pundick, Ben Renow-Clarke, Dominic Shakeshaft,

Gwenan Spearing, Matt Wade, Steve Weiss Coordinating Editor: Kevin Shea

Copy Editor: Kim Wimpsett

Compositor: SPi Global

Indexer: SPi Global

Artist: SPi Global

Cover Designer: Anna Ishchenko

Distributed to the book trade worldwide by Springer Science+Business Media New York, 233 Spring

Street, 6th Floor, New York, NY 10013. Phone 1-800-SPRINGER, fax (201) 348-4505, e-mail

[email protected], or visit www.springeronline.com. Apress Media, LLC

is a California LLC and the sole member (owner) is Springer Science + Business Media Finance Inc

(SSBM Finance Inc). SSBM Finance Inc is a Delaware corporation.

For information on translations, please e-mail [email protected], or visit www.apress.com.

Apress and friends of ED books may be purchased in bulk for academic, corporate, or promotional

use. eBook versions and licenses are also available for most titles. For more information, reference

our Special Bulk Sales–eBook Licensing web page at www.apress.com/bulk-sales.

Any source code or other supplementary material referenced by the author in this text is available to

readers at www.apress.com/. For detailed information about how to locate your book’s source

code, go to www.apress.com/source-code/.

To my children

Who have been a perennial source of joy, laughter, and friendship

The reliable, diligent, disciplined Anushka Nikita

and

The enigmatic, free-spirited, will-o’-the-wisp Saskia Anyara

Contents at a Glance

About the Author

About the Technical Reviewers

Preface

Chapter 1: Sorting, Searching, and Merging

Chapter 2: Introduction to Objects

Chapter 3: Linked Lists

Chapter 4: Stacks and Queues

Chapter 5: Recursion

Chapter 6: Random Numbers, Games, and Simulation

Chapter 7: Working with Files

Chapter 8: Introduction to Binary Trees

Chapter 9: Advanced Sorting

Chapter 10: Hashing

Index

Contents

About the Author

About the Technical Reviewers

Preface

Chapter 1: Sorting, Searching, and Merging

1.1 Sorting an Array: Selection Sort

1.1.1 Analysis of Selection Sort

1.2 Sorting an Array: Insertion Sort

1.2.1 Analysis of Insertion Sort

1.3 Inserting an Element in Place

1.4 Sorting a String Array

1.5 Sorting Parallel Arrays

1.6 Binary Search

1.7 Searching an Array of Strings

1.8 Example: Word Frequency Count

1.9 Merging Ordered Lists

1.9.1 Implementing the Merge

Chapter 2: Introduction to Objects

2.1 Objects

2.2 Defining Classes and Creating Objects

2.2.1 Access to Class and Instance Variables

2.2.2 Initializing Class and Instance Variables

2.3 Constructors

2.3.1 Overloading a Constructor

2.4 Data Encapsulation, Accessor, and Mutator Methods

2.4.1 An Improved Constructor

2.4.2 Accessor Methods

2.4.3 Mutator Methods

2.5 Printing an Object’s Data

2.5.1 Using an Instance Method (the Preferred Way)

2.5.2 Using a Static Method

2.5.3 Using the toString() Method

2.6 The Class Part

2.6.1 Testing the Class Part

2.7 How to Name Your Java Files

2.8 Working with Objects

2.8.1 Assigning an Object Variable to Another

2.8.2 Losing Access to an Object

2.8.3 Comparing Object Variables

2.9 The null Pointer

2.10 Passing an Object as an Argument

2.11 Array of Objects

2.11.1 Finding the Part with the Lowest Price

2.12 Searching an Array of Objects

2.13 Sorting an Array of Objects

2.14 Using a Class to Group Data: Word Frequency Count

2.15 How to Return More Than One Value: Voting

Chapter 3: Linked Lists

3.1 Defining Linked Lists

3.2 Basic Operations on a Linked List

3.2.1 Counting the Nodes in a Linked List

3.2.2 Searching a Linked List

3.2.3 Finding the Last Node in a Linked List

3.3 Building a Linked List: Adding a New Item at the Tail

3.4 Insertion Into a Linked List

3.5 Building a Linked List: Adding a New Item at the Head

3.6 Deletion from a Linked List

3.7 Building a Sorted Linked List

3.8 A Linked List Class

3.9 How to Organize Java Files

3.10 Expanding the LinkedList Class

3.11 Example: Palindrome

3.12 Saving a Linked List

3.13 Arrays vs. Linked Lists

3.14 Storing a Linked List Using Arrays

3.15 Merging Two Sorted Linked Lists

3.16 Circular and Two-Way Linked Lists

3.16.1 Circular Lists

3.16.2 Two-Way (Doubly Linked) Lists

Chapter 4: Stacks and Queues

4.1 Abstract Data Types

4.2 Stacks

4.2.1 Implementing a Stack Using an Array

4.2.2 Implementing a Stack Using a Linked List

4.3 A General Stack Type

4.3.1 Example: Convert from Decimal to Binary

4.4 How to Convert from Infix to Postfix

4.4.1 Evaluating an Arithmetic Expression

4.5 Queues

4.5.1 Implementing a Queue Using an Array

4.5.2 Implementing a Queue Using a Linked List

Chapter 5: Recursion

5.1 Recursive Definition

5.2 Writing Recursive Functions in Java

5.3 Converting a Decimal Number to Binary Using Recursion

5.4 Printing a Linked List in Reverse Order

5.5 Towers of Hanoi

5.6 Writing Power Functions

5.7 Merge Sort

5.8 Counting Organisms

5.9 Finding a Path Through a Maze

5.9.1 Writing the Program

Chapter 6: Random Numbers, Games, and Simulation

6.1 Random Numbers

6.2 Random and Pseudorandom Numbers

6.3 Generating Random Numbers by Computer

6.4 A Guessing Game

6.5 Drills in Addition

6.6 Nim

6.7 Nonuniform Distributions

6.7.1 Collecting Bottle Caps

6.8 Simulation of Real-Life Problems

6.9 Simulating a Queue

6.9.1 Programming the Simulation

6.10 Estimating Numerical Values Using Random Numbers

6.10.1 Estimating

6.10.2 Estimating π

Chapter 7: Working with Files

7.1 Input/Output in Java

7.2 Text and Binary Files

7.3 Internal vs. External File Name

7.4 Example: Comparing Two Files

7.5 The try . . . catch Construct

7.6 Input/Output for Binary File

7.6.1 DataOutputStream and DataInputStream

7.6.2 Binary File of Records

7.7 Random Access Files

7.8 Indexed Files

7.9 Updating a Random Access File

Chapter 8: Introduction to Binary Trees

8.1 Trees

8.2 Binary Trees

8.3 Traversing a Binary Tree

8.4 Representing a Binary Tree

8.5 Building a Binary Tree

8.6 Binary Search Trees

8.7 Building a Binary Search Tree

8.7.1 Example: Word Frequency Count

8.8 Building a Binary Tree with Parent Pointers

8.8.1 Building a Binary Search Tree with Parent Pointers

8.9 Level-Order Traversal

8.10 Some Useful Binary Tree Functions

8.11 Binary Search Tree Deletion

8.12 An Array as a Binary Tree Representation

Chapter 9: Advanced Sorting

9.1 Heapsort

9.1.1 Converting a Binary Tree into a Max-Heap

9.1.2 The Sorting Process

9.2 Building a Heap Using siftUp

9.3 Analysis of Heapsort

9.4 Heaps and Priority Queues

9.5 Sorting a List of Items with Quicksort

9.5.1 Another Way to Partition

9.5.2 Nonrecursive Quicksort

9.5.3 Finding the k

th Smallest Number

9.6 Shell (Diminishing Increment) Sort

Chapter 10: Hashing

10.1 Hashing Fundamentals

10.1.1 The Search and Insert Problem

10.2 Solving the Search and Insert Problem by Hashing

10.2.1 The Hash Function

10.2.2 Deleting an Item from a Hash Table

10.3 Resolving Collisions

10.3.1 Linear Probing

10.3.2 Quadratic Probing

10.3.3 Chaining

10.3.4 Linear Probing with Double Hashing

10.4 Example: Word Frequency Count

Index

About the Author

Dr. Noel Kalicharan is a senior lecturer in computer science at the University

of the West Indies (UWI) in St. Augustine, Trinidad. For more than 36 years, he

has taught programming courses to people at all levels, from children to senior

citizens. He has been teaching algorithms and programming, among other things,

at UWI since 1976.

In 1988, he developed and hosted a 26-program television series entitled

Computers: Bit by Bit. This series taught computer literacy and programming to

the general public. He is always looking for innovative ways to teach logical

thinking skills that go hand in hand with programming skills. His efforts resulted

in two games—BrainStorm! and Not Just Luck—which won him the Prime

Minister’s Award for Invention and Innovation in 2000 and 2002, respectively.

He has written 17 computing books and is a computer science author for

Cambridge University Press, which published his international successes,

Introduction to Computer Studies and C by Example. The C book has received

glowing reviews from readers from diverse countries such as Australia, Brazil,

Canada, France, India, and Scotland. Many rate it as having “the best treatment

of pointers,” one of the more difficult programming topics to master. Advanced

Topic in Java is written in a more leisurely style.

In 2010, Kalicharan was designated as a Trinidad & Tobago Icon in

In 2010, Kalicharan was designated as a Trinidad & Tobago Icon in

Computer Science by the National Institute for Higher Education, Research,

Science, and Technology (NIHERST). In 2011, he was bestowed with a National

Award, the Public Service Medal of Merit (Gold), for his contribution to

education. In 2012, he was given a life-time award for Excellence in Education

by the Ministry of Education of Trinidad & Tobago.

In 2012, he created a system called DigitalMath

(www.digitalmath.tt). DigitalMath is an ingenious way to do arithmetic

with your hands. With it, you can do addition, subtraction, multiplication, and

division quickly, accurately, and with confidence, using just your fingers.

Born in Lengua Village in Princes Town, Trinidad, he received his primary

education at the Lengua Presbyterian School and his secondary education at

Naparima College. He is a graduate of the University of the West Indies in

Jamaica, the University of British Columbia in Canada, and the University of the

West Indies in Trinidad