Data structures Flashcards
Array vs linked list
Statically/Dynamically allocated
Fast/slow retrieval
Fast/slow modification
allocation
space allocated at start vs space added when necessary
adjacent vs not adjacent
retrieval
addresses of all elements are known
addresses are unknown and has to be retrieved frpm previous node
modification
array recreated when modified with O(N) efficiency
array modified without recreating with O(1) efficiency
static vs dynamic 5
allocation size memory reuse execution time efficiency
hash table properties
O(1) efficiency
key collisions
BST properties
O(log n)
natively maintain sorting order
freespace
System keeps track of the free disc blocks for allocating space to files when they are created.
To reuse the space released from deleting the files
The system maintains a free space list which keeps track of the disk blocks that are not allocated to some file or directory
Pre order traversal
Root left right
Post order
left right root
