Data structures Flashcards
Strong type
standard types, such as integer and character - provide the basis for all other types, and a fixed amount of memory is defined
Static types
require a fixed amount of memory, such as arrays (and sets), but not included in the pre-defined types - must be declared before use
Dynamic types
may be expanded given the limitation of available memory e.g. files and pointers -> lists, queues and trees
Queue
FIFO data structure - elements added only to end of queue and removed from front of queue
Circular queue
queue implemented within an array, where the first element of the array logically follows the last element
Priority queue
queue in which the highest-priority elements are removed first; within a priority queue, the earliest arrival is removed first
List
consists of a number of items in which the same item may occur more than once
Stack
LIFO data structure - used in calculations and to hold return addresses when subroutines are called
Hash table
a data structure that implements a dictionary or associative array
Collision
occurs when a hash function produces the same value for two or more keys -> cannot store two sets of data in the same location
Linear probing (open addressing)
places data in the next free position in hash table
Chaining (closed addressing)
uses linked lists, instead of storing actual data in the hash table
Mid-square method
first square item, extract a portion of the resulting digits, then perform mod to get an address
Folding method
divide item into equal-size piece, add pieces together, then perform mod to get an address
Dictionary
abstract data type that defines an unordered collection of data as a set of key-value pairs
