Exercises in this lecture   Go to the notes, in which this exercise belongs -- Keyboard shortcut: 'u'   Alphabetic index   Course home   

Exercise solution 7.2
Dobbeltkædet cirkulær liste

Her følger en løsningsskitse til en dobbeltkædet, cirkulær liste: 

// UKOMPLET SKITSE. AFHÆNGER AF CircularList mv.

class DoubleCircularList extends CircularList {

 class DoubleLinkable extends Linkable {

   private DoubleLinkable prev;
   
   DoubleLinkable(){
     super();
     prev = null;
   }

   DoubleLinkable(Object data){
     super(data);
     this.prev = null;
   }


   DoubleLinkable(Object data, Linkable next){
     super(data,next);
     this.prev = null;
   }

   DoubleLinkable(Object data, Linkable next, DoubleLinkable prev){
     super(data,next);
     this.prev = prev;
   }

   Linkable prev(){
     return(prev);
   }

   void setPrev(DoubleLinkable prev){
     this.prev = prev;
   }

 } // end DoubleLinkable

 public DoubleCircularList(){
   super();
 }

 // private firstLinkable OK as inherited
 
 // simpler because of double linking:
 protected Linkable butLastLinkable (){
   if (length == 0)
     return(null);
   else return(((DoubleLinkable)last).prev());
 }

 // emptyMe OK as inherited
 
 // size OK as inherited

 // redefined from CircularList
 private DoubleLinkable makeLinkable(Object el, DoubleLinkable next){
  if (next == null)
      return (new DoubleLinkable(el));
  else return (new DoubleLinkable(el,next));
 }

 protected void makeMeSingular(Object el){
   super.makeMeSingular(el);
   ((DoubleLinkable)last).setPrev((DoubleLinkable)last);
 }

 /** Insert el as a new first element */
 public void insertFirst(Object el){
  super.insertFirst(el);
  DoubleLinkable inserted = (DoubleLinkable)last.next();
  inserted.setPrev((DoubleLinkable)last);
 }


 /** Insert el as a new last element */
  public void insertLast(Object el){
    // reimplemented from scratch:
    DoubleLinkable newLink;
    if (length == 0) {
      makeMeSingular(el);
    }
    else{
      DoubleLinkable rememberOldLast = (DoubleLinkable)last;
      newLink = makeLinkable(el,(DoubleLinkable)firstLinkable());
      last = newLink;
      rememberOldLast.setNext(last);
      ((DoubleLinkable)last).setPrev(rememberOldLast);
      length = length + 1;
    }
 }

 /** Delete my first element */
 public void deleteFirst(){
   super.deleteFirst();
   DoubleLinkable first = (DoubleLinkable)((DoubleLinkable)last).next();
   first.setPrev((DoubleLinkable)last);
 }

 /** Delete my last element */
 public void deleteLast(){
   super.deleteLast();
   DoubleLinkable first = (DoubleLinkable)((DoubleLinkable)last).next();
   first.setPrev((DoubleLinkable)last);
 }   

 // retrieveFirst inherited and OK

 // retrieveLast inherited and OK

 public String toString(){
     return("Double: " + super.toString());
 }

}

Her er endvidere et link til det rene Java program .