Java Reference
In-Depth Information
4.1
Lists
We all have an intuitive understanding of what we mean by a “list.” Our first step is
to define precisely what is meant so that this intuitive understanding can eventually
be converted into a concrete data structure and its operations. The most important
concept related to lists is that of position. In other words, we perceive that there
is a first element in the list, a second element, and so on. We should view a list as
embodying the mathematical concepts of a sequence, as defined in Section 2.1.
We define a list to be a finite, ordered sequence of data items known as ele-
ments. “Ordered” in this definition means that each element has a position in the
list. (We will not use “ordered” in this context to mean that the list elements are
sorted by value.) Each list element has a data type. In the simple list implemen-
tations discussed in this chapter, all elements of the list have the same data type,
although there is no conceptual objection to lists whose elements have differing
data types if the application requires it (see Section 12.1). The operations defined
as part of the list ADT do not depend on the elemental data type. For example, the
list ADT can be used for lists of integers, lists of characters, lists of payroll records,
even lists of lists.
A list is said to be empty when it contains no elements. The number of ele-
ments currently stored is called the length of the list. The beginning of the list is
called the head, the end of the list is called the tail. There might or might not be
some relationship between the value of an element and its position in the list. For
example, sorted lists have their elements positioned in ascending order of value,
while unsorted lists have no particular relationship between element values and
positions. This section will consider only unsorted lists. Chapters 7 and 9 treat the
problems of how to create and search sorted lists efficiently.
When presenting the contents of a list, we use the same notation as was in-
troduced for sequences in Section 2.1. To be consistent with Java array indexing,
the first position on the list is denoted as 0. Thus, if there are n elements in the
list, they are given positions 0 through n 1 as ha
0
; a
1
; :::; a
n1
i. The subscript
indicates an element's position within the list. Using this notation, the empty list
would appear as hi.
Before selecting a list implementation, a program designer should first consider
what basic operations the implementation must support. Our common intuition
about lists tells us that a list should be able to grow and shrink in size as we insert
and remove elements. We should be able to insert and remove elements from any-
where in the list. We should be able to gain access to any element's value, either to
read it or to change it. We must be able to create and clear (or reinitialize) lists. It
is also convenient to access the next or previous element from the “current” one.
The next step is to define the ADT for a list object in terms of a set of operations
on that object. We will use the Java notation of an interface to formally define the
