Arbeiten mit .NET: Etwas Theorie/ Listen

Was sind Listen

Um zu erklären, wofür Listen eigentlich gut sind, ist es meistens eine gute Idee zu erklären, wofür andere Datentypen nicht geeignet sind.

Arrays bieten eine einfache Möglichkeit, einfache Datentypen zu speichern, wenn bekannt ist, welchen Datentyp man wie oft speichern will. Listen sind in dieser Hinsicht um einiges flexibler zu gestalten. Wenn zB Daten aus einer Datenbank gelesen werden sollen und man nicht weiss, wie viele Daten zu erwarten sind, helfen Listen weiter.

Listen haben andere Vorteile, wie auch andere dynamische Datenstrukturen, die ihre ganz eigenen Vorzüge haben. Auf diese Vorzüge werden hier noch im Einzelnen eingegangen.

Verkettete Listen

Einfach verkettete Liste

Eine einfach verkettete Liste besteht nur aus Nodes (Knotenpunkten), die den jeweils gewünschten Wert und einen "Zeiger" auf die nächste Node haben. Vereinfacht sei grafisch dargestellt, wobei O eine Node ist und --> der Zeiger auf eine andere Node:

|root|-->O-->O-->O-->|tail|

"Root" ist hierbei keine Node, sondern nur ein Zeiger auf das erste Elemente der Liste. "Tail" ist schlicht das letzte Element der Liste.

Die Implementation einer verketteten Liste sieht nun so aus:

public class LinkedList
{
    private Node root;
    private Node tail;
}

public class Node
{
    public object Value; //Enthält den Wert, der gespeichert werden soll
    public Node NextNode; //Beinhaltet die Referenz auf die nächste Node
}

Mit dieser Liste lässt sich natürlich noch überhaupt nichts anfangen, den diese muss mann zumindest noch befüllen können. Deswegen soll das Beispiel um eine entsprechende Methode erweitert werden, nämlich hier AddValue():

public class LinkedList
{
    private Node root;

    public void AddValue(object Value)
    {
        Node newNode = new Node(); //Neue, noch leere Node erstellen
        newNode.Value = Value; //Der Node den Wert verpassen

        if(root == null) //Sonderfall: Es ist noch keine Node in der Liste, Liste ist leer
        {
            root = newNode; //root zeigt auf die erste (und bisher) einzige Node
            tail = newNode; //HIer sind tail und root noch die gleichen Zeiger
        }
        else
        {
            tail.NextNode = newNode;
            tail = newNode;
        }
    }
}

Der else-Teil in der neuen Funktion bedarf möglicherweise noch etwas Erklärung. Mit dem Befehl tail.NextNode = newNode; erkläre ich der Node, die im Augenblick die letzte in der LIste ist, dass es eine neue Node gibt, die an die Liste angehangen werden soll.

Nun ist aber die bisher unter tail gespeicherte Node nicht mehr die letzte Node, so dass dieser Titel der neuen Node zukommt.

Um es noch einmal klar zu stellen: tail ist eine Referenz, ein Zeiger auf eine Node (Klassen sind Referenztypen in C#), nicht die Node selber. Aber ich kann die Node, auf die der Zeiger zeigt, verändern. Mit dem ersten Befehl im else-Teil habe ich C# angewiesen: "Verändere die Node, auf welche die Referenz tailzeigt so, als das die Referenz NextNode in der Node von tail dieselbe Referenz ist, wie newNode." newNode und tail.NextNode beinhalten also nun einen Zeiger auf dieselbe Stelle im Speicher.

Der zweite Befehl führt nun dazu, dass ich die Referenz von tail abändere und diese auf newNode zeigen lasse. Das Ergebnis lautet nun, dass zum Einen tail auf newNode zeigt und zum Anderen zeigt auch die Node, auf die tail vorher verwies, auf newNode.

Sortierte Listen

Iteratoren

Geht noch weiter... --Afisch 14:15, 19. Mär. 2010 (CET)