Unterabschnitte


A.2.5 Einfach verkettete Liste


A.2.5.1 Java-Version

Eine einfache Liste für ganzzahlige Werte mit den Anforderungen aus der Aufgabenstellung (siehe Einfach verkettete Liste) könnte so aussehen:

// Time-stamp: "11.05.03 13:38 einfacheListe.java klaus@wachtler.de"
//
// Lösung der Übungsaufgabe: Erstellen einer einfach verketteten Liste

// Die eigentliche Liste besteht aus einer Referenz auf das erste Element.
public class einfacheListe
{
    // Datentyp für ein Element der Liste:
    private class ListenElement
    {
        private int           nutzdaten;  // die Daten eines Elements
        private ListenElement next;       // Verweis auf Nachfolger

        public ListenElement( int daten )
        {
            nutzdaten = daten;
            next = null;
        }

        // fügt hinter sich ein neues Element ein:
        public void einf_dahinter( int wert )
        {
            // dazu den bisherigen Nachfolger merken, um
            // ihn später als Nach-Nachfolger einsetzen zu können:
            ListenElement uebernaechster = next;

            // neues Element schaffen und anhängen:
            next = new ListenElement( wert );

            // bisherigen Nachfolger dahinter setzen:
            next.setNext( uebernaechster );
        }

        public void setDaten( int daten )
        {
            nutzdaten = daten;
        }

        public int getDaten()
        {
            return nutzdaten;
        }

        public void setNext( ListenElement next_neu )
        {
            next = next_neu;
        }

        public ListenElement getNext()
        {
            return next;
        }


        // sucht nach einem Wert, und liefert das ListenElement
        // (falls gefunden), oder null.
        public ListenElement sucheWert( int wert )
        {
            // Schleife notfalls über alle Elemente:
            ListenElement aktuellesElement = this;
            do
            {
                if( aktuellesElement.getDaten()==wert )
                {
                    return aktuellesElement;
                }
                aktuellesElement = aktuellesElement.getNext();
            }
            while( aktuellesElement.getNext()!=null );

            // wenn alle Elemente nicht paßten, dann ist die Suche
            // fehlgeschlagen:
            return null;
        }

        // sucht nach dem Vorgänger eines Werts, und liefert das
        // ListenElement (falls gefunden), oder null.
        public ListenElement sucheVorgaengerVonWert( int wert )
        {
            // Schleife notfalls über alle Elemente:
            ListenElement aktuellesElement = this;
            do
            {
                if( aktuellesElement.next!=null
                    &&
                    aktuellesElement.next.getDaten()==wert
                    )
                {
                    return aktuellesElement;
                }
                aktuellesElement = aktuellesElement.getNext();
            }
            while( aktuellesElement.getNext()!=null );

            // wenn alle Elemente nicht paßten, dann ist die Suche
            // fehlgeschlagen:
            return null;
        }

        // Ausgabe einer Liste in einen String:
        // Element ausgeben, dann ggf. den Rest
        public String toString()
        {
            return ( " El." + nutzdaten
                     + ( next==null ? "." : ", " + next.toString() )
                     );
        }

    } // class ListenElement


    private ListenElement   anfang;

    public einfacheListe()
    {
        anfang = null;
    }

    // fügt einen neuen Wert am Anfang ein:
    public void einf_vorn( int wert )
    {
        // das bisherige erste Element merken, um es später zum
        // zweiten zu machen (auch wenn das bisherige erste
        // null ist, also die Liste bisher leer ist):
        ListenElement  zweites = anfang;

        // ein neues erstes Element erzeugen, und mit wert
        // initialisieren:
        anfang = new ListenElement( wert );

        // das bisherige erste Element (oder null) hinten
        // anhängen:
        anfang.setNext( zweites );
    }

    // fügt einen neuen Wert am Ende ein:
    public void einf_hinten( int wert )
    {
        // Wenn die Liste noch leer ist, dann einfach ein
        // Element an den Anfang setzen:
        if( anfang==null )
        {
            anfang = new ListenElement( wert );
        }
        else
        {
            // Suche nach dem letzten Element:
            ListenElement letztes = anfang;
            while( letztes.getNext()!=null )
            {
                letztes = letztes.getNext();
            }
            // letztes hat jetzt keinen Nachfolger mehr.
            // Das wird geändert:
            letztes.einf_dahinter( wert );
        }
    }
    // versucht, ein neues Element wert hinter einem gegebenen Wert
    // hinterwas einzusetzen.
    // Das kann natürlich fehlschlagen, wenn das Element, hinter
    // dem eingefügt werden soll, gar nicht existiert.
    // Dementsprechend wird true zurückgegeben, wenn alles geklappt
    // hat; sonst false.
    public boolean einf_HinterWert( int hinterwas, int wert )
    {
        // Leere Liste?
        if( anfang==null )
        {
            return false;
        }
        else
        {
            ListenElement element = anfang.sucheWert( hinterwas );
            if( element==null )
            {
                return false;
            }
            else
            {
                element.einf_dahinter( wert );
                return true;
            }
        }

    }


    // versucht, ein neues Element wert vor einem gegebenen Wert
    // vorwas einzusetzen.
    // Das kann natürlich fehlschlagen, wenn das Element, vor
    // dem eingefügt werden soll, gar nicht existiert.
    // Dementsprechend wird true zurückgegeben, wenn alles geklappt
    // hat; sonst false.
    public boolean einf_VorWert( int vorwas, int wert )
    {
        // Leere Liste?
        if( anfang==null )
        {
            return false;
        }
        // dann könnte es natürlich sein, daß gleich vor das erste
        // Element eingefügt werden soll:
        else if( anfang.getDaten()==vorwas )
        {
            einf_vorn( wert );
            return true;
        }
        else
        {
            ListenElement element = anfang.sucheVorgaengerVonWert( vorwas );
            if( element==null )
            {
                return false;
            }
            else
            {
                element.einf_dahinter( wert );
                return true;
            }
        }

    }


    // sucht nach einem Wert, und liefert true, wenn der gesuchte Wert
    // enthalten ist:
    public boolean sucheWert( int wert )
    {
        // Leere Liste?
        if( anfang==null )
        {
            return false;
        }
        else
        {
            return anfang.sucheWert( wert )!=null;
        }

    }

    // versucht, ein Element wert aus der Liste zu löschen.
    // Das kann natürlich fehlschlagen, wenn das Element, das
    // gelöscht werden soll, gar nicht existiert.
    // Dementsprechend wird true zurückgegeben, wenn alles geklappt
    // hat; sonst false.
    public boolean entf_wert( int wert )
    {
        // Leere Liste?
        if( anfang==null )
        {
            return false;
        }
        // dann könnte es natürlich sein, daß gleich das erste
        // Element gelöscht werden soll:
        else if( anfang.getDaten()==wert )
        {
            anfang = anfang.getNext();
            return true;
        }
        else
        {
            // Ansonsten brauchen wir den Vorgänger des zu löschenden
            // Elements; dessen Nachfolger muß gelöscht werden:
            ListenElement element = anfang.sucheVorgaengerVonWert( wert );
            if( element==null )
            {
                return false;
            }
            else
            {
                element.setNext( element.getNext().getNext() );
                return true;
            }
        }

    }


    // Ausgabe einer Liste in einen String:
    // Element ausgeben, dann den Rest
    public String toString()
    {
        return "Liste: " + ( anfang==null ? "-" : anfang.toString() );
    }

} // public class einfacheListe

Und hier das zugehörige Testprogramm:

// Time-stamp: "(17.05.02 11:53) teste_einfacheListe.java [Klaus@Wachtler.de]"
//
// javac teste_einfacheListe.java einfacheListe.java
// java teste_einfacheListe
//
// Testprogramm für class einfacheListe

import java.util.*;

public class teste_einfacheListe
{
    public static void main( String args[] )
    {
        einfacheListe   l = new einfacheListe();

        // ein paar jeweils von vorne her einfügen:
        l.einf_vorn( 45 );
        l.einf_vorn( 34 );

        // ein paar von hinten:
        l.einf_hinten( 112 );
        l.einf_hinten( 123 );
        System.out.println( l.toString() );

        // ist der Wert 45 enthalten?
        System.out.println( "45 ist "
                            + ( l.sucheWert( 45 ) ? "" : "nicht " )
                            + "enthalten"
                            );

        // ist der Wert 123 enthalten?
        System.out.println( "123 ist "
                            + ( l.sucheWert( 123 ) ? "" : "nicht " )
                            + "enthalten"
                            );

        // Die (nicht existierende) 30 löschen:
        if( l.entf_wert( 30 ) )
        {
            System.out.println( l.toString() );
        }
        else
        {
            System.out.println( "die 30 kann nicht gelöscht werden!" );
        }

        // Die 123 löschen:
        if( l.entf_wert( 123 ) )
        {
            System.out.println( l.toString() );
        }
        else
        {
            System.out.println( "die 123 kann nicht gelöscht werden!" );
        }

        // Die 112 löschen:
        if( l.entf_wert( 112 ) )
        {
            System.out.println( l.toString() );
        }
        else
        {
            System.out.println( "die 112 kann nicht gelöscht werden!" );
        }

        // Hinter der 45 noch eine 50 einfügen:
        if( l.einf_HinterWert( 45, 50 ) )
        {
            System.out.println( l.toString() );
        }
        else
        {
            System.out.println( "hinter 45 kann nichts eingefügt werden!" );
        }

        // Die 45 löschen:
        if( l.entf_wert( 45 ) )
        {
            System.out.println( l.toString() );
        }
        else
        {
            System.out.println( "die 45 kann nicht gelöscht werden!" );
        }

        // Vor der 34 noch eine 30 einfügen:
        if( l.einf_VorWert( 34, 30 ) )
        {
            System.out.println( l.toString() );
        }
        else
        {
            System.out.println( "vor 34 kann nichts eingefügt werden!" );
        }

        // Vor der 50 noch eine 48 einfügen:
        if( l.einf_VorWert( 50, 48 ) )
        {
            System.out.println( l.toString() );
        }
        else
        {
            System.out.println( "vor 50 kann nichts eingefügt werden!" );
        }

        // Vor der nicht existierenden 10 noch eine 8 einfügen
        // (klappt hoffentlich nicht):
        if( l.einf_VorWert( 10, 8 ) )
        {
            System.out.println( l.toString() );
        }
        else
        {
            System.out.println( "vor 10 kann nichts eingefügt werden!" );
        }

    }


} // public class teste_einfacheListe

Die Ausgabe sieht folgendermaßen aus:

Liste:  El.34,  El.45,  El.112,  El.123.
45 ist enthalten
123 ist nicht enthalten
die 30 kann nicht gelöscht werden!
Liste:  El.34,  El.45,  El.112.
Liste:  El.34,  El.45.
hinter 45 kann nichts eingefügt werden!
Liste:  El.34.
Liste:  El.30,  El.34.
vor 50 kann nichts eingefügt werden!
vor 10 kann nichts eingefügt werden!


A.2.5.2 C++-Version

Die Musterlösung in C++ ist auffallend ähnlich der Java-Version (siehe Java-Version):

// Time-stamp: "11.05.03 17:12 einfacheListe.cpp klaus@wachtler.de"
//
// Lösung der Übungsaufgabe: Erstellen einer einfachen Liste
//
// ANSI-C++
//
// Linux:    g++ -Wall einfacheListe.cpp && ./a.out
//
// VC++ 6.0: cl /Zi /GX einfacheListe.cpp
//           .\einfacheListe

#include <iostream>
using namespace std;

// Die eigentliche Liste besteht aus einem Zeiger auf das erste Element.
class einfacheListe
{
private:

  // Datentyp für ein Element der Liste:
  class ListenElement
  {
  private:
    int            nutzdaten;  // die Daten eines Elements
    ListenElement *next;       // Verweis auf Nachfolger

  public:

    // Konstruktor
    ListenElement( int daten = 0 )
    {
      nutzdaten = daten;
      next = NULL;
    }

    // Destruktor
    // Achtung! Weil das delete next den Destruktor gleich wieder
    // für den Nachfolger aufruft, in dem wiederum ein delete next
    // steht, wird rekursiv die gesamte Liste ab dem aktuellen Element
    // freigegeben!
    // Wenn man nur ein Element freigeben will, aber nicht seine
    // Nachfolger, dann muß man zuvor sein next zu NULL setzen!
    virtual ~ListenElement()
    {
      delete next;
    }

    // fügt hinter sich ein neues Element ein:
    void einf_dahinter( int wert )
    {
      // dazu den bisherigen Nachfolger merken, um
      // ihn später als Nach-Nachfolger einsetzen zu können:
      ListenElement *uebernaechster = next;

      // neues Element schaffen und anhängen:
      next = new ListenElement( wert );

      // bisherigen Nachfolger dahinter setzen:
      next->setNext( uebernaechster );
    }

    void setDaten( int daten )
    {
      nutzdaten = daten;
    }

    int getDaten()
    {
      return nutzdaten;
    }

    void setNext( ListenElement *next_neu )
    {
      next = next_neu;
    }

    ListenElement *getNext()
    {
      return next;
    }


    // sucht nach einem Wert, und liefert das ListenElement
    // (falls gefunden), oder NULL.
    ListenElement *sucheWert( int wert )
    {
      // Schleife notfalls über alle Elemente:
      ListenElement *aktuellesElement = this;
      do
      {
        if( aktuellesElement->getDaten()==wert )
        {
          return aktuellesElement;
        }
        aktuellesElement = aktuellesElement->getNext();
      }
      while( aktuellesElement->getNext()!=NULL );

      // wenn alle Elemente nicht paßten, dann ist die Suche
      // fehlgeschlagen:
      return NULL;
    }

    // sucht nach dem Vorgänger eines Werts, und liefert das
    // ListenElement (falls gefunden), oder NULL.
    ListenElement *sucheVorgaengerVonWert( int wert )
    {
      // Schleife notfalls über alle Elemente:
      ListenElement *aktuellesElement = this;
      do
      {
        if( aktuellesElement->next!=NULL
            &&
            aktuellesElement->next->getDaten()==wert
            )
        {
          return aktuellesElement;
        }
        aktuellesElement = aktuellesElement->getNext();
      }
      while( aktuellesElement->getNext()!=NULL );

      // wenn alle Elemente nicht paßten, dann ist die Suche
      // fehlgeschlagen:
      return NULL;
    }

    // Ausgabe einer Liste in einen ostream:
    // Element ausgeben, dann ggf. den Rest
    virtual void tostream( ostream &o ) const
    {
      o << " El." << nutzdaten;
      if( next==NULL )
      {
        o << ".";
      }
      else
      {
        o << ", ";
        next->tostream( o );
      }
    }

  }; // class ListenElement

  ListenElement   *anfang;

public:

  // Konstruktor
  einfacheListe()
  {
    anfang = NULL;
  }
  // Destruktor
  virtual ~einfacheListe()
  {
    // Listenelemente freigeben:
    delete anfang;
  }

  // fügt einen neuen Wert am Anfang ein:
  void einf_vorn( int wert )
  {
    // das bisherige erste Element merken, um es später zum
    // zweiten zu machen (auch wenn das bisherige erste
    // NULL ist, also die Liste bisher leer ist):
    ListenElement  *zweites = anfang;

    // ein neues erstes Element erzeugen, und mit wert
    // initialisieren:
    anfang = new ListenElement( wert );

    // das bisherige erste Element (oder NULL) hinten
    // anhängen:
    anfang->setNext( zweites );
  }

  // fügt einen neuen Wert am Ende ein:
  void einf_hinten( int wert )
  {
    // Wenn die Liste noch leer ist, dann einfach ein
    // Element an den Anfang setzen:
    if( anfang==NULL )
    {
      anfang = new ListenElement( wert );
    }
    else
    {
      // Suche nach dem letzten Element:
      ListenElement *letztes = anfang;
      while( letztes->getNext()!=NULL )
      {
        letztes = letztes->getNext();
      }
      // letztes hat jetzt keinen Nachfolger mehr.
      // Das wird geändert:
      letztes->einf_dahinter( wert );
    }
  }

  // versucht, ein neues Element wert hinter einem gegebenen Wert
  // hinterwas einzusetzen.
  // Das kann natürlich fehlschlagen, wenn das Element, hinter
  // dem eingefügt werden soll, gar nicht existiert.
  // Dementsprechend wird true zurückgegeben, wenn alles geklappt
  // hat; sonst false.
  bool einf_HinterWert( int hinterwas, int wert )
  {
    // Leere Liste?
    if( anfang==NULL )
    {
      return false;
    }
    else
    {
      ListenElement *element = anfang->sucheWert( hinterwas );
      if( element==NULL )
      {
        return false;
      }
      else
      {
        element->einf_dahinter( wert );
        return true;
      }
    }
  }


  // versucht, ein neues Element wert vor einem gegebenen Wert
  // vorwas einzusetzen.
  // Das kann natürlich fehlschlagen, wenn das Element, vor
  // dem eingefügt werden soll, gar nicht existiert.
  // Dementsprechend wird true zurückgegeben, wenn alles geklappt
  // hat; sonst false.
  bool einf_VorWert( int vorwas, int wert )
  {
    // Leere Liste?
    if( anfang==NULL )
    {
      return false;
    }
    // dann könnte es natürlich sein, daß gleich vor das erste
    // Element eingefügt werden soll:
    else if( anfang->getDaten()==vorwas )
    {
      einf_vorn( wert );
      return true;
    }
    else
    {
      ListenElement *element = anfang->sucheVorgaengerVonWert( vorwas );
      if( element==NULL )
      {
        return false;
      }
      else
      {
        element->einf_dahinter( wert );
        return true;
      }
    }
  }


  // sucht nach einem Wert, und liefert true, wenn der gesuchte Wert
  // enthalten ist:
  bool sucheWert( int wert )
  {
    // Leere Liste?
    if( anfang==NULL )
    {
      return false;
    }
    else
    {
      return anfang->sucheWert( wert )!=NULL;
    }

  }

  // versucht, ein Element wert aus der Liste zu löschen.
  // Das kann natürlich fehlschlagen, wenn das Element, das
  // gelöscht werden soll, gar nicht existiert.
  // Dementsprechend wird true zurückgegeben, wenn alles geklappt
  // hat; sonst false.
  bool entf_wert( int wert )
  {
    // Leere Liste?
    if( anfang==NULL )
    {
      return false;
    }
    // dann könnte es natürlich sein, daß gleich das erste
    // Element gelöscht werden soll:
    else if( anfang->getDaten()==wert )
    {
      ListenElement *zweites = anfang->getNext(); // kurz merken

      // Das bisherige erste Element muß gelöscht werden.
      // Dazu:
      // 1. seinen Nachfolger abhängen (damit beim folgenden Frei-
      //    geben nicht der gesamte Listenrest freigegeben wird):
      anfang->setNext( NULL );
      // 2. das erste Element löschen:
      delete anfang;
      // jetzt das zweite Element zum ersten machen:
      anfang = zweites;

      return true;
    }
    else
    {
      // Ansonsten brauchen wir den Vorgänger des zu löschenden
      // Elements; dessen Nachfolger muß gelöscht werden:
      ListenElement *element = anfang->sucheVorgaengerVonWert( wert );
      if( element==NULL )
      {
        return false;
      }
      else
      {
        // das zu löschende Element ist jetzt element->getNext().
        // Dieses Element kurz merken, damit wir es zum Schluß
        // freigeben können:
        ListenElement *zuloeschen = element->getNext();

        element->setNext( element->getNext()->getNext() );

        // auch hier den Nachfolger plattmachen, damit beim
        // Freigeben von zuloeschen nicht der ganze Listenrest
        // freigegeben wird:
        zuloeschen->setNext( NULL );
        delete zuloeschen;

        return true;
      }
    }
  }


  // Ausgabe einer Liste in einen String:
  // Element ausgeben, dann den Rest
  void tostream( ostream &o ) const
  {
    o<< "Liste: ";
    if( anfang==NULL )  o << "-";
    else                anfang->tostream( o );
  }

}; // class einfacheListe


ostream &operator<<( ostream &o, const einfacheListe &l )
{
    l.tostream( o );
    return o;
}

int main( int nargs, char **args )
{
    einfacheListe   l;

    // ein paar jeweils von vorne her einfügen:
    l.einf_vorn( 45 );
    l.einf_vorn( 34 );

    // ein paar von hinten:
    l.einf_hinten( 112 );
    l.einf_hinten( 123 );
    cout << l << endl;

    // ist der Wert 45 enthalten?
    cout << "45 ist "
         << ( l.sucheWert( 45 ) ? "" : "nicht " )
         << "enthalten" << endl;

    // ist der Wert 123 enthalten?
    cout << "123 ist "
         << ( l.sucheWert( 123 ) ? "" : "nicht " )
         << "enthalten" << endl;

    // Die (nicht existierende) 30 löschen:
    if( l.entf_wert( 30 ) )
    {
        cout << l << endl;
    }
    else
    {
        cout << "die 30 kann nicht gelöscht werden!" << endl;
    }

    // Die 123 löschen:
    if( l.entf_wert( 123 ) )
    {
        cout << l << endl;
    }
    else
    {
        cout << "die 123 kann nicht gelöscht werden!" << endl;
    }

    // Die 112 löschen:
    if( l.entf_wert( 112 ) )
    {
        cout << l << endl;
    }
    else
    {
        cout << "die 112 kann nicht gelöscht werden!" << endl;
    }

    // Hinter der 45 noch eine 50 einfügen:
    if( l.einf_HinterWert( 45, 50 ) )
    {
        cout << l << endl;
    }
    else
    {
        cout << "hinter 45 kann nichts eingefügt werden!" << endl;
    }

    // Die 45 löschen:
    if( l.entf_wert( 45 ) )
    {
        cout << l << endl;
    }
    else
    {
        cout << "die 45 kann nicht gelöscht werden!" << endl;
    }

    // Vor der 34 noch eine 30 einfügen:
    if( l.einf_VorWert( 34, 30 ) )
    {
        cout << l << endl;
    }
    else
    {
        cout << "vor 34 kann nichts eingefügt werden!" << endl;
    }

    // Vor der 50 noch eine 48 einfügen:
    if( l.einf_VorWert( 50, 48 ) )
    {
        cout << l << endl;
    }
    else
    {
        cout << "vor 50 kann nichts eingefügt werden!" << endl;
    }

    // Vor der nicht existierenden 10 noch eine 8 einfügen
    // (klappt hoffentlich nicht):
    if( l.einf_VorWert( 10, 8 ) )
    {
        cout << l << endl;
    }
    else
    {
        cout << "vor 10 kann nichts eingefügt werden!" << endl;
    }
    return 0;
} // main( int nargs, char **args )

Die wesentlichen Unterschiede zur Java-Version sind:

Die Ausgabe sieht folgendermaßen aus:

Liste:  El.34,  El.45,  El.112,  El.123.
45 ist enthalten
123 ist nicht enthalten
die 30 kann nicht gelöscht werden!
Liste:  El.34,  El.45,  El.112.
Liste:  El.34,  El.45.
hinter 45 kann nichts eingefügt werden!
Liste:  El.34.
Liste:  El.30,  El.34.
vor 50 kann nichts eingefügt werden!
vor 10 kann nichts eingefügt werden!

www.wachtler.de