Linked List

Class Kata „Linked List“

Entwickle den abstrakten Datentyp Liste in Form einer verketteten Liste. Die zu implementierende Klasse LinkedList<T> muss das Interface IList<T> implementieren.

Eine verkettete Liste besteht aus Elementen, die jeweils einen Wert sowie einen Zeiger auf das nächste Element der Liste enthalten:

class Element<T>
{
    public Element(T item) {
        Item = item;
    }

    public T Item { get; set; }

    public Element<T> Next { get; set; }
}

Aus diesen Elementen wird die Liste intern zusammengesetzt. Nach außen sind die Elemente nicht sichtbar. Die LinkedList<T> verhält sich wie andere Klassen, die IList<T> implementieren:

class LinkedList<T> : IList<T> {
	...
}

Variationen

Die Liste kann auch doppelt verkettet sein. Zusätzlich zur Next Eigenschaft der Element erhalten diese eine Prev Eigenschaft für den Verweis auf das vorhergehende Element. Damit wird das Traversieren rückwärts vom letzten zum ersten Element beschleunigt.

class Element<T>
{
    public Element(T item) {
        Item = item;
    }

    public T Item { get; set; }

    public Element<T> Next { get; set; }

    public Element<T> Prev { get; set; }
}