38 Javanotes 9.0, Chapter 9 — Linked Data Structures and Recursion
Chapter 9
Linked Data Structures and Recursion
In this chapter, we look at two advanced
programming techniques, recursion and linked data structures, and some of their
applications. Both of these techniques are related to the seemingly paradoxical
idea of defining something in terms of itself. This turns out to be a
remarkably powerful idea.
A subroutine is said to be recursive if it calls itself, either directly or
indirectly. What this means is that the subroutine is used in its own definition. Recursion
can often be used to solve complex problems by reducing them to simpler
problems of the same type.
A reference to one object can be stored in an instance variable of another
object. The objects are then said to be “linked.” Complex data structures can
be built by linking objects together. An especially interesting case occurs
when an object contains a link to another object that belongs to the same
class. In that case, the class is used in its own definition. Several important
types of data structures are built using classes of this kind.
Contents of Chapter 9:
- Section 1: Recursion
- Section 2: Linked Data Structures
- Section 3: Stacks, Queues, and ADTs
- Section 4: Binary Trees
- Section 5: A Simple Recursive Descent Parser
- Programming Exercises
- Quiz on This Chapter