1.4 Abstract Data Types (ADTs)

8.24.26 ZyBook and Class Review

What does ADT stand for?

Abstract Data Type

What is an Abstract Data Type (ADT)?

A data type described by the operations it provides without specifying how those operations are implemented.

What does an ADT focus on?

What operations can be performed on the data rather than how those operations are implemented.

What does an ADT hide?

The underlying implementation details.

What does an ADT provide to the programmer?

A well-defined interface of operations for interacting with the data.

Can the same ADT have different implementations?

Yes. An ADT can be implemented using different underlying data structures.

Does a programmer need to know the underlying implementation to use an ADT?

No

Does the underlying implementation of an ADT matter?

Yes, when analyzing or improving runtime efficiency.

What is the difference between and ADT and a data structure?

An ADT describes what operations are available; a data structure describes how the data is actually organized and stored.

What is a common example of an ADT?

A List

What operations might a List ADT provide?

Append, remove, search, and print.

What are two common data structures used to implement a List ADT?

An array and a linked list.

What does a List ADT hold?

Ordered data

What does “ordered” mean for a List ADT?

The items maintain an order based on how they are added/stored.

What happens when you append 55, 88, and 66 to an empty list?

The list becomes 55, 88, 66

What happens when you perform Append(list, 11), Append(list, 4), and Append(list, 7)?

The list becomes 11, 4, 7

What happens when you remove item 2 from a list containing 2, 20, 30?

The list becomes 20, 30.

Can a List ADT be implemented using an array?

Yes

Can a List ADT be implemented using a linked list?

Yes

Does the programmer need to know whether a List uses an array or linked list?

No

Does the underlying data structure of a List affect program execution?

Yes. Different implementations can have different efficiency.

What is the main idea behind the List ADT example with an array and linked list?

Both implementations provide the same List interface even though they store the data differently.