SkipList: Difference between revisions
From charlesreid1
No edit summary |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
==Skip List Java Class== | |||
The SkipList class is a Java implementation of a Skip List. It draws heavily for inspiration on the Java Collections API (ConcurrentSkipList class) and phishman3579 on Github, both of which follow the same basic outline for their implementation, and make great use of the rich features of Java. | The SkipList class is a Java implementation of a Skip List. It draws heavily for inspiration on the Java Collections API (ConcurrentSkipList class) and phishman3579 on Github, both of which follow the same basic outline for their implementation, and make great use of the rich features of Java. | ||
Like phishman3579, I implemented the skip list and the skip map as two separate classes, while the ConcurrentSkipListMap class implements everything in one go. It makes the class really large, plus it has to deal with some extra complications due to threading, so it was nice to have a slightly shorter, slightly less convoluted example to follow. | |||
The SkipList implemented as a values-only lookup table (like a set) involves quite a bit of bookkeeping. | |||
==Links to useful materials== | |||
Collections API skip list implementation: | |||
* https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89a19a29bb9f9807d2a28351ed7f7df/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java | |||
phishman3579 skip list implementation: | |||
* https://github.com/phishman3579/java-algorithms-implementation | |||
* https://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/SkipList.java | |||
{{MapsFlag}} | {{MapsFlag}} | ||
Latest revision as of 10:32, 30 June 2017
Skip List Java Class
The SkipList class is a Java implementation of a Skip List. It draws heavily for inspiration on the Java Collections API (ConcurrentSkipList class) and phishman3579 on Github, both of which follow the same basic outline for their implementation, and make great use of the rich features of Java.
Like phishman3579, I implemented the skip list and the skip map as two separate classes, while the ConcurrentSkipListMap class implements everything in one go. It makes the class really large, plus it has to deal with some extra complications due to threading, so it was nice to have a slightly shorter, slightly less convoluted example to follow.
The SkipList implemented as a values-only lookup table (like a set) involves quite a bit of bookkeeping.
Links to useful materials
Collections API skip list implementation:
phishman3579 skip list implementation:
- https://github.com/phishman3579/java-algorithms-implementation
- https://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/data_structures/SkipList.java
 |
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
|