Maps/SortedArrayMap: Difference between revisions
From charlesreid1
(Created page with "=Notes= ==Procedure== ==Abstract map implementation notes== =Code= ==Git link== The sorted array implementation of a map is at git.charlesreid1.com: https://charlesreid1....") |
m (Replacing charlesreid1.com:3000 with git.charlesreid1.com) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 3: | Line 3: | ||
==Procedure== | ==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= | =Code= | ||
| Line 9: | Line 13: | ||
==Git link== | ==Git link== | ||
The sorted array implementation of a map is at git.charlesreid1.com: https://charlesreid1.com | The sorted array implementation of a map is at git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/hash/SortedArrayMap.java | ||
This implements the Map ADT - see [[Maps/ADT]]. | This implements the Map ADT - see [[Maps/ADT]]. | ||
Latest revision as of 03:39, 9 October 2019
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://git.charlesreid1.com/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
|