ADTs Flashcards
Name 9 ADTs
- Queue
- Stack
- List
- Arrays
- Linked Lists
- Hash Tables
- Graphs
- Trees
- Binary Trees
What is a Queue’s priority
FiFo
What is a Stack’s priority
LiFo
What is Static and Dynamic
Static - Fixed size e.g. arrays
Dynamic - Variable sized e.g. Lists
What are the parts of linked lists
There are 2 parts
Data (can be complex data structure)
Pointer (index of next node)
What is Encapsulation
To hide data from users. To hide inner workings of program.
What is Overflow
Trying to push to a full stack
What is underflow
Trying to pop from an empty stack
What is a Call Stack
Provides a system for passing parameters and return addresses to subroutines
What are the functions for adding to and removing from a Queue
enQueue(item)
deQueue()
What are the functions for adding to and removing from a stack
Push(item)
Pop()
What are the functions to check if a stack or queue is full or empty
IsFull()
IsEmpty()
What is the function to view whats on top of the stack
Peek()
What’s the function to return the num of items on a stack
size()
What is a Hash table
Uses a hashing algorithm to find data quickly
Each record is assigned a unique address
Collision occurs if addresses are the same, they are remade if this happens
What function is in most hashing algorithms
MOD by number of slots. The remainder is the address
What is a collision
Keys that generate the same address for different primary keys, referred to as synonyms