Data Structures and Abstract Data Types

Flashcards reviewing key concepts of data structures and abstract data types.

Abstract Data Type (ADT)

The facilities and functionality. What it does.

Data Structure

The data structure employed by the ADT. How it does what it does.

Implementation

The implementation of the data structure. How it is stored and manipulated.

Queue

An ordered collection of items which are added at one end, called the “tail,” and removed from the other end, called the “head”.

Queue()

Creates a new queue that is empty.

enqueue(item)

Adds a new item to the tail of the queue.

dequeue()

If not empty, removes the front item from the queue.

isEmpty()

Tests to see whether the queue is empty.

size()

Counts the number of items in the queue.

Why is it called “abstract”?

The definition of an ADT only mentions what operations can be performed but not how these operations will be implemented.

Data structure

The physical representation of the structure of the data being stored in memory.

Abstract data type

Both the data structure and the procedures/functions which manipulate that data structure.

Encapsulation

The only way the user can interact with a variable of that ADT is through an interface, a set of procedures that operate on the data structure.

“Strong” encapsulation

Details of how the data structure is actually stored can be completely hidden from the user.

Which language offers encapsulation?

Java

Upper bound (upb)

Index of the last element

Lower bound (lwb)

Index of the first element

Abstract data types (ADTs)

Emphasize the user’s point of view