Register

# 17.1. Data Structures and Algorithm Analysis Introduction¶

## 17.1.1. Introduction¶

### 17.1.1.1. Course Introduction¶

Goals of 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.

### 17.1.1.2. Costs and Benefits¶

• Each data structure has costs and benefits.
• Rarely is one data structure better than another in all situations.

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

### 17.1.1.3. Data Structure¶

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

### 17.1.1.4. Logical vs. Physical Form¶

• Data items have both a logical and a physical form.

• Logical form: definition of the data item within an ADT.

• Ex: Integers in mathematical sense: +, -

• Physical form: implementation of the data item within a data structure.

• Ex: 32/64 bit integers, overflow.