Java Reference
In-Depth Information
Because a sequence is linear, you are able to add a new object only at the beginning or at the end, or
insert a new object following a given object position in the sequence — after the fifth, say. Generally, you
can retrieve an object from a sequence in several ways. You can select the first or the last; you can get the
object at a given position — as in indexing an array; or you can search for an object identical to a given
object by checking all the objects in the sequence either backward or forward. You can also iterate through
the sequence backward or forward accessing each object in turn. You didn't implement all these capabilities
in the linked list class in Chapter 6, but you could have.
You have essentially the same options for deleting objects from a sequence as you have for retrieving
them; that is, you can remove the first or the last, you can delete the object at a particular position in the
sequence, or you can remove an object that is equal to a given object. Sequences have the facility to store
several copies of the same object at different places in the sequence. This is not true of all types of collec-
tions, as you already know from the outline of a set in the previous section.
A
stack
, which is a last-in, first-out (LIFO) storage mechanism, is also considered to be a sequence, as
is a
queue
, which is usually a first-in, first-out (FIFO) mechanism. The Java collections framework imple-
ments a range of different queues including a
priority queue
in which elements in the queue are ordered,
which implies that FIFO doesn't apply. The elements in a priority queue are in ascending sequence from the
head of the queue, so it's more a case of “lowest in, first out."
It's easy to see that a linked list can act as a stack because using the methods to add and remove objects at
the end of a list makes the list operate as a stack. Similarly, only adding objects by using the method to add
an object to the end of a linked list, and only retrieving objects from the head of the list, makes it operate as
a FIFO queue.
Maps
A
map
is rather different from a set or a sequence collection because each entry involves a pair of objects.
A map is sometimes referred to as a
dictionary
because of the way it works. Each object that is stored in a
map has an associated
key
object, and the object and its key are stored together as a pair. The key determines
where the object is stored in the map, and when you want to retrieve an object, you must supply its key —
so the key acts as the equivalent of a word that you look up in a regular dictionary.
Figure 14-3
shows how
a map works.
