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
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.
All data structures have been unit tests up to 100% line coverage.
Can be found here.
Can be downloaded here.
Can be downloaded here as an Eclipse project.
As always, they go to firstname.lastname@example.org.