A data structure is encapsulation of data and relevant
operations. It is referred to as an
Abstract Data Type (ADT), signifying that the actual implementation
is left open, subject to satisfying the intended meaning of the
operations.
For the most part the exact data representation is not presented;
rather, all access to the data is through the operations.
The Java class is a perfect model for an ADT.
In addition to the encapsulation with accessibility via operations
only, the presentation of operations are in the modern
object-oriented fashion in which the data takes precedence over
the operation.
According to this definition, every Java class is a data structure.
However, classically, we have particular
interest in the classes which
are often termed to be part of the Java collections.
In Java terms these are contained in the
java.util package. In particular, they are
aggregate data structures typically representing unbounded
structures whose size is parameterized.
The focus of interest to this class is:
Building data structures.
what data to use
what operations are of interest
how to implement the operations
Comparing and contrasting the efficiency of different
implementations
Using data structures to solve difficult algorithmic problems.
There are many factors involved in these pursuits, but we can
often pin it down to three things:
Simplicity
Speed (run-time).
Space usage.
Simplicity
This really should be the first consideration. We say time is
money, but the "time" may be the amount of time you spend on
something, not the time it takes to execute.
KISS philosophy: Keep It Simple and Stupid
Always use the simplest data structure (dumbest?) first.
Try to get a working model.
Then build on the model, to make it faster, etc.
Don't spend time making something complex so as to
speed it up if it won't greatly improve the overall speed.
Keep in mind the utility and possible life-cycle of this code
so that you're not wasting your time.
Speed
This is the second consideration: try to improve the overall speed.
There are several considerations:
Profiling and tweaking. Try to speed up the most costly operations.
For example, in a database algorithm that involves disk and RAM
operations, the disc operations are at least 1000 times as
costly as the RAM operations, so we want to
focus on making the disc operations less costly.
If you identify some time-consuming operation, look for an
order-of-magnitude improvement, e.g., going from quadratic
time to linear time. This is difficult and involves
finding a better data structure and/or better algorithm.
Space efficiency
Advanced data structures usually require extra storage to
hold information about the structure which can be used for
efficient processing. Usually this features is considered
last, but in data-intensive data structures, say, for
a database, it is crucial.