Herefter følger en løsningsskitse. Vi inkluderer først Linkable og
CircularList klasserne. Dernæst kommer klasen CircularListWithIterator. Bemærk, at
vi laver en indre klasse CircularListIterator, som implementerer Enumeration.
Denne klasse har en instansvariabel count, som på simpel vis holder styr på hvor mange
elementer vi har gennemløbet. Man kunne undgå brug af en sådan varibel ved på en anden
og mere tilfredsstillende måde at erkende, at man er nået hele vejen rundt i liste. Overvej dette.
Tilsidst ser vi et program som laver en cirkulær liste med 99 heltal, hvorover vi itererer. Her er endvidere et link til det rene Java program .import java.util.*;
class Linkable {
private Object data;
private Linkable next;
/** Return a Linkable object with null references in both data and next */
Linkable(){
data = null;
next = null;
}
/** Return a Linkable object with null references in next, and the parameter as data */
Linkable(Object data){
this.data = data;
this.next = null;
}
/** Return a Linkable object with first parameter as data and second parameter as next */
Linkable(Object data, Linkable next){
this.data = data;
this.next = next;
}
/** Return the data of this Linkable object */
Object data(){
return (data);
}
/** Return the reference to the next Linkable */
Linkable next(){
return (next);
}
/** Set the data field of this Linkable object */
void setData(Object data){
this.data = data;
}
/** Set the next field of this Linkable object */
void setNext(Linkable next){
this.next = next;
}
} //Linkable
class CircularList {
int length;
Linkable last;
/** return the first Linkable objekt in the circular list */
private Linkable firstLinkable(){
if (length != 0)
return(last.next());
else return(null); //does not make sense
}
/** return the Linkable objekt just before last */
private Linkable butLastLinkable(){
if (length == 0)
return(null);
else {
Linkable link = last;
while (link.next() != last) link = link.next();
return (link);
}
}
/** arrange that I become empty */
private void emptyMe(){
length = 0;
last = null;
}
/** Arrange that I am a circular list with el as the only element */
private void makeMeSingular(Object el){
last = new Linkable(el);
last.setNext(last);
length = 1;
}
/** Construct an empty circular list */
public CircularList(){
this.emptyMe();
}
/** Return my number of elements */
public int size(){
return(length);
}
/** Insert el as a new first element */
public void insertFirst(Object el){
Linkable newLink;
if (length == 0) {
makeMeSingular(el);
}
else {
newLink = new Linkable(el,firstLinkable());
last.setNext(newLink);
length = length + 1;
}
}
/** Insert el as a new last element */
public void insertLast(Object el){
Linkable newLink;
if (length == 0) {
makeMeSingular(el);
}
else{
Linkable rememberOldLast = last;
newLink = new Linkable(el,firstLinkable());
last = newLink;
rememberOldLast.setNext(last);
length = length + 1;
}
}
/** Delete my first element */
public void deleteFirst(){
if (length <= 1)
this.emptyMe();
else{
last.setNext(firstLinkable().next());
length = length - 1;
}
}
/** Delete my last element */
public void deleteLast(){
if (length <= 1)
this.emptyMe();
else {
Linkable theFirst = firstLinkable();
last = butLastLinkable();
last.setNext(theFirst);
length = length - 1;
}
}
/** Return my first element if any. Else return null */
Object retrieveFirst(){
if (length >= 0)
return(last.next().data());
else return(null);
}
/** Return my last element if any. Else return null */
Object retrieveLast(){
if (length >= 0)
return(last.data());
else return(null);
}
/** Return my string representation */
public String toString(){
StringBuffer str = new StringBuffer();
if (length == 0)
return("Empty circular list");
else {
Linkable link = firstLinkable();
str.append("CircularList[");
for (int i = 1; i <= length; i++){
str.append(link.data().toString() + ",");
link = link.next();
};
str.append("]");
return (str.toString());
}
}
} // CircularList
class CircularListWithIterator extends CircularList {
class CircularIterator implements Enumeration {
Linkable currentElement; // det element som iteratoren peger på
int count; // antallet af besøgte elementer
CircularIterator (){
count = 0; // vi har besøgt count elementer
if (size() == 0)
currentElement = null;
else currentElement = last.next(); // altså det første element.
}
public boolean hasMoreElements(){
return (count < size());
}
public Object nextElement(){
if (currentElement != null){
Object el = currentElement.data();
currentElement = currentElement.next();
count = count + 1;
return(el);
}
else return(null);
}
} // end class CircularListIterator
public CircularListWithIterator(){
super();
}
Enumeration elements(){
return (new CircularIterator());
}
} // CircularListWithIterator
public class IteratorCircularList {
public static void main (String[] args){
CircularListWithIterator cl = new CircularListWithIterator();
for (int i = 1; i < 100; i++){
cl.insertFirst(new Integer(i));
}
System.out.println(cl);
for (Enumeration it = cl.elements(); it.hasMoreElements(); )
System.out.println(it.nextElement());
}
}