Data Storage and Structures

Data Storage and Structures
An Introduction

Computer Science Department

bernstdh@jmu.edu

Motivation

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

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.)

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

An Analogous Situation (cont.)

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

An Analogous Situation (cont.)

Storing an Order for A

An Analogous Situation (cont.)

Storing Orders for A and B

An Order for C

An Analogous Situation (cont.)

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.)

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:

An Analogous Situation (cont.)

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.)

An Example of a Manifest

An Analogous Situation (cont.)

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

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

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:

Structures that use Contiguous Locations

Structures that use Non-Contiguous Locations

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

There's Always More to Learn