StapelListe

Polymorphe Implementierung der Schnittstelle Stapel als verkettete Liste aus der Bibliothek für das Lehrbuch Programmieren mit Java

Dokumentation Programmtext mit Dokumentation

package lehrbuch.kapitel9;
public class StapelListe implements Stapel {

	public StapelListe() {
		anker = null;
	}

	public StapelListe(final StapelListe quelle) throws VollAusnahme {
		this();
		kopieren(quelle);
	}

	public void entleeren() {
		anker = null;
	}

	public void eintragen (final Object element) throws VollAusnahme {
		try {
			anker = new Knoten(element, anker);
		}
		catch(OutOfMemoryError ausnahme) {
			throw new VollAusnahme();
		}
	}

	public Object lesen() throws LeerAusnahme {
		try {
			return anker.wert;
		}
		catch(NullPointerException ausnahme) {
			throw new LeerAusnahme();
		}
	}

	public void entfernen() throws LeerAusnahme {
		try { anker = anker.verbindung; }
		catch(NullPointerException ausnahme) { throw new LeerAusnahme(); }			
	}

	public boolean istLeer(){
		return anker == null;
	}

	public boolean istVoll() {
		try {
			Knoten knoten = new Knoten(); // Versuch
			return false; // ist gelungen
		} catch(OutOfMemoryError ausnahme) {
			return true; // kein Platz mehr
		}
	}

	// Implementierungen für kopieren und istGleich: mit Wiederholung und rekursiv
	public void kopieren(final StapelListe quelle) throws VollAusnahme {
		entleeren();
		Knoten knoten = quelle.anker;
		while (knoten != null) {
			eintragen(knoten.wert);
			knoten = knoten.verbindung;
		}
	}

	public boolean istGleich(final StapelListe stapel) {
		Knoten dieses = anker;
		Knoten jenes = stapel.anker;
		while (dieses != null && jenes != null) {
			if (dieses.wert != jenes.wert)
				return false;
			dieses = dieses.verbindung;
			jenes = jenes.verbindung;
		}
		return dieses == null && jenes == null;
	}

	public void kopierenRek(final StapelListe quelle) throws VollAusnahme {
		anker = knotenKopie(quelle.anker);
	}
	private Knoten knotenKopie(final Knoten quelle) throws VollAusnahme {
		Knoten ziel = null;
		try {
			ziel = new Knoten(quelle.wert); // throws NullPointerException, wenn quelle == null
			ziel.verbindung = knotenKopie(quelle.verbindung); // rekursiver Aufruf
		}
		catch(NullPointerException ausnahme) {} // Liste zu Ende
		catch(OutOfMemoryError ausnahme) { // kein Speicher mehr frei
			throw new VollAusnahme();
		}
		return ziel;
	}

	public boolean istGleichRek(final StapelListe stapel) { 
		return knotenVergleichen(anker, stapel.anker);
	}
	private boolean knotenVergleichen(final Knoten erster, final Knoten zweiter) {
		try {
			return erster.wert == zweiter.wert & // throws NullPointerException, wenn eine Referenz == null
				knotenVergleichen(erster.verbindung, zweiter.verbindung); // rekursiver Aufruf
		}
		catch(NullPointerException ausnahme) { // eine der Listen zu Ende
			return erster == null & zweiter == null; // auch die andere?
		}
	}

	private class Knoten {
		Object wert;
		Knoten verbindung;
		Knoten() {} // parameterloser Konstruktor (Attrappe für den Versuch in voll)
		Knoten(final Object wert) { // Konstruktor mit einem Parameter
			this.wert = wert; // verbindung == null
		}
		Knoten(final Object wert, final Knoten verbindung) { // Konstruktor mit zwei Parametern
			this.wert = wert;
			this.verbindung = verbindung;
		}
	}

	private Knoten anker = null;
}