Static and Dynamic Data Structures
What is Static vs. Dynamic?
Traditional Java data structures, such as LinkedList and HashMap, are "dynamic," meaning that their internal state is changed every time a modifying method such as add() or remove() is called.
A "static" data structure remains unchanged when modifying methods are called. Instead of changing the state of the object, these methods return a new instance of that class which realizes the change.
For example, calling SList.add does not add an element to the list. It returns a new SList which does contain the added element. The original object is unchanged.
Static data structures are useful when every stage of a changing data structure needs to be preserved. Using static data structures is more space and time efficient than constantly cloning a dynamic data structure. For instance, adding an element to an SList takes O(1) time, as opposed to cloning a LinkedList and adding an element to it, which takes O(n) time for a list of size n.
For convenience, dynamic versions of every static data structure are also provided so that, if you choose, all your data structures can obey the same interface.
The performance of the dynamic data structures is roughly equivalent to the java.util structures that they mimic.
Currently, the following data structures have been implemented:
- List: static SList and dynamic DList
- HashTable: static SHashTable and dynamic DHashTable
Thread Safety
Static data structures are thread safe because their internal state never changes. Their dynamic equivalents have been synchronized to make them thread safe as well.
Unit Tests
All data structures have been unit tests up to 100% line coverage.
Documentation
Can be found here.
JAR File
Can be downloaded here.
Source Code
Can be downloaded here as an Eclipse project.
Bugs
As always, they go to sgware@gmail.com.