Data Structures Flashcards
What is the time complexity of SEARCH for an ARRAY?
O(n) - okay
What is the time complexity of INSERTION for an ARRAY?
O(n) - okay
What is the time complexity of DELETION for an ARRAY?
O(n) - okay
What is the worst space complexity of an array?
O(n) - okay
What is the time complexity of ACCESS of a STACK?
O(n) - okay
What is the time complexity of SEARCH of a STACK?
O(n) - okay
What is the time complexity of INSERTION of a STACK?
O(1) - great
What is the average time complexity of DELETION of a STACK?
O(1) - great
What is the worst space complexity of a STACK?
O(n) - okay
What is the time complexity of ACCESS of a LINKED LIST?
O(n) - okay
What is the time complexity of SEARCH of a LINKED LIST?
O(n) - okay
What is the time complexity of INSERTION of a LINKED LIST?
O(1) - great
What is the time complexity of DELETION of a LINKED LIST?
O(1) - great
What is the worst space complexity of a LINKED LIST?
O(n) - okay
What is the average time complexity of access, search, insertion, and deletion of a SKIP LIST?
O(log(n)) - good
What is the worst time complexity of access, search, insertion, and deletion of a SKIP LIST?
O(n) - okay
What is the worst space complexity of a SKIP LIST?
O(n log(n)) - bad!
What is the time complexity of ACCESS of a HASH TABLE?
Not applicable (why?)
What is the average time complexity of SEARCH, INSERTION, and DELETION of a HASH TABLE?
O(1) - great!
What is the worst time complexity of SEARCH, INSERTION, and DELETION of a HASH TABLE?
O(n) - okay
What is the worst space complexity of a HASH TABLE?
O(n) - okay
What is the average time complexity of access, search, insertion, and deletion of a BINARY SEARCH TREE?
O(log(n)) - good
What is the worst time complexity of access, search, insertion, and deletion of a BINARY SEARCH TREE?
O(n) - okay
What is the worst space complexity of a BINARY SEARH TREE?
O(n) - okay
What is the average time complexity of ACCESS for a CARTESIAN TREE or a SPLAY TREE?
Not applicable (why?)
What is the average time complexity of search, insertion and deletion for a CARTESIAN TREE?
O(log(n)) - good
What is the worst time complexity of search, insertion and deletion for a CARTESIAN TREE?
O(n) - okay
What is the worst space complexity of a CARTESIAN TREE?
O(n) - okay
What is the time complexity of access, search, insertion and deletion for a B-TREE?
O(log(n)) - good
What is the time complexity of access, search, insertion and deletion for a RED-BLACK TREE?
O(log(n)) - good
What is the time complexity of search, insertion and deletion for a SPLAY TREE?
O(log(n)) - good
What is the time complexity of access, search, insertion and deletion for a AVL TREE?
O(log(n)) - good
What is the worst space complexity of a B-TREE?
O(n) - okay
What is the worst space complexity of a RED-BLACK TREE?
O(n)- okay
What is the worst space complexity of a SPLAY TREE?
O(n) - okay
What is the worst space complexity of a AVL TREE?
O(n) - okay
What is an array?
A simple data structure consisting of a collection of elements, identified by at least one array index or key.
[3,5,6,8,2]
What is a stack?
An abstracted data type which is an ordered collection of elements with two operations, push (adds) and pop(removes last added).
What data structures can be used to implement a STACK?
Arrays or linked lists.
What is a linked list?
A data structure consisting of a group of nodes which represent a sequence. Each node consists of data and reference to the next node.
What are advantages of linked lists?
- Dynamic data structure that allocates memory when needed
- Insertion and deletion are easy to implement and FAST!
- Can create stacks and queues easily.
- Reduce access time and can expand in real time without memory overhead.
What is a doubly linked list?
A linked list where each node contains a reference to the next and previous nodes, allowing forward and backward traversal.
What is XOR-linking?
It uses bitwise XOR operation to compress the next and previous node address information into a single address field.
What are some disadvantages of linked lists?
- Uses more memory because of pointers needing to store next node info.
- Nodes need to be read in order from beginning.
- Nodes stored incontiguously (entries are not stored next to each other in memory), which increases time of access.
- Reverse traversal of singly-linked lists is cumbersome, and double linked lists take up a lot of space.
What is a skip list?
A data structure that allows fast search within an ordered sequence of elements. Can be implemented with parallel linked lists.
What is a hash table?
A data structure that maps keys to values (dictionary, associative array). It uses a hash function that takes a value and assigns an index to it. Usually implemented with arrays.
What is a binary search tree?
A family of data structures that stores items (numbers, names, etc) in memory in sorted order so look up can use binary search.
What is a Cartesian tree?
A binary tree derived from a sequence of numbers. It can be constructed in linear time using a stack-based algorithm for finding all nearest smaller values in sequence.
What is a red-black tree?
A binary search tree which color-codes each node as red or black, which allows for self balancing (height balanced. Enforces property that path from root to farthest leaf is no more than twice as long as path from root to nearest leaf.
What is a splay tree?
A self-adjusting binary search tree with the property that recently accessed elements are quick to access again, by reorganizing the accessed element to the root.
What is an AVL tree?
Adelson-Velsky and Landis tree.
Self balancing binary search tree that ensures the heights of two child subtrees of any node differ by at most one. Tree rotations rotate child and node to balance height and distribute children evenly.
What is the time complexity of ACCESS for an ARRAY?
O(1) - great
