Java Software Structures

John Lewis is an Associate Professor of Computer Science at Villanova University. He received his Ph.D. from Virginia Tech in 1991. Prof. Lewis' area of specialization is Software Engineering, with a particular focus on web-based software development. He regularly teaches courses in Object-Oriented Design, Software Engineering, and Algorithms & Data Structures. Prof. Lewis is a member of the Association for Computing Machinery (ACM), the IEEE Computer Society, and Sigma Xi, the scientific research society. He has won numerous teaching awards, and is active in the ACM's Special Interest Group on Computer Science Education (SIGCSE). Joe Chase is an Associate Professor of Computer Science and Chair of the Department of Information Technology at Radford University. He received his Ph.D. from Virginia Tech in 1994. Prof. Chase's areas of specialization include Computer Science Education, Software Engineering, with a particular focus on web-based software development, and Human-Computer Interaction. He regularly teaches courses in Software Engineering, Data Structures, and Analysis of Algorithms. Prof. Chase is a member of the Association for Computing Machinery (ACM), the IEEE Computer Society, and UPE. He is also active in the ACM's Special Interest Group on Computer Science Education (SIGCSE).

Preface.
I. FOUNDATIONS.



Introduction.

1. Software Engineering.


Software Development.



Software Quality.



Software Life Cycle Models.



The Unified Modeling Language (UML).



Error Handling.



Analysis of Algorithms.



Software Engineering and Data Structures.

2. Collections.


Collections.



A Bag Collection.



Using a Bag: Bingo.



Implementing a Bag: with Arrays.



Analysis of the Array Implementation of a Bag.

3. Linked Structures.


References as Links.



Managing Linked Lists.



Elements without Links.



Implementing a Bag: with Links.



Analysis of the Linked Implementation of a Bag.

4. Recursion.


Recursive Thinking.



Recursive Programming.



Using Recursion.



Analyzing Recursive Algorithms.

5. Sorting and Searching.


Searching.



Linear Search.



Binary Search.



Comparing Search Algorithms.



Sorting.



Selection Sort.



Insertion Sort.



Bubble Sort.



Quick Sort.



Merge Sort.

II. LINEAR DATA STRUCTURES.

Introduction.
6. Stacks.


A Stack ADT.



Using Stacks: Evaluating Postfix Expressions.



Using Stacks: Simulating Recursion.



Implementing Stacks: with Links.



Implementing Stacks: with Arrays.



Implementing Stacks: the java.util.Stack Class.



Analysis of Stack Implementations.

7. Queues.


A Queue ADT.



Using Queues: Code Keys.



Using Queues: Ticket Counter Simulation.



Using Queues: Radix Sort.



Implementing Queues: with Links.



Implementing Queues: with Arrays.



Implementing Queues: with Circular Arrays.



Analysis of Queue Implementations.

8. Lists.


A List ADT.



Using Ordered Lists: Tournament Maker.



Using Indexed Lists: The Josephus Problem.



Implementing Lists: with Arrays.



Implementing Lists: with Links.



Analysis of List Implementations.

III. NON-LINEAR DATA STRUCTURES.

9. Trees.


Trees.



Definitions.



Strategies for Implementing Trees.



Tree Traversals.



Implementing Binary Trees.



Using Binary Trees: Expression Trees.

10. Binary Search Trees.


A Binary Search Tree.



Implementing Binary Search Trees: with Links.



Using Binary Search Trees: Implementing Ordered Lists.



Balanced Binary Search Trees.



Implementing Binary Search Trees: AVL Trees.



Implementing Binary Search Trees: Red/Black Trees.



Implementing Binary Search Trees: The Java Collections API.

11. Heaps.


A Heap.



Using Heaps: Heap Sort.



Using Heaps: Priority Queues.



Implementing Heaps: with Links.



Implementing Heaps: with Arrays.



Analysis of Heap Implementations.

12. Multi-way Search Trees.


2-3 Trees.



2-4 Trees.



B-Trees.

13. Hashing.


A Hashing.



Hashing Functions.



Resolving Collisions.



Deleting Elements from a Hash Table.



Hash Tables in the Java Collections API.

14. Graphs.


Undirected Graphs.



Directed Graphs.



Networks.



Common Graph Algorithms.

Appendices.


Java Overview.



Introduction to GUIs in Java.



Java Class Descriptions.