Lineare Liste

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de

Verkettete Listen gehören zu den dynamischen Datenstrukturen, die eine Speicherung von einer im Vorhinein nicht bestimmten Anzahl von miteinander in Beziehung stehenden Werten einfacher oder zusammengesetzter Datentypen erlauben. Sie werden durch Zeiger auf die jeweils folgende(n) Knoten oder Speicherzellen des Arbeitsspeichers realisiert. bereit. Knoten Ein Knoten (engl. node) bezeichnet ein Element der Liste, welches die Daten und einen Zeiger auf seinen Nachfolger enthält. Einfach verkettete Liste Eine einfach verkettete Liste ist die einfachste Form der verketteten Liste, da sie neben den einzelnen Knoten nur einen "Start"-Zeiger besitzt. Letzterer zeigt auf den ersten Knoten in der Liste (roter Pfeil). Der letzte Knoten in der Liste zeigt auf den Nullwert (hier null). Liste (Datenstruktur), Wikipedia – Die freie Enzyklopädie, 07.12.2005 - Der Text ist unter der Lizenz „Creative Commons Attribution/Share Alike“ verfügbar; zusätzliche Bedingungen können anwendbar sein. Siehe die Nutzungsbedingungen für Einzelheiten. In der Wikipedia ist eine Liste der Autoren verfügbar.

Verbale Definition: Eine Liste ist entweder leer oder sie besteht aus einem Kopf und einem Zeiger, der wiederum eine Liste ist.

Übung Analysieren Sie den Quelltext, gehen Sie dabei vor allem auf sucheMax() ein. Begründen Sie: "int max = 0;" (in sucheMax2()) ist ein ungünstiges Vorgehen. Implemtieren Sie insertVorne(int i), die am Anfang der Liste ein Element einfügt. Implementieren Sie die Methode contains(inhalt); - diese gibt true bzw. false als Antwort zurück, je nachdem, ob das gewünschte Element existiert oder nicht. index(inhalt) soll die Position zurückgeben, an der inhalt zum letzen Mal (Variante: zum ersten Mal) in der Liste steht. (schwierig) Schreiben Sie eine rekursive Variante der Ausgabe. Implementieren Sie insertListe(i, pos); die an der Position pos den Wert i in die Liste einfügt.

Inhaltsverzeichnis 1 Umsetzung von Listen in Java 1.1 Möglicher Quelltext einer eigenen Implementierung einer Liste in Java 2 Weblinks 3 Siehe auch

Umsetzung von Listen in Java

Es gibt in der Progammiersprache Java als Schnittstelle java.util.List und als konkrete Implementierungen java.util.LinkedList und java.util.ArrayList.

• LinkedList (engl.)
• LinkedList (deu.)
• Liste - (r-krell)

Möglicher Quelltext einer eigenen Implementierung einer Liste in Java

class Liste {
// Eine rekursiv aufgebaute Liste
    
 // Eigenschaften
 private int wert;                      // Inhalt
 private Liste next;                    // Verweis auf naechste Liste
 
 // Konstruktor, legt erstes Element fest
 public Liste (int i)                    
 { next = null;                        
   wert = i;     
 }

 // Methoden
 public void add (int i) 
 // add hängt am Ende der Liste einen neuen Knoten mit dem Wert i an
 {
  Liste runner; 
  runner = this ; 
  while (runner.next != null) 
  { 
    runner = runner.next;          
  } //while
  runner.next=new Liste(i);  
 } // add    
 
 public void gibAufKonsoleAus()
 // gibt die Werte aller Knoten aus.
 {
  Liste runner;  
  runner = this ; 
  System.out.print("(");    
  while (runner != null)   
  { 
    System.out.print(runner.wert); 
    if (runner.next!=null) System.out.print(" -> "); 
    runner = runner.next;         
  } // while 
  System.out.println(")"); 
 } // ausgabe
 
 public int sucheMax() {
 // sucht den größten Wert in der Liste
 return sucheMax2(this);
 }
 
 public int sucheMax2(Liste hilf) {
    int max = 0; // Kritisch! (Siehe Aufgabe hierzu!)
    while (hilf!=null){
       if (max < hilf.wert) max=hilf.wert;
       hilf=hilf.next;
    }
 return max;   
 } 
}  //Liste

//Alternative Realisation (rekursiv):
public int sucheMax3(Liste hilf, int max) {
   if (hilf == null) return max;
   else {
     if (max < hilfwert) max = hilf.wert;
     return sucheMax3(hilf.next, max);
   }
}

Alternativen zum Quelltext:

• Es gibt Varianten, bei denen der Kopf einzeln definiert ist.
• ...

Weblinks

• Lineare Abstrakte Datentypen (Keller, Schlangen, Listen) und einige Anwendungen (z.B. Tiefen- und Breitensuche)

Siehe auch

• Informatik
• Programmiersprachen