■■ Linked lists: In a linked list, each item is given its own memory space
and can be placed anywhere in memory. Each item stores the memory
address of the next item (a link), and sometimes also a link to the previ-
ous item. This arrangement has the added flexibility of supporting the
quick addition or removal of an item because no memory needs to be
copied. To add or remove items in a linked list, the links in the items
that surround the item being added or removed must be changed to
reflect the new order of items. Linked lists address the weakness of
arrays with regard to inefficiencies when adding and removing items
by not placing items sequentially in memory. Of course, linked lists also
have their weaknesses. Because items are randomly scattered through-
out memory, there can be no quick access to individual items based on
their index. Also, linked lists are less efficient than arrays with regard to
memory utilization, because each list item must have one or two link
pointers, which use up precious memory.
■■ Trees: A tree is similar to a linked list in that memory is allocated sepa-
rately for each item in the list. The difference is in the logical arrange-
ment of the items: In a tree structure, items are arranged hierarchically,
which greatly simplifies the process of searching for an item. The root
item represents a median point in the list, and contains links to the two
halves of the tree (these are essentially branches): one branch links to
lower-valued items, while the other branch links to higher-valued
items. Like the root item, each item in the lower levels of the hierarchy
also has two links to lower nodes (unless it is the lowest item in the
hierarchy). This layout greatly simplifies the process of binary searching,
where with each iteration one eliminates one-half of the list in which it
is known that the item is not present. With a binary search, the number
of iterations required is very low because with each iteration the list
becomes about 50 percent shorter.Control Flow
In order to truly understand a program while reversing, you’ll almost always
have to decipher control flow statements and try to reconstruct the logic behind
those statements. Control flow statements are statements that affect the flow of
the program based on certain values and conditions. In high-level languages,
control flow statements come in the form of basic conditional blocks and loops,
which are translated into low-level control flow statements by the compiler.
Here is a brief overview of the basic high-level control flow constructs:
■■ Conditional blocks: Conditional code blocks are implemented in most
programming languages using the ifstatement. They allow for speci-
fying one or more condition that controls whether a block of code is
executed or not.32 Chapter 2