Java Reference
In-Depth Information
Array-based lists are faster for random access by position. Positions can easily
be adjusted forwards or backwards by the
next
and
prev
methods. These opera-
tions always take (1) time. In contrast, singly linked lists have no explicit access
to the previous element, and access by position requires that we march down the
list from the front (or the current position) to the specified position. Both of these
operations require (n) time in the average and worst cases, if we assume that
each position on the list is equally likely to be accessed on any call to
prev
or
moveToPos
.
Given a pointer to a suitable location in the list, the
insert
and
remove
methods for linked lists require only (1) time. Array-based lists must shift the re-
mainder of the list up or down within the array. This requires (n) time in the aver-
age and worst cases. For many applications, the time to insert and delete elements
dominates all other operations. For this reason, linked lists are often preferred to
array-based lists.
When implementing the array-based list, an implementor could allow the size
of the array to grow and shrink depending on the number of elements that are
actually stored. This data structure is known as a dynamic array. Both the Java and
C
++
/STL
Vector
classes implement a dynamic array. Dynamic arrays allow the
programmer to get around the limitation on the standard array that its size cannot
be changed once the array has been created. This also means that space need not
be allocated to the dynamic array until it is to be used. The disadvantage of this
approach is that it takes time to deal with space adjustments on the array. Each time
the array grows in size, its contents must be copied. A good implementation of the
dynamic array will grow and shrink the array in such a way as to keep the overall
cost for a series of insert/delete operations relatively inexpensive, even though an
occasional insert/delete operation might be expensive. A simple rule of thumb is
to double the size of the array when it becomes full, and to cut the array size in
half when it becomes one quarter full. To analyze the overall cost of dynamic array
operations over time, we need to use a technique known as amortized analysis,
which is discussed in Section 14.3.
4.1.4
Element Implementations
List users must decide whether they wish to store a copy of any given element
on each list that contains it. For small elements such as an integer, this makes
sense. If the elements are payroll records, it might be desirable for the list node
to store a reference to the record rather than store a copy of the record itself. This
change would allow multiple list nodes (or other data structures) to point to the
same record, rather than make repeated copies of the record. Not only might this
save space, but it also means that a modification to an element's value is automati-
cally reflected at all locations where it is referenced. The disadvantage of storing a
pointer to each element is that the pointer requires space of its own. If elements are
