Data Structures Flashcards
Are elements indexed in a Linked List
No
Advantages of Linked List
Insert/Delete are quick: Prepend O(1) Append O(n)
Implement a Linked List
class Node {
constructor() {
var data;
Node.next()
Node (data) {
this.data = data
}
}Binary Search Tree Structure
left nodes < root nodes < right nodes
Balanced Binary Tree Method Complexity
insert & find: O(logn)
Proper way to Traverse a Binary Tree
Left then root then right
Heap Structure
Root is smaller than children(Min Binary Heap), Root is always larger (Max Binary Heap.
Priority Queue is a Min Binary Heap. (2n +1): 2 to get child index, Math.floor(n/2) to get parent index
Implement a counting function in a Linked List
function countNodes(Nodehead) {
//assuming head !== null
let count = 1
Node.current = head
while (current.next != null) {
current = current.next;
count += 1;
}
return count;
}Hash Tables consist of
keys mapped to values stored as objects in an array
Hash Table Time complexity
Constant
How do hash table elements get sorted
A key is passed into a hashing function, and the result is the index the key, value pair is stored at
Hash function for integers
sum(integers) % array.size = index
Hash function for strings
sum(CharCode) % array.size = index
Open Addressing method for Collision Handling in Hash Tables
Linear Probing: takes linear time, decent in if the load factor is low. keep looking for the next open index (or plus 3, quadratic). Keys might bunch together
Load factor in a Hash Table
load factor = n / k where n is the number of entries and k is the number of buckets in the array
Closed Addressing method for Collision Handling in Hash Tables
Chaining: creating a linked list at indexes with more than one hash pointing to it. Search by stepping along the linked list. O(n)
Objectives of a Hash function
- minimize collisions
- uniform distribution of hash values
- easy to calculate
- be able to resolve collisions
Runtime of a hash function
O(1)
Linked List
Data structure that represents a sequence of nodes. Single & double linked. Single only points one direction, double points both directions
Linked List disadvantage
does not provide constant time access to look up an index. O(n) time
Linked list advantage
add/remove items from the beginning of the list in constant time.
Deleting node in linked list
given n, find prev. prev.next = n.next. Check for null pointers and reset the head/tail node as necessary
linked list runner technique
iterate through the linked list with 2 pointers simultaneously, with one ahead of the other. the ‘fast’ node could be ahead by a fixed amount or could be hopping multiple nodes.
Array advantages
Constant time for lookup
Stacks
LIFO, O(1) time for add/remove
Queue
FIFO O(1) time for add/remove
When to use DFS
If we know the solution lies somewhere deep in a tree or far from the source vertex in graph, use DFS. If our tree is very wide, use DFS as BFS will take too much memory.
When to use BFS
If we know the solution is not that far from the source vertex, use BFS. If our tree is very deep, choose BSF over DFS.
