Java Reference
In-Depth Information
21.1
Introduction
21.2
Self-Referential Classes
21.3
Dynamic Memory Allocation
21.4
Linked Lists
21.4.1 Singly Linked Lists
21.4.2 Implementing a Generic
List
Class
21.4.3 Generic Classes
ListNode
and
List
21.4.4 Class
ListTest
21.4.5
List
Method
insertAtFront
21.4.6
List
Method
insertAtBack
21.4.7
List
Method
removeFromFront
21.4.8
List
Method
removeFromBack
21.4.9
List
Method
print
21.4.10 Creating Your Own Packages
21.5
Stacks
21.6
Queues
21.7
Trees
21.8
Wrap-Up
Summary | Self-Review Exercises | Answers to Self-Review Exercises | Exercises |
Special Section: Building Your Own Compiler
This chapter shows how to build
dynamic data structures
that grow and shrink at execu-
tion time.
Linked lists
are collections of data items “linked up in a chain”—insertions and
deletions can be made
anywhere
in a linked list.
Stacks
are important in compilers and op-
erating systems; insertions and deletions are made only at one end of a stack—its
top
.
Queues
represent waiting lines; insertions are made at the back (also referred to as the
tail
)
of a queue and deletions are made from the front (also referred to as the
head
).
Binary trees
facilitate high-speed searching and sorting of data, eliminating duplicate data items effi-
ciently, representing file-system directories, compiling expressions into machine language
and many other interesting applications.
We discuss each of these major data-structure types and implement programs that
create and manipulate them. We use classes, inheritance and composition to create them
for reusability and maintainability. We also explain how to organize classes into your own
packages to promote reuse. We include this chapter for computer-science and computer-
engineering students who need to know how to build linked data structures.
Software Engineering Observation 21.1
The vast majority of software developers should use the predefined generic collection classes
that we discussed in Chapter 16, rather than developing customized linked data structures.
Optional Online “Building Your Own Compiler” Project
If you feel ambitious, you might want to attempt the major project described in the special
section entitled Building Your Own Compiler, which we've posted online at
http://
www.deitel.com/books/jhtp10
.
You've been using a Java compiler to translate your Java
programs to bytecodes so that you could execute these programs. In this project, you'll ac-
tually build your own compiler. It will read statements written in a simple, yet powerful
high-level language similar to early versions of the popular language BASIC and translate
these statements into Simpletron Machine Language (SML) instructions—SML is the lan-
guage you learned in the Chapter 7 special section, Building Your Own Computer. Your
Simpletron Simulator program will then execute the SML program produced by your
compiler! Implementing this project by using an object-oriented approach will give you
an opportunity to exercise most of what you've learned in this topic. The special section
carefully walks you through the specifications of the high-level language and describes the
