Data Structures Flashcards
Primitives
int, float, byte, etc. All built from bits.
Basic types used to build software
Primitives
Byte
8 bits, 0-255
Half a byte
Nybble, Hex
Integer types
Short (2B), Int (4B), Long (8B)
Short integer
2 bytes
int Integer
4 bytes
Long integer
8 bytes
Hex
Half-byte, 0-f
Memory location
Pages on physical memory/RAM (frames), or on disk/ROM
Frame
Page in physical memory
Page Replacement steps
Find page on disk, find empty/victim frame, write victim frame to disk if dirty, bring new page into memory, update frame table
FIFO
First-in-first-out, replace oldest page first
LRU
Least-recently-used, replace page that was called on the longest ago
Page vs. Frame
Frame is the storage unit/location in memory, page is the stuff being store
array indexing directions
row / column
Array lookup
Super fast, but modifying the array sucks
Linked Lists
Every node references next node. Lookups are slow, but modifying the list is easy.
Queue
FIFO, built from arrays or lists
Stack
LIFO, built from arrays or lists
Queue terminology
Enqueue, dequeue, remove
Stack terminology
Push, pop, empty
Operational Ceiling
Limit before failure
Limit before failure
Operational Ceiling
Linear/Serial Search
O(n), starts at one end and moves down the line
Binary Search
O(log n), divide at midpoint & repeat, needs ordered list
Search starts at one end and moves down the line
Linear/Serial Search
Search divides at midpoint & repeat, needs ordered list
Binary Search
Hash Function
Maps a key (name) to an integer index of a hash table array / bucket. O(1) ideally, O(n) in practice. Calculates the key based on the data that’s being stored.
Collision
Multiple keys mapping to the same index–can be resolved by having the bucket itself being a collection, moving shit to the next open spot (open addressing), or using a perfect hash function instead.
Multiple keys mapping to the same index
Collision
If collision, slapping data in the next free index of the hash table.
Open Addressing
Open Addressing
When mapping new key, if there’s a collision, just go down the indices until you find a free space. When doing a lookup, the hash function will still return the original index, so you just go down the indices until you find what you’re looking for, or find an empty spot.
Where shit is stored in hashing
Buckets
Bubble Sort
Compare [0] and [1], swap if needed, compare [1] and [2], etc. Then start again, up to len-1, etc. O(n^2)
Compare [0] and [1], swap if needed, compare [1] and [2], etc. Then start again, up to len-1, etc. O(n^2)
Bubble Sort
Insertion Sort
Make new list, and go down line of original list, placing things into new list in order. O(n^2)
Make new list, and go down line of original list, placing things into new list in order. O(n^2)
Insertion Sort
Selection Sort
Find min element and move to start, find 2nd to min element and move it into next spot, etc. O(n^2)
Find min element and move to start, find 2nd to min element and move it into next spot, etc. O(n^2)
Selection Sort
Quicksort
Select pivot, move smaller elements to the left and bigger to the right, then pivot on those two list, etc. O(n log n)
Select pivot, move smaller elements to the left and bigger to the right, then pivot on those two list, etc. O(n log n)
Quicksort
