- Forward


Data Storage and Structures
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • 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
An Analogous Situation
Back SMYC Forward
  • 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
An Analogous Situation (cont.)
Back SMYC Forward
  • The Setting:
    • Each order can consists of multiple items
    • Items can be different sizes
  • An Example with Two Customers:
    • warehouse_orders01
An Analogous Situation (cont.)
Back SMYC Forward
  • The Setting (cont.):
    • The warehouse is filled with a number of different bins
    • The dividers between the bins are removable
  • An Illustration:
    • warehouse_bins
An Analogous Situation (cont.)
Back SMYC Forward

Storing an Order for A

warehouse_storage01
An Analogous Situation (cont.)
Back SMYC Forward

Storing Orders for A and B

warehouse_storage02

An Order for C

warehouse_orders02
An Analogous Situation (cont.)
Back SMYC Forward
  • 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
An Analogous Situation (cont.)
Back SMYC Forward
  • 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:
    • warehouse_storage03
An Analogous Situation (cont.)
Back SMYC Forward
  • 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 Analogous Situation (cont.)
Back SMYC Forward

An Example of a Manifest

warehouse_manifest01
An Analogous Situation (cont.)
Back SMYC Forward
  • 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)
Organization/Storage of Data
Back SMYC Forward
  • 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
Using the Analogy
Back SMYC Forward
  • 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:
    • memory01
Structures that use Contiguous Locations
Back SMYC Forward
  • When We Know...
    • The size of each element
    • The number of elements
  • An Illustration:
    • memory_contiguous01
Structures that use Non-Contiguous Locations
Back SMYC Forward
  • 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
    • memory_irregular01
    • memory_irregular02
There's Always More to Learn
Back -