|
||||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |
See:
Description
Class Summary | |
---|---|
DHashTable<K,V> | A simple dynamic HashTable . |
DList<O> | A dynamic singly-linked List . |
HashTable<K,V> | A simple hash-table (the abstract superclass of DHashTable and SHashTable ). |
List<O> | A singly-linked list (the abstract superclass of DList and SList ). |
SHashTable<K,V> | A simple static HashTable . |
SList<O> | A static singly-linked List . |
A set of unchanging (static) data structures, which return clones every time they are modified, and their equivalent dynamic counterparts.
Static vs. DynamicTraditional 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 add(O)
on SList
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.
Equals vs==
By default, data structures test equality using ==
because it is faster. If you wish to use Object.equals(java.lang.Object)
, equivalent methods are provided.
For example, SList
provides both List.contains(O)
and List.containsEquals(O)
.
Each static data structure defines a protected method called makeName
, where Name
is the name of the data structure.
The method takes the same argument as the class's main constructor. All modifying methods, such as add()
and remove()
use this method when creating new instances of the class.
The purpose of these make
methods is to allow easy subclassing of static structures.
For example, say we wanted to define a subclass of SList
, called SQueue
, that has a getFirst()
method.
Every modifying method of SList
would need to be rewritten in SQueue
so that it would return an instance of SQueue
rather than SList
. However, because all modifying methods in SList
use makeList(int, Node
to
create their clones, we can simply override makeList
, like so:
public class SQueue<O> extends SList<O> {
// SQueue keeps track of its first node.
protected final Node<O> first;
// This is the main constructor for SQueue.
protected SQueue(int size, Node<O> last, Node<O> first){
super(size, last);
this.first = first;
}
// Overrides SList#makeList.
protected SQueue<O> makeList(int size, Node<O> last){
return new SQueue<O>(size, last, first);
}
// Empty constructor.
public SQueue(){
super();
first = null;
}
// Get the first element of the SQueue.
public O getFirst(){
if(length == 0) return null;
else return first.content;
}
// Overrides SList#add, but can still use super.add thanks to makeList!
public SQueue<O> add(O element){
if(length == 0){
Node<O> first = new Node<O>(element, null);
return new SQueue<O>(1, first, first);
}
else return (SQueue<O>) super.add(element);
}
/* ... other modifying methods here ... */
}
|
||||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |