Subato

Resource Files

Unveränderbare einfach verkettete Liste

Listen als einfach verkettete Listenzellen

Implementieren Sie die dort noch fehlenden Methoden der Klasse LL für einfach verkettete Listen.

Rufen Sie dabei nie die Methoden get und size auf.

Die Methoden im einzelnen:

  • boolean containsWith(Predicate<A> p);
    Es soll geprüft werden, ob für ein Element der Liste das übergebene Prädikat gilt.
  • boolean contains(A el);
    Es soll geprüft werden, ob ein dem Argument gleiches Objekt in der Liste ist.
  • boolean isPrefixOf(LL<A> that);
    Es soll geprüft werden, ob die this-Liste der Anfang der that-Liste ist.
  • LL<A> drop(int i)
    Es wird eine Teilliste erzeugt, die ohne die ersten i-Elemente aus der this-Liste entsteht. Ist i größer als die Länge, dann sei das Ergebnis die leere Liste.
  • LL<A> take(int i)
    Es wird eine Teilliste erzeugt, die aus den ersten i-Elemente aus der this-Liste entsteht. Ist i größer als die Länge, dann sei das Ergebnis die komplette Liste.
  • LL<A> sublist(int from, int length)
    Es wird eine Teilliste erzeugt, die mit dem Element an dem angegebenen Index startet und die angegebene Länge hat.
  • A last()
    das letzte Element der Liste soll zurück gegeben werden. Für leere Liste soll null zurück gegeben werden.
  • LL<A> append(LL<A> that)
    Eine neue Liste durch aneinanderhänge von this und that soll erzeugt werden.
  • void forEach(Consumer<? super A> con)
    Führe die übergebene Aktion für jedes Element der Liste aus.
  • LL<A> filter(Predicate<? super A> p)
    Erzeuge eine neue Liste, die aus all den Elementen der Liste besteht, für die das Prädikat gilt. Die Reihenfolge der Elemente der Ergebnisliste entspricht der Reihenfolge der Ausgangsliste.
  • <B> LL<B> map(Function<? super A, ? extends B> f)
    Erzeuge eine neue Liste, die durch Anwendung der übergebenen Funktion auf die Elemente der Liste entsteht.
  • <A> reverse()
    Eine neue Liste in umgekehrter Elementreihenfolge der this-Elemente soll erzeugt werden.

Hinweis: Versuchen Sie einfache rekursive Lösungen zu finden. In der Musterlösung lommen die Methoden mit jeweils 3 Zeilen Methodenrumpf aus. 


package name.panitz.util; import java.util.function.Consumer; import java.util.function.Function; import java.util.function.Predicate; public class LL<A> { private final A hd; private final LL<A> tl; public boolean isEmpty(){ return hd==null&&tl==null; } public LL(A hd, LL<A> tl) { this.hd = hd; this.tl = tl; } public LL() { this(null,null); } public int size() { if (isEmpty()) return 0; return 1 + tl.size(); } public A get(int i) { return i==0?hd:tl.get(i-1); } boolean containsWith(Predicate<? super A> p) { return false; } boolean contains(A el) { return false; } boolean isPrefixOf(LL<A> that) { return false; } LL<A> drop(int i){ return new LL<>(); } LL<A> take(int i){ return new LL<>(); } LL<A> sublist(int from, int length){ return new LL<>(); } A last(){ return null; } LL<A> append(LL<A> that){ return new LL<>(); } void forEach(Consumer<? super A> con){ } LL<A> filter(Predicate<? super A> p){ return new LL<>(); } <B> LL<B> map(Function<? super A, ? extends B> f){ return new LL<B>(); } LL<A> reverse(){ return new LL<A>(); } @SuppressWarnings("unchecked") static <A> LL<A> create(A... es){ LL<A> result = new LL<A>(); for (int i=es.length-1;i>=0;i--){ result = new LL<A>(es[i],result); } return result; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((hd == null) ? 0 : hd.hashCode()); result = prime * result + ((tl == null) ? 0 : tl.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj){ return true; } if (obj == null){ return false; } if (!(obj instanceof LL)){ return false; } LL other = (LL) obj; if (hd == null) { if (other.hd != null){ return false; } } else if (!hd.equals(other.hd)){ return false; } if (tl == null) { if (other.tl != null){ return false; } } else if (!tl.equals(other.tl)){ return false; } return true; } @Override public String toString(){ StringBuffer result = new StringBuffer("["); boolean first = true; for (LL<A> it = this;!it.isEmpty();it=it.tl){ if (first){ first = false; } else{ result.append(", "); } result.append(it.hd); } result.append("]"); return result.toString(); } }
java