• Almost all applications require a large number of entities
• We may or may not know a lot about the number and nature of these elements before the application is executed
• The organization/storage of the entities will depend on what we do and do not know

• Why Use an Analogy?
  • The data storage problem is fairly conceptual
  • It often helps to consider a physical analogue
• The Physical Analogue:
  • A warehouse containing outgoing orders

• The Setting:
  • Each order can consists of multiple items
  • Items can be different sizes
• An Example with Two Customers:
  • 

• The Setting (cont.):
  • The warehouse is filled with a number of different bins
  • The dividers between the bins are removable
• An Illustration:
  • 

Storing an Order for A

Storing Orders for A and B

An Order for C

• A Problem:
  • This order cannot be stored contiguously without moving the other orders around
  • It is fairly expensive to move items
• A Solution: Break the Order into Pieces
  • They can place an arrow with a number on it in any bin
  • The arrow is used to indicate that this order continues in another bin

• Continuing with the Example:
  • Place two "small" items in bins 3 and 4
  • Place an "arrow" in bin 5 indicating the order continues in bin 11
  • Place two "large" items in bins 11-14
• An Illustration:
  • 

• A Problem:
  • As the warehouse gets full, it becomes increasingly difficult to keep track of orders
• A Solution: A Manifest
  • When an order is placed in contiguous bins the manifest shows the first bin and the number of bins in the order
  • When the order is broken into pieces, the manifest contains the location of the bin containing the first part of the order

An Example of a Manifest

• The number of items is known but the specifics of each item (e.g., the size) are not
  • Leaving enough space in the manifest for all of the different pieces of the order but don't fill in the location and bin requirements
• The specifics of each item (e.g., the size) are known, but the number of items is not
  • Guess at the number of items and leave enough bins to handle that number
  • If more bins are required, the "arrows" can be used to locate the remainder of the order
• Nothing is known about the order
  • The order will probably need to be stored in a large number of pieces (using the "arrows" to keep track of the pieces)

• Data Structures:
  • Used to organize the storage and retrieval of data values
  • A realization in computer memory of a set of values
• Contents of Data Structures:
  • Homogeneous (i.e., identical) elements
  • Heterogeneous (i.e., different) elements

• The Important Observations:
  • Random access memory (RAM) and "permanent" memory stores (e.g., disks) have many of the properties of the warehouse
  • Each element (i.e., int, float) to be stored has a size (in bytes)
  • The "manifest" from the warehouse example is analogous to named variables
• Memory as a Sequence of Bytes:
  • 

• When We Know...
  • The size of each element
  • The number of elements
• An Illustration:
  • 

• When We Don't Know...
  • Either the number of elements
  • Or the size of the elements
• An Illustration:
  • Suppose use the first four bytes to store the size/compositionn of the element and the last four bytes to store the address of the next element
  • 
  •