Data Structures Flashcards
What is Big O Notation?
Big O notation is a way of writing this function to show how an algorithm scales with the size of its input.
What are common Big O Functions?
O(1) - Constant time. Always fast. Number of operations never grows with input size n.
O(n) - Linear time. Fine. Number of operations grows at the same rate of input size n.
O(n^2) - Quadratic time. Bad. Number of operations explodes as the input size n grows.
O(n!) - Factorial. Trash. Number of operations is astronomical if n isn’t tiny.
How do you calculate Big O for a statement?
If this statement were to run once, how many simple calculations would it take in terms of the size of the data sets being used.
How many times will this statement run worst-case, within the context of this function, in terms of the size n of the data sets being used?
Take the answers from steps i and ii, and multiply them together.
Drop any constant, so 2n becomes n or 3(n^2) becomes n^2. That is the Big O notation for this statement.
After determining Big O for each statement, how do you find the function’s Big O?
Find the statement(s) with the worst Big O notation. That is the Big O notation for the function.
What does the acronym FIFO mean?
First In First Out
What methods are available on a Queue data structure?
enqueue(value)- adds avalueto the “back” of the queue
dequeue()- removes the “front” value from the queue and returns it
peek() - peeks the “front” value without modifying the queue
What must you do to access the value at an arbitrary point in a queue (not just the “front”)?
Dequeue until you reach desired value
What does the acronym LIFO mean?
Last In First Out
- What methods are available on a Stack data structure?
pop() - Pops the “top” value off the stack.
push() - Pushes an item to the “top” of the stack
peek() - Returns the “top” value without modifying it
How are linked lists different from an array?
Linked lists are sequential access, where as arrays are random access
Does not need to be mutated to scan it’s contents (queue needs to be mutated)
How would you access an arbitrary node in a linked list (not just the “head”)?
Start at the head and traverse through with the next property
What properties are available on linked lists?
.data- contains the node’s value.
.nexta reference to the next node in the list, if there is one. If there is no “next” node in the list, this property is typically set tonull.
