Java Data Structures - Contents
A D V E R T I S E M E N T
Since you've looked at node based data structures,
and their flexibility, you might wonder why would we want to use anything else. Well,
sometimes, the situation comes where the standards are not enough. Where we need that
extra boost of performance, which is currently occupied by the Java's garbage collection.
In any environment, allocating and releasing memory
is slow! Most of the time, you should try to avoid the procedure, unless you really need
it (or it's not in a time critical loop). You certainly wouldn't want to allocate and/or
release memory every time you do anything to a list, or a binary tree. What can we do to
avoid the natural way? Plenty!
The most common way around these kinds of problems
is to use our own allocation technique, which is perfectly suited for our purposes, and
will generally be much faster than the current system's approach (but always make sure;
system techniques are quite fast as well).
Using our own allocation scheme does imply that
we'll have to restrict our selves, but most of the times (when you really need it), the
restriction is worth while. What we will be doing is simulating the allocation and release
of nodes, using an array of nodes, stored in a linked list fashion. It may seem complex,
but in reality, it's not.
This array of nodes, is usually referred to as the "Node
Pool" (we "catch" one when we need one, and "throw
it back" when we don't). I know, I know, I haven't been the same since that girl
on IRC has stolen my humor.
There are two considerations we should think about
before we start programming, however. These two are whether we want to make the node-pool
itself static or dynamic? Shall we allocate the node-pool with every new instance of the
object, or shall we just share one common node-pool for all the objects of that class?
These two approaches are both quite useful in
different situations. For example, when was the last time you've ever used more than 52
cards in a deck of cards? That implies that your deck of cards class may have no more than
52 cards at a time; a perfect candidate for a Node Pool! Inside your game, you have this
one class, which can only hold 52 cards, no more. Then again, what if your card game has
to have several decks? You might want to extend that a little more; like have a separate
deck for each deck! (am I making any sense?)
The reason I describe this deck of cards example is
a historical one; it was the first program I've ever used with Node Pools (long time ago;
in C++). The one static node-pool allows other instances of the class (inside the same
program) to know which cards are missing from this universal deck, and which are present.
On the other hand, if you have a local (non-static) node-pool, each deck handles it's own
cards, and non of the other decks know anything about it.
It is important to understand this concept, since it
makes a lot of sense <sometimes> (and will allow you to write robust code
that doesn't waste memory). Then again, sometimes it makes absolutely no sense to use a
node-pool at all!
The example we will design in the next few sections
will deal with a binary tree, which does not use dynamic memory when inserting (or
removing) nodes. It will have a non-static node-pool; meaning that you'll have to specify
the maximum number of elements when it's instantiated (create an instance of it). I
believe the example will be general enough for you to learn to apply node-pools in various
different situations. Since I've already showed how to use my own pComparable
for JDK 1.1 (or lower), this next example will deal only with JDK 1.2 java.lang.Comparable
interface for most purposes. (A java.lang.Comparable interface
is worth learning, since it's very useful; I only wonder why they haven't come up with
something similar earlier?)
Back to Table of Contents
A D V E R T I S E M E N T
|
Subscribe to SourceCodesWorld - Techies Talk |
|
Add to Favorites
Make Home Page
