Data Structures from Scratch Flashcards
What is RAM?
RAM is a (physical) data structure consisting of billions of shelves each of which holds 8 bits. Each shelf of 8 bits constitutes a byte of memory that is directly connected to the memory controller, which the CPU can access. Each byte is either on or off as indicated by a value of 0 or 1. Random access means that the CPU can access any position in constant time. Note that when a CPU asks for the contents of a particular addrress, it also recieves the contents of nearby addresses - all of which get cached.
How do binary digit systems work?
Computers only use 0 and 1, which restricts them to a binary number system described by powers of two. That is, the number 0001 = 1 since the rightmost position is 2^0 followed by 2^1, 2^2, and 2^3. This works for intense but floats require twice the storage - half to store the number and half to store the location of the decimal point. Negative numbers use the leftmost position to indicate sign (0 for positive).
What is the space and time complexity of operating on fixed-width integers?
Fixed-width integers are integers that are stored using constant memory (e.g., int32 can describe 2^32 different integers all of which use 32 bytes of memory); operations on fixed-width integers are usually O(1) inn time and space.
How are arrays stored and what is the cost?
Arrays use contiguous blocks of memory to store fixed-width data. Each element of the array takes 8 positions in memory if it is a 64 bit integer. The upside is fast access - O(1). The downside is every fixed memory use and the need for continuous stretches of free memory.
Why are dynamic arrays treated as though they have O(1) time cost?
Dynamic arrays must re-size themselves as items are appended and they run out of memory. Specifically, if a dynamic array runs out of room, it doubles is memory allocation and moves to an open area of memory with enough space - this is O(n). However, the array is now doubled in size, which gives a bunch of O(1) assignments so the overall cost is considered O(1).
What is a linked list?
A linked list consists of a series of non-contiguous nodes each made up of a data and a pointer to the location of the next node. In addition, there is a node consisting of pointers to the first and last nodes. Appending and prepending to a linked list is O(1) since you need only reassign the pointer of the last (or first) node along with the head or tail pointer. The downside is that access is no longer O(1) but rather O(i) where i is the number of steps you must take through the list.
What is a hash table?
A hash table consists of key-value pairs where the key or index is the actual data (e.g., a word, character, number, etc.) and the value is some statistic (typically a count) about that data. To create the keys, computers use hashing functions to map to addresses in RAM. To avoid hash collisions where multiple data points have the same address, linked lists can be stored as the value. Consequently, hash tables have a lookup time of O(1) but this can degrade to O(n) in the case of collisions but these are pretty rare.
