Java Reference
In-Depth Information
Choosing the best data structures and algorithms for a particular task is one of the
keys to developing high-performance software.
Key
Point
A
data structure
is a collection of data organized in some fashion. The structure not only
stores data but also supports operations for accessing and manipulating the data.
In object-oriented thinking, a data structure, also known as a
container
or
container object
,
is an object that stores other objects, referred to as data or elements. To define a data structure
is essentially to define a class. The class for a data structure should use data fields to store data
and provide methods to support such operations as search, insertion, and deletion. To create a
data structure is therefore to create an instance from the class. You can then apply the methods
on the instance to manipulate the data structure, such as inserting an element into or deleting
an element from the data structure.
Section 11.11 introduced the
ArrayList
class, which is a data structure to store elements
in a list. Java provides several more data structures that can be used to organize and manipu-
late data efficiently. These are commonly known as
Java Collections Framework
. We will
introduce the applications of lists, vectors, stacks, queues, and priority queues in this chapter
and sets and maps in the next chapter. The implementation of these data structures will be
discussed in Chapters 24-27.
data structure
container
Java Collections Framework
The
Collection
interface defines the common operations for lists, vectors, stacks,
queues, priority queues, and sets.
Key
Point
The Java Collections Framework supports two types of containers:
One for storing a collection of elements is simply called a
collection
.
collection
■
The other, for storing key/value pairs, is called a
map
.
map
■
Maps are efficient data structures for quickly searching an element using a key. We will intro-
duce maps in the next chapter. Now we turn our attention to the following collections.
■
Set
s store a group of nonduplicate elements.
Set
■
List
s store an ordered collection of elements.
List
■
Stack
s store objects that are processed in a last-in, first-out fashion.
Stack
■
Queue
s store objects that are processed in a first-in, first-out fashion.
Queue
■
PriorityQueue
s store objects that are processed in the order of their priorities.
PriorityQueue
The common features of these collections are defined in the interfaces, and implementa-
tions are provided in concrete classes, as shown in Figure 20.1.
Note
All the interfaces and classes defined in the Java Collections Framework are grouped in
the
java.util
package.
Design Guide
The design of the Java Collections Framework is an excellent example of using interfaces,
abstract classes, and concrete classes. The interfaces define the framework. The abstract
classes provide partial implementation. The concrete classes implement the interfaces
with concrete data structures. Providing an abstract class that partially implements an
interface makes it convenient for the user to write the code. The user can simply define
Search WWH ::
Custom Search