Intro to DSA Flashcards
what is a data structure?
a way of organizing, storing, and performing operations on data
record
ds that stores subitems. called fields, with a name associated with each subitem (typically found in databases)
array
ds stores an ordered list of items and is accessible by a positional index
linked list
- ds stores an ordered list of items in nodes
- each node stores data and has a pointer to next node
binary tree
ds where each node stores data and has up to two children (left and right child)
hash table
ds stores unordered items by mapping (or hashing) each item to a location in an array
max-heap
tree maintains simple property that node’s key is greater than or equal to node’s childrens’ keys
min-heap
tree maintains simple property that node’s key is less than or equal to node’s childrens’ keys
graph
ds for representing connections among items, and has vertices connected by edges
vertex in graph ds
represents an item in a graph
edge in graph ds
represents a connection between two vertices in a graph
algorithm
set of commands that must be followed for computer to perform calculations or solving a problem
characteristics of an algorithm
unambiguity, finiteness, well-defined inputs, well-defined outputs, effectiveness, feasibility, and language independence
abstract data type (adt)
data type described by predefined user operations
9 common ADTs
list, dynamic array, stack, queue, deque, bag, set, priority queue, dictionary (map)
ADT: list
holds ordered data
ex. array, linked list
ADT: dynamic array
holds ordered data and allows indexed access
ex. array
ADT: stack
items only inserted on or removed from top of stack
ex. linked list
ADT: dictionary (map)
associates or maps keys with values
ex. hash table, binary search tree
ADT: queue
items inserted at end of queue and removed from front of queue
ex. linked list
ADT: priority queue
each item has a priority and items with higher priority are closer to front of queue than items with lower priority
ex. heap
ADT: deque (pronounced “deck”)
items can be inserted and removed at both front and back
ex. linked list
ADT: bag
stores items and order does no matter and duplicate items are allowed
ex. array, linked list
ADT: set
for collection of distinct items
ex. binary search tree, hash table
huffman coding
common compression technique that assigns fewer bits to frequent items, using a binary tree
