Data Structures Flashcards
Linked List
(def., positioning, what are they used for, how to invoke)
a collection of nodes where each node contains a data field and a reference (link) to the next node in the list
unlike normal list (arrays) elements do not have objective positions in the list, instead they have a relational postition based on surrounding nodes
used to create graphs and trees, data strucutres that require frequent addition/deletion
invoked in python by creating a Node class
Hash Table
(def, use case)
(object in js, dictionary in python)
data structure of key(index), value pairs
lookup up values by the key, not their location in the data structure
good for optimizing a problem, nested loop
Big O for Arrays (List)
lookup: O(1)
push: O(1)
pop: O(1)
insert: O(n) - iterate through
delete: O(n) - iterate through
prepend: O(n) - iterate through
Pros & Cons of Array (List)
Pros
- fast lookup
- fast push/pop
- ordered
Cons
- slow insert, delete, append at beginning
- static arrays: fixed size
Big O for Hash Table (Dictionary)
insert: O(1)
lookup: O(1) : sometimes O(n) when collision occurs
delete: O(1) : not ordered so no shifting
search: O(1)
Pros & Cons for Hash Tables
Pros
- fast access O(1), but more memory required O(n)
- fast lookups and inserts
Cons
- unordered
- collision: key has more than one value (data element)
- slows down insert & delete O(n)
- for loops, loop the entire memory space
- arrays only loop through the size of the data strucutre
- slow key insertion
Common Approach to Handling Hash Table Collision
what is the big O notation?
create a linked list for the additional value (data element)
O(n) insert and delete
Big O for Linked List
prepend: O(1)
append: O(1)
lookup: O(n)
insert: O(n)
delete: O(n)
Doubly Linked List
(definition)
pointers to the next a previous nodes
traversal forwards a backwards
Pros (4) & Cons (3) Linked List
(Single & Double)
Pros
- inserts and deletes are faster than arrays
- size is more flexible than an array (arrays double in memory once size hits a certain threshold)
- although not indexed, items are sorted unlike hash tables
- can be used to handle hash table collision
Cons
- iterating through linked list is sometimes slower than arrays becuase nodes are scattered over memory
- in single linked list, you can only traverse in one direction
- for doubly linked list, it requires more memory becuase of the two way traversal
Array (List)
(def., types of data it can hold, memory footprint)
most straight forward type of data structure
a data structure that contains a group of elements
can hold almost any type of data
smallest memory footprint
Pros (2) & Cons (3) of Doubly Linked List
Pros
- traverse forwards and backwards, unlike single linked list
- lookup faster
Cons
- delete and insert, slower than singly linked list
- requires more memory than singly linked list
- more complex to implement
Stacks & Queues
(def., ex.)
Stacks
LIFO: last item in is the only element you can access
Examples:
- undo button on phone/ms word
- function calls: inner most function (last written) first called
- browser history: backwards to the previous page
Queues
FIFO: first item in is the only elment you can access
Examples:
- uber ride: first person requesting ride is the first serviced
- printing: first request, first printed
- waiting in line: first in line, first serviced
Big O Stacks & Queues
Stack: Big O
lookup: O(n) - available although not often used
pop: O(1)
push: O(1)
peek: O(1) - view top item in the stack
Queue: Big O
lookup: O(n) - available although not often used
enqueue (similar to prepend): O(1)
dequeue (pop from the beginning): O(1)
peek: O(1) - view bottom item in queue
Trees
def. & nodes (4)
- hierarchical relational data structure
- nodes, pointers, & data
- linked list, except nodes only point to children
nodes
parent: root node
child: descends from parent
sibling: child node belonging to same parent
leaf: ending node that has no children
Binary Tree/Binary Search Tree (bst)
(prop. & rules)
properties
- parent can only have two children
- child can only have one sibling
- half of all nodes are on the bottom level
bst rules
- all children to right > in vlaue than parent
- all children to left < in value than parent
Big O BST
lookup: O(log N)
insert: O(log N)
delete: O(log N)
Pros (4) & Cons (2) of BST
Pros
- preserves relationships unlike hash tables
- search & lookups are fast
- balanced tree has good performance: O(log N) all operations
- flexible size
Cons
- no O(1) operations, not fastest for any specific operations
- unbalanced: bst can become linked list if you create children with no siblings, O(n) for some methods
Heaps
(def., common use cases, 2 types of binary heaps)
- can be used in any algorithmn when ordering is important
- created using left to right insertion
- common uses: priority queue, sorting, data storage
binary heaps: 2 types
max heap: root has largest value and all subsequent children ‘s value is less than their parent
mix heap: root has smallest values and all subsequent children’s values is greater than their parent
Big O for Heaps
lookup: O(n) - less order compared to bst
insert: O(log N)
delete: O(log N)
find min/max: O(1)
Pros for Heaps
Define Priority Queue
Pros
- good for comparative evaluation: ex. find all values greater than some other value
- least amount of memory possible
- flexible size
Priority Queue
each data element has a priority compared to others
ex.: line at a night club, VIPs show up late still go in first
Tries
(def., what is it optimized for, big O)
- specific type of tree used for searching text data
- outperforms bst for text searches
- benefits
- fast processing
- small memory space
- big O
- O(word length) : O(n)
Graphs
(3 points for now)
- non-linear: vertices and edges (nodes and lines)
- no hierarchical relationship (no root node) - network model
- loops are allowed in graphs
Traversal (Graphs v. Trees)
(might move to algorithm cards)
Graph Traversal: breath-first search, depth-first search
Trees: pre-order, in-order, post-order
