Week 5 - Data Structures Flashcards
What’s one of the biggest advantages of hash tables?
They combine the best of two worlds - arrays and linked lists
What’s the biggest disadvantage of hash tables?
Huge memory consumption
What’s the O of hash tables?
O(n)
What’s a hash function?
It’s a function that sorts elements within a hash table
What are tries?
Tries are data structures with trees, whose nodes are arrays
What’s the O of tries?
O(1) - constant search time
What’s the biggest disadvantage of tries?
Huge memory consumption
What do structures do?
Structures provide a way to unify several vars. of different types into a single new var. type
What structures are used for?
Structures are used to group elements of different data types that have a logical connection
What’s the difference between “typedef struct” and “struct”?
“typedef” allows us to create an alias for the struct. This alias is then used later to define variables of that type without having to write the “struct” keyword
Where are structures defined?
Structs are defined in separate .h files or atop of our programs, outside of any function
How can elements (aka members) of structs be access?
Using the dot operator (.)
How can we dynamically allocate structs?
Using the malloc function
What’s an example of dynamically allocated struct using the arrow operator?
(*mycar).year = 2011; can be replaced by mycar → year = 2011;
In how many directions can we move in a singly-linked list?
One direction only
What’s the problem with singly-linked lists moving in one direction only?
We cannot delete a node
In how many directions can we move on doubly-linked lists?
Two directions: foward and backward
What’s the downside of doubly-linked lists moving in both directions (foward and backward)?
We need to add an extra pointer to the structure definition, so more memory will be consumed
What are singly and doubly linked lists good for?
Insertion and deletion of elements
What’s the time singly and doubly linked lists take to insert and delete elements respectively?
Constant time
What’s the downside of singly and doubly linked lists?
We lose the ability to randomly access lists elements, so accessing elements will take linear time
Why are tries considered the holy grail of data scructs?
That’s because they provide a way to insert, delete and lookup in constant time
What do tries combine together to store data?
Structs and pointers
What’s one of the biggest advantages of tries?
They have no collision risk (two pieces of data will never have the same path)
What’s the downside of tries?
Memory consumption
What’s the reason to use stacks?
Make sure that the last element to be added is the first one to be removed
What do we need to consider before selecting a data struct?
How fast we want to:
* Insert data
* Delete data
* Look up data
