Computer Science 268: Introduction to Computer Programming (Java)

Study Guide

Unit 9

Chapter 9: Linked Data Structures and Recursion

The information in this chapter is considered to be an advanced Java programming topic. Therefore, this section of the textbook is not covered in the course.

Section 9.1 Recursion

• 9.1.1 Recursive Binary Search
• 9.1.2 Towers of Hanoi
• 9.1.3 A Recursive Sorting Algorithm
• 9.1.4 Blob Counting

Section 9.2 Linked Data Structures

• 9.2.1 Recursive Linking
• 9.2.2 Linked Lists
• 9.2.3 Basic Linked List Processing
• 9.2.4 Inserting into a Linked List
• 9.2.5 Deleting from a Linked List

Section 9.3 Stacks, Queues, and ADTs

• 9.3.1 Stacks
• 9.3.2 Queues
• 9.3.3 Postfix Expressions

Section 9.4 Binary Trees

• 9.4.1 Tree Traversal
• 9.4.2 Binary Sort Trees
• 9.4.3 Expression Trees

Section 9.5 A Simple Recursive Descent Parser

• 9.5.1 Backus-Naur Form
• 9.5.2 Recursive Descent Parsing
• 9.5.3 Building an Expression Tree