Abstract Data Types Flashcards
(9 cards)
What is a list in the context of ADTs?
A list is an ADT for holding ordered data.
Examples include array and linked list.
Define a dynamic array.
A dynamic array is an ADT for holding ordered data and allowing indexed access.
An example is a standard array.
What is a stack?
A stack is an ADT in which items are only inserted on or removed from the top of a stack.
It is typically implemented using a linked list.
Describe a queue.
A queue is an ADT in which items are inserted at the end of the queue and removed from the front of the queue.
This structure is often implemented using a linked list.
What is a deque?
A deque (pronounced ‘deck’) is an ADT in which items can be inserted and removed at both the front and back.
It is commonly implemented using a linked list.
Define a bag in terms of ADTs.
A bag is an ADT for storing items in which the order does not matter and duplicate items are allowed.
Examples include array and linked list implementations.
What is a set in the context of ADTs?
A set is an ADT for a collection of distinct items.
Implementations include binary search tree and hash table.
What characterizes a priority queue?
A priority queue is a queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority.
This structure is typically implemented using a heap.
Define a dictionary (map) in terms of ADTs.
A dictionary is an ADT that associates (or maps) keys with values.
Common implementations include hash table and binary search tree.
