List

Aus SibiWiki
Zur Navigation springen Zur Suche springen

Diese Seite entspricht dem Abi 17 (und folgenden)

Erklärvideo

Wie durchläuft man standardmäßig Listen?

Das wird hier anhand der Methode public int gesamtVermoegen() erklärt.

Erklärvideo: Liste durchlaufen am Beispiel "public int gesamtVermoegen()"

Fachbegriffe

Liste, Zeiger, an den Anfang, aktuelles Element, hasAccess(), ist leer (=isEmpty()), einfügen, (hinten) anhängen, (das aktuelle Element) löschen

Schnittstellenbeschreibung (Zentralabitur)


Standardvorgehen im Umgang mit Listen

Meistens werden Listen von vorne nach hinten durchlaufen und dabei wird mit jedem einzelnen Eintrag der Liste etwas gemacht. Das funktioniert folgendermaßen:

  1. Zeiger auf den Anfang der Liste setzen
  2. while-Schleife, die so lange läuft, wie der Zeiger in der Liste ist. Innerhalb der Schleife...
    1. das Element, auf das der Zeiger zeigt, in einer lokalen Variable speichern.
    2. mit diesem Element etwas machen (das hängt von der Aufgabe der Methode ab)
    3. den Zeiger eins weiterrücken.

Java

In Java sieht das so aus (die Liste ist in diesem Beispiel mit Objekten vom Typ Person gefüllt):

  • pList.toFirst();
  • while(pList.hasAccess()){
    • Person p = pList.getContent();
    • //TODO: mit der Person p etwas machen!
    • pList.next();
  • }

Mit for-Schleife

Mit einer for-Schleife lässt sich dieses Standard-Verfahren viel einfacher implementieren!

  • for(pList.toFirst(); pList.hasAccess(); pList.next()){
    • Person p = pList.getContent();
    • //TODO: mit der Person p etwas machen!
  • }

Beispielmethoden für Listen

Hier werden beispielhaft einige Methoden für Listen aufgeführt:

enthaelt


private boolean enthaelt(List<Person> pList, String pName) {
  boolean ergebnis = false;
  pList.toFirst();
  while(pList.hasAccess()){
     Person p = pList.getContent();
     if(p.gibName().equals(pName)){
        ergebnis = true;
     }
     pList.next();
  }
  return ergebnis;
}

Die Methode zeigt das Standard-Vorgehen zum Durchlaufen von Listen:

  • Es wird ein ergebnis deklariert. ergebnis ist vom selben Typ wie der Rückgabetyp der Methode (hier: boolean). ergebnis wird mit einem Standardwert versehen: Bevor man die Liste durchsucht, hat man noch nichts gefunden, d.h. ergebnis ist false
  • Der Zeiger wird auf den Anfang der Liste gesetzt.
  • Mit while(pList.hasAccess()) und pList.next() wird die Liste dann komplett durchlaufen.
  • Dabei wird mit Person p = pList.getContent(); jeweils die Person ausgelesen, auf die der Zeiger zeigt.
  • Mit der Person p wird dann etwas gemacht; in diesem Fall wird ihr Name mit dem Parameter pName verglichen und wenn das übereinstimmt, dann wird ergebnis auf true gesetzt.
  • Zum Schluss wird ergebnis zurückgegeben.

Anzahl aus Geburtsjahr

Hier wird folgendes algorithmische Verfahren umgesetzt:

  • ergebnis wird auf 0 gesetzt.
  • die Liste pList komplett durchlaufen.
    • Für die jeweils aktuelle Person wird geprüft, ob ihr Geburtsjahr dem Parameter pJahr entspricht.
      Wenn ja, wird ergebnis um 1 erhöht.
  • Nach dem Ende der Schleife wird ergebnis zurückgegeben.

Hinweis: Hier wird die Liste mit einer for-Schleife durchlaufen. Das ist für die Programmierung viel angenehmer, weil man nicht Gefahr läuft, das next() zu vergessen!


 public Person anzahlPersonenAusGeburtsjahr(List<Person> pList, int pJahr){
    int ergebnis = 0;
    for(pList.toFirst(); pList.hasAccess(); pList.next()){
       Person p = pList.getContent();
       if(p.getGeburtsjahr() == pJahr){
          ergebnis += 1;
       }
    }
    return ergebnis;
  }


jüngste Person

Hier wird folgende Strategie verfolgt:

  • in ergebnis wird zuerst die erste Person der Liste gespeichert.
  • Dann wird die Liste komplett durchlaufen.
    • Dabei wird die jeweils die Person, auf die der Zeiger zeigt, mit ergebnis verglichen: Wenn sie jünger ist, dann wird aktuell in ergebnis gespeichert.
  • Am Ende wird ergebnis zurückgegeben.

 public Person juengstePerson(List<Person> pList){
    Person ergebnis = null;
    if(pList.isEmpty()){
        return ergebnis;
    }
    pList.toFirst();
    Person ergebnis = pList.getContent();
    while(pList.hasAccess()){
       Person p = pList.getContent();
       if(p.getGeburtsjahr() < ergebnis.getGeburtsjahr()){
          ergebnis = p;
       }
       pList.next();
    }
    return ergebnis;
  }

Sortierverfahren

Sortieren durch Einfügen

siehe Insertionsort

Sortieren durch Auswählen

siehe Selectionsort

Bubblesort

Bubblesort ist mit der neuen List-Implementierung nicht mehr sinnvoll, da es keine Möglichkeit gibt die Methode Flip sinnvoll zu programieren.
Flip soll immer dann zwei Werte vertauschen, wenn der im Alphabet vordere Buchstabe hinten steht bzw. die hintere Zahl größer ist.
Um die Methode jedoch sinnvoll programieren zu können, wären komplizierte & umständliche Programierungen notwendig.
Desweiteren wäre am Ende das Sortierverfahren zu Rechenintensiv.

Mergesort

nicht relevant fürs Zentralabitur!

siehe Mergesort

Quicksort

im Zentralabitur nur relevant für den LK!

siehe Quicksort

istSortiert

für eine Liste, die mit Objekten vom Typ String gefüllt ist.


public boolean istSortiert(List<String> pList)
{
   boolean ergebnis = true;
   pList.toFirst();
   while(pList.hasAccess())
      {
      String aktuell = pList.getContent();
      pList.next();
      if(pList.hasAccess() == false)
      {
         ergebnis = true;
         return ergebnis;
      }
      String naechster = pList.getContent();
      if(aktuell.compareTo(naechster)>0)
      {
         ergebnis = false;
         return ergebnis;
      }
   }
   ergebnis = true;
   return ergebnis;
}