you have a sufficient understanding of the individual fields. This process will
be demonstrated in the reversing chapters in the second part of this book.
Lists
Other than user-defined data structures, programs routinely use a variety of
generic data structures for organizing their data. Most of these generic data
structures represent lists of items (where each item can be of any type, from a
simple integer to a complex user-defined data structure). A list is simply a
group of data items that share the same data type and that the program views
as belonging to the same group. In most cases, individual list entries contain
unique information while sharing a common data layout. Examples include
lists such as a list of contacts in an organizer program or list of e-mail messages
in an e-mail program. Those are the user-visible lists, but most programs will
also maintain a variety of user-invisible lists that manage such things as areas
in memory currently active, files currently open for access, and the like.
The way in which lists are laid out in memory is a significant design deci-
sion for software engineers and usually depends on the contents of the items
and what kinds of operations are performed on the list. The expected number
of items is also a deciding factor in choosing the list’s format. For example, lists
that are expected to have thousands or millions of items might be laid out dif-
ferently than lists that can only grow to a couple of dozens of items. Also, in
some lists the order of the items is critical, and new items are constantly added
and removed from specific locations in the middle of the list. Other lists aren’t
sensitive to the specific position of each item. Another criterion is the ability to
efficiently search for items and quickly access them. The following is a brief
discussion of the common lists found in the average program:
■■ Arrays: Arrays are the most basic and intuitive list layout—items are
placed sequentially in memory one after the other. Items are referenced
by the code using their index number, which is just the number of items
from the beginning of the list to the item in question. There are also
multidimensional arrays, which can be visualized as multilevel arrays.
For example, a two-dimensional array can be visualized as a simple
table with rows and columns, where each reference to the table requires
the use of two position indicators: row and column. The most signifi-
cant downside of arrays is the difficulty of adding and removing items
in the middle of the list. Doing that requires that the second half of the
array (any items that come afterthe item we’re adding or removing) be
copied to make room for the new item or eliminate the empty slot pre-
viously occupied by an item. With very large lists, this can be an
extremely inefficient operation.Low-Level Software 31