Maps/SortedArrayMap: Difference between revisions
From charlesreid1
| Line 8: | Line 8: | ||
Next, we define the class itself, which still uses an ArrayList object to store data, but stores it in a sorted order. This makes insertions O(N) or O(log N), depending on the algorithm used. | Next, we define the class itself, which still uses an ArrayList object to store data, but stores it in a sorted order. This makes insertions O(N) or O(log N), depending on the algorithm used. | ||
=Code= | =Code= | ||
Revision as of 03:53, 26 June 2017
Notes
Procedure
Following the Maps/UnsortedArrayMap implementation mainly, here.
While we could have a general parent class, ArrayMap, what we do instead is to repeat our implementation of the ItemIterator utility class. A little bit of copy-pasta, but that's okay.
Next, we define the class itself, which still uses an ArrayList object to store data, but stores it in a sorted order. This makes insertions O(N) or O(log N), depending on the algorithm used.
Code
Git link
The sorted array implementation of a map is at git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/SortedArrayMap.java
This implements the Map ADT - see Maps/ADT.
Java implementation
Flags
 |
Maps and Dictionaries Part of Computer Science Notes
Series on Data Structures
Maps/Dictionaries Maps · Maps/ADT · Maps in Java · Maps/OOP · Maps/Operations and Performance Map implementations: Maps/AbstractMap · Maps/UnsortedArrayMap · Maps/SortedArrayMap Dictionary implementations: Dictionaries/LinkedDict · Dictionaries/ArrayDict
Hashes Hash Maps/OOP · Hash Maps/Operations and Performance Hash Maps/Dynamic Resizing · Hash Maps/Collision Handling with Chaining Hash functions: Hash Functions · Hash Functions/Cyclic Permutation Hash map implementations: Hash Maps/AbstractHashMap · Hash Maps/ChainedHashMap
Skip Lists · Java/ConcurrentSkipList · Java implementations: SkipList
Sets Sets · Sets/ADT · Sets in Java · Sets/OOP · Multisets
|