Programming Data Structures in Java Publisher/ISBN/Ordering Information Description of Book Program Examples from Book Solutions Manual for Book Preface Table of Contents

Book Information

Book Description

Each chapter provides further support for students with: example programs, illustrations, chapter summaries and exercises. All of the examples classes used in the textbook are also available on the web.

Preface to Programming Data Structures in Java (First Edition)

Prerequisites

Overview

The list of chapter titles outlines the arrangement of materials.

1. Getting Started
2. Basic Java Programming Constructs
3. Java Class Libraries
4. Searching Algorithms: Correctness and Efficiency
5. Data Abstraction
6. Stacks
7. Sets
8. Queues
9. Priority Queues and Dictionaries
10. Advanced Object-Oriented Concepts
11. Recursion
12. Trees
13. Advanced Trees
14. Graphs
15. Sorting Algorithms
16. Concurrency and Exceptions
17. Advanced GUIs and Animation

Chapter 2 is mostly review for those who have already completed an introductory course using the Java programming language. It concentrates on Java language constructs and classes from the java.lang package.

Chapter 3 reviews many of the classes of the Java Class Libraries, in particular those used to implement graphical user interfaces in applets and Java applications. As well, use of the Graphics class is summarized.

Chapter 4 introduces fundamental material on searching algorithms and program correctness. Big O notation is also introduced. The algorithms covered are: order n and log n searches (serial and binary searches); as well as order n2 and n log n sorts (bubble and merge sorts).

Chapter 5 examines data structures and data abstraction. It provides a carefully developed abstract data type (an address book). This chapter emphasizes mechanisms and motivation for information hiding.

Chapter 6 through 9 use the ideas developed in Chapter 5 to introduce standard data abstractions, such as stacks, queues, and sets along with data structures to represent them. With most data abstractions, an extensive example of a typical usage is developed. For example, an expression evaluator uses the stack, and a bank simulation uses the queue. This approach is taken to ensure that the student understands an abstraction and its usual implementations, and also gains a good feel for the practical utility of the abstraction. The examples developed in these chapters typically consist of a number of reusable classes implementing the abstractions. These examples serve as case studies and allow further emphasis of software engineering ideas.

Chapter 10 concentrates on the higher concepts of object-oriented programming. These include abstract classes, class hierarchies, genericity, and Java interfaces. Object-oriented analysis is emphasized. The chapter also deals with the realities of programming in Java such as resource constraints and trade-offs between resource usage and program flexibility.

Chapter 11 gives standard examples of recursion and prepares the student for the use of recursion in manipulating data structures such as trees.

Chapter 12 introduces trees, their common implementations, and their common uses. This chapter uses a binary search tree example. Multiple implementations are examined along with their performance.

Chapter 13 contains advanced material on trees. It covers AVL trees in depth and examines multiple methods of tree traversal.

Chapter 14 introduces graphs with their basic algorithms, abstractions, and uses. This chapter begins with traversals of different implementations of graphs and continues to the implementation of a hypertext system.

Chapter 15 returns to the subject of sorting, and surveys basic sorting methods. These methods include: exchange sorts, heap sort, quicksort, merge sort, radix sort, and sorting with files.

Chapter 16 examines the issue of concurrency in general with examples such as producer-consumer programs and its use in Java-specific contexts such as lengthy responses to button presses. The second half of the chapter covers exceptions.

Chapter 17 provides additional detail for students wishing to write more complex Java applets and applications. It covers dialog boxes, loading images, using scrollbars, advanced animation using off-screen bitmaps, and printing.

Flexibility

This book provides only an introduction to program correctness, so the instructor may choose to add extra material on this subject. A good insertion point for this material is just after Chapter 4, or just after Chapter 11.

This book covers linked lists chapter by chapter, as the need for using the various kinds of linking arises. Chapters 2, 5, 6, 8, and 9 introduce linked lists with this organization:

2. Basic Programming Constructs

Java Classes for linked nodes.

5. Data Abstraction

Linearly linked lists, used to implement an address book.

6. Stacks

Linearly linked lists, used to implement a stack.

8. Queues

Linearly linked lists, used to implement a queue. Front and rear links for linked lists.

9. Priority Queues and Dictionaries

Linearly linked lists, used to implement a priority queue. Circularly linked lists, used to implement a dictionary. Doubly linked lists, used to implement a dictionary. Sentinel nodes in a linked list. Linearly linked lists, used to implement hashing buckets.

An instructor may prefer to present this material on linked lists as a unit. A good insertion point for this unit would be just after Chapter 3. Alternatively, a summary unit on this material would fit well at the end of Chapter 9.

Recursion is introduced as one of the basic programming constructs covered in Chapter 2. Chapter 6 covers the relationship between recursion and stacks. Chapter 11 concentrates on recursion. Chapters 12 and 13 make extensive use of recursion as it relates to trees. Instructors who wish to emphasize recursion may wish to introduce a unit on this subject. A good insertion point for this unit would be just before or after Chapter 6.

The Java Programming Language

The language is portable; it can be used on any computer platform that has a Java interpreter. This means that software developers can confidently program in Java and know that their software will run on any such computer. As well, individuals can also share applets via the Web. Attempts are made to make the use of shared programs safe. For security, for example, no applet may read from or write to a file on the system on which it is being executed.

Java syntax is based on the C syntax but many of the difficult and error prone parts of C and C++, such as pointers, operator overloading, and multiple inheritance have been eliminated. In this book we have eliminated still more of the "tricks" that some C programmers delight in. Our approach is based on the fundamental principle of structured programming, namely keeping programs easy to understand.

Java and its class libraries have many additional features which are not part of C or C++. It provides for strings, graphics, concurrency, and exception handling, as well as a large number of data structures in its class libraries. Java also provides graphical user interface classes.

All of these features contribute to Java's attractiveness as both a commercial software tool and a means of addressing the core computer science concepts.

Example Programs

Contacts

Table of Contents of Programming Data Structures in Java