0.Course Introduction§

Content Goals for this Course

Reinforce the concept that costs and benefits exist for every data structure.
Learn the commonly used data structures.
- These form a programmer’s basic data structure “toolkit”.
Understand how to measure the cost of a data structure or program.
- These techniques also allow you to judge the merits of new data structures that you or others might invent.

Costs and Benefits

Each data structure has costs and benefits.
- Rarely is one data structure better than another in all situations.
- We talk about a lot of data structures and algorithms that have stood the test of time.
Any data structure requires:
- space for each data item it stores,
- time to perform each basic operation,
- programming effort.
Only after a careful analysis of problem characteristics can we know the best data structure for a task.

Data Structure: Definition

A data structure is the physical implementation of an ADT.
- Each operation associated with the ADT is implemented by one or more subroutines in the implementation.
Data structure usually refers to an organization for data in main memory.
File structure: an organization for data on peripheral storage, such as a disk drive.

Logical vs. Physical Form

Data items have both a logical and a physical form.
Logical form: definition of the data item as an ADT.
- Ex: Integers in mathematical sense: operators +, -
Physical form: implementation of the data item within a data structure.
- Ex: 32/64 bit integers, overflow.

Logical vs. Physical Form (2)

Data Type

ADT

Type

Operations

Data Items

Logical Form

Data Structure

Storage Space

Subroutines

Data Items

Physical Form