Basic Java Data Structures

last updated 1/19/07

Data

The representation of information in a manner suitable for communication or analysis by humans or machines

Data are the nouns of the programming world:

The objects that are manipulated

The information that is processed

Data Type

A category of data characterized by the supported elements of the category and the supported operations on those elements

A language's set of primitive types (Java's are byte, char, short, int, long, float, double, and boolean) are not sufficient, by themselves, for dealing with data that have many parts and complex interrelationships among those parts.

Data structures provide this ability.

Definitions

Atomic or primitive type: A data type whose elements are single, nondecomposable data items (as primitives in Java)

Composite type A data type whose elements are composed of multiple data items

Structured composite type An organized collection of components in which the organization determines the means of accessing individual data components or subsets of the collection

Type examples

Definitions

Data abstraction The separation of a data type’s logical properties from its implementation

Data encapsulation The separation of the representation of data from the applications that use the data at a logical level; a programming language feature that enforces information hiding

Abstract data type (ADT) A data type whose properties (domain and operations) are specified independently of any particular implementation

In effect, all Java built-in types are ADTs.

In addition to the built-in ADTs, Java programmers can use the Java class mechanism to build their own ADTs.

Data Structure A collection of data elements whose logical organization reflects a relationship among the elements

It is best to design data structures with ADTs.

Basic Operations on Encapsulated Data

A constructor is an operation that creates a new instance (object) of the data type.

Transformers (sometimes called mutators) are operations that change the state of one or more of the data values.

An observer (sometimes called an accessor) is an operation that allows us to observe the state of one or more of the data values with out changing them.

An iterator is an operation that allows us to process all the components in a data structure sequentially.

Data Levels of an ADT

Logical (or abstract) level: Abstract view of the data values (the domain) and the set of operations to manipulate them.

Application (or user) level: Here the application programmer uses the ADT to solve a problem.

Implementation level: A specific representation of the structure to hold the data items, and the coding of the operations in a programming language.

Communication between the Application (user) Level and Implementation Level

Across an "Abstraction Barrier":

Java’s Built-In Types

Type Taxonomy

Implementation Dependent Structures

As primitive (read as built in) structures provided by a programming language, you have arrays and objects that reference other objects as in linked links.

Implementation Independent Structures

These data structures are more abstractly discussed. They may be implemented with different underlying structures.

For example the stack and queue could be implemented either as a linked list or an array.

Basic Structuring Mechanisms

There are two basic structuring mechanisms provided in Java (and many other high level languages): arrays and references

References

Are memory addresses

Sometimes called "links", "addresses", or "pointers"

Java uses the reserved word null to indicate an “absence of reference” and is the default reference

A variable of a reference (non-primitive) type holds the address of the memory location that holds the value of the variable, rather than the value itself.

The Java Class Construct

Can be a mechanism for creating composite data types.

Is composed of named data fields (class and instance variables) and methods.

Is unstructured because the meaning is not dependent on the ordering of the members.

Records

When a class is used strictly to hold data and does not hide the data.

A record is a composite data type made up of a finite collection of not necessarily homogeneous elements called fields.

Accessing is done directly through a set of named field selectors.

Assignment Statement

Primitive Types versus Objects

Ramifications of Using References

Aliases—we have two names for the same object. But consider

Comparison of objects

Comparison of primitive and non

Parameter Passing

This is a form of assignment--from the calling code to the called method.

All Java arguments are "passed by value".

If the argument is a primitive type, a copy of the value (int, double, and so on) is passed to the method.

If it is a reference type, then the reference copied to the method, but the object is not copied!

Garbage Management

Garbage: The set of currently unreachable objects

Garbage collection: The process of finding all unreachable objects and deallocating their storage space

Deallocate: Return the storage space for an object to the pool of free memory so that it can be reallocated to new objects

Dynamic memory management: The allocation and deallocation of storage space as needed while an application is executing