Java Reference
In-Depth Information
12
Lists and Arrays Revisited
Simple lists and arrays are the right tools for the many applications. Other situa-
tions require support for operations that cannot be implemented efficiently by the
standard list representations of Chapter 4. This chapter presents a range of topics,
whose unifying thread is that the data structures included are all list- or array-like.
These structures overcome some of the problems of simple linked list and con-
tiguous array representations. This chapter also seeks to reinforce the concept of
logical representation versus physical implementation, as some of the “list” imple-
mentations have quite different organizations internally.
Section 12.1 describes a series of representations for multilists, which are lists
that may contain sublists. Section 12.2 discusses representations for implementing
sparse matrices, large matrices where most of the elements have zero values. Sec-
tion 12.3 discusses memory management techniques, which are essentially a way
of allocating variable-length sections from a large array.
12.1
Multilists
Recall from Chapter 4 that a list is a finite, ordered sequence of items of the form
hx
0
;x
1
;:::;x
n1
i where n 0. We can represent the empty list by
null
or hi.
In Chapter 4 we assumed that all list elements had the same data type. In this
section, we extend the definition of lists to allow elements to be arbitrary in nature.
In general, list elements are one of two types.
1. An atom, which is a data record of some type such as a number, symbol, or
string.
2. Another list, which is called a sublist.
A list containing sublists will be written as
hx1;hy1;ha1; a2i; y3i;hz1; z2i; x4i:
405
