6.19. Summary of Map ADT Implementations¶
Over the past two chapters we have looked at several data structures that can be used to implement the map abstract data type: a binary search on a list, a hash table, a binary search tree, and a balanced binary search tree. To conclude this section, let’s summarize the performance of each data structure for the key operations defined by the map ADT (see Table 1).
operation 
Sorted List 
Hash Table 
Binary Search Tree 
AVL Tree 


\(O(n)\) 
\(O(1)\) 
\(O(n)\) 
\(O(\log_2{n})\) 

\(O(\log_2{n})\) 
\(O(1)\) 
\(O(n)\) 
\(O(\log_2{n})\) 

\(O(\log_2{n})\) 
\(O(1)\) 
\(O(n)\) 
\(O(\log_2{n})\) 

\(O(n)\) 
\(O(1)\) 
\(O(n)\) 
\(O(\log_2{n})\) 
You have attempted of activities on this page