Data Structures Flashcards
What is a linked list?
A list that involves nodes that point to the next item in the list.
What is a stack?
An Abstract Data Structure (ADT) that is a LIFO. Last-in First-Out nature. Think stack of books
What is a queue?
An Abstract Data Structure (ADT) that is FIFO. First in First out. Think of a line in a grocery store
Breadth FIrst / Level Order Traversal
Traverse all nodes at one level before heading to the next
Depth First Search (Traversal)
Completely traverse a sub-tree before before traversing a sibling tree
In Order Traversal
Left -> Current -> Right
Post Order Traversal
Left -> Right -> Current
Pre Order Traversal
Current -> Left -> Right
Hashing
Maps a key to a unique integer
Hash Table Access
O(1)
Hash Table Space
O(n)
Hash Table Insert
O(1)
Hash Table Delete
O(1)
What is a Hash table
A data structure that maps keys to values using an associative array
BST Access Avg.
O(n log n)
BST Search Avg.
O(n log n)
BST Insertion Avg.
O(n log n)
BST Deletion Avg.
O(n log n)
Heap Order Property
No child has a key less than its parents key
