Erstellen einer zirkulär verknüpften Liste in C #?

Was wäre der beste Weg, um erstellen Sie eine zirkulär verknüpfte Liste in C#. Sollte ich leiten es aus der LinkedList< T> - Kollektion? Ich bin Planung über ein einfaches Adressbuch mit Hilfe dieser verketteten Liste zu speichern meine Kontakte (es ist gonna be eine saugen-y-Adressbuch, aber das ist mir egal denn ich werde die einzige sein, die es zu benutzen). Ich hauptsächlich nur wollen, zu erstellen, die entscheidend mit Liste, damit ich es wieder verwenden können in anderen Projekten.

Wenn Sie glaube nicht, dass die Verlinkte Liste, ist den richtigen Weg zu gehen, lassen Sie mich wissen, welchen Weg wäre besser.

InformationsquelleAutor der Frage Kredns | 2009-04-04

  1. 75

    Da die meisten dieser Antworten nicht tatsächlich an die Substanz der Frage, lediglich die Absicht, vielleicht wird dies helfen:

    Soweit ich sagen kann, der einzige Unterschied zwischen einer Verknüpften Liste und einem Kreisförmig Verlinkte Liste ist das Verhalten von Iteratoren bei erreichen das Ende oder den Anfang einer Liste. Eine sehr einfache Möglichkeit, um Unterstützung auf das Verhalten einer Kreisförmig Verlinkte Liste ist für das schreiben einer extension-Methode für eine LinkedListNode liefert den nächsten Knoten in der Liste oder den ersten, wenn kein solcher Knoten existiert, und ebenso die für das abrufen des vorherigen Knoten oder der Letzte, wenn kein solcher Knoten vorhanden ist. Der folgende code sollte erreichen, dass, obwohl ich es noch nicht getestet:

    static class CircularLinkedList {
    public static LinkedListNode<T> NextOrFirst<T>(this LinkedListNode<T> current)
    {
        return current.Next ?? current.List.First;
    }

    public static LinkedListNode<T> PreviousOrLast<T>(this LinkedListNode<T> current)
    {
        return current.Previous ?? current.List.Last;
    }
}

    Jetzt können Sie einfach anrufen myNode.NextOrFirst() anstelle von myNode.Weiter, und Sie werden alle haben, die das Verhalten einer kreisförmig verlinkte Liste. Sie können immer noch Konstante Zeit, die Umzüge und einfügen, bevor und nachdem alle Knoten in der Liste und die wie. Wenn es gibt einige andere wichtige bit of a circular linked list ich bin fehlt, lass es mich wissen.

    InformationsquelleAutor der Antwort Clueless

  2. 6

    Würde es wahrscheinlich eine schlechte Idee, eine Ableitung von BCL-LinkedList-Klasse. Diese Klasse wurde entwickelt, um eine nicht-zirkuläre Liste. Versuchen, damit es Runder wird nur Probleme verursachen.

    Sind Sie wahrscheinlich viel besser für das schreiben Ihrer eigenen.

    InformationsquelleAutor der Antwort JaredPar

  3. 4

    Ich glaube nicht, dass ein kreisförmig verlinkte Liste ist die richtige Datenstruktur für eine Kontakte-Liste. Eine einfache Liste<> oder Sammlung<> sollte ausreichen.

    InformationsquelleAutor der Antwort Mitch Wheat

  4. 4

    Haben Sie eine spezifische Anforderung eines zirkulär verknüpften Liste (D. H. Hausaufgaben)? Wenn nicht, würde ich vorschlagen, die einfach List<T> Klasse zum speichern Ihrer Kontakte.

    InformationsquelleAutor der Antwort Samuel

  5. 3

    Zirkular-verlinkte Listen sind Häufig implementiert mit arrays, wodurch Sie sehr schnell sind und durch Ihre Beschaffenheit nicht erfordern dynamische Größenänderung. Sie müssen nur ein quick-check auf die read-und die write-Indizes zu sehen, wenn Sie fiel aus dem Ende und wenn ja, zurücksetzen auf null (oder eins, was auch immer).

    Jedoch, Sie sind in der Regel für Dinge wie input-Puffer, wo die Daten hat keinen wirklichen Wert einmal gelesen. Kontaktlisten haben bleibenden Wert und neue Kontakte überschreiben, die älter Kontakte, wenn die Liste füllt sich, das wäre ok, es sei denn, Sie überschreiben Ihre grandmom, ist dass Sie einen Haufen Geld in Ihrem Testament.

    Ich glaube nicht, dass eine verlinkte Liste ist der effizienteste Weg, zu gehen für einen kreisförmigen Puffer (ursprüngliche Frage).

    Dem Zweck, ein Ringpuffer ist Geschwindigkeit und ein array kann einfach nicht geschlagen werden, die für die Geschwindigkeit im Zusammenhang mit einem Ringpuffer. Auch wenn Sie immer einen Zeiger auf das zuletzt zugegriffen verlinkten Liste Element, ein array wird immer noch effizienter sein. Listen dynamische Größenanpassung Fähigkeiten (overhead) , nicht gebraucht für Runde Puffer.
    Having said that, ich denke, dass ein Ringpuffer ist wahrscheinlich nicht die richtige Struktur für die Anwendung (Kontakt-Liste), die Sie erwähnen.

    InformationsquelleAutor der Antwort RAL

  6. 3
    class CircularArray<T> : IEnumerator<T>
{
    private readonly T[] array;
    private int index = -1;
    public T Current { get; private set; }

    public CircularArray(T[] array)
    {
        Current = default(T);
        this.array = array;
    }

    object IEnumerator.Current
    {
        get { return Current; }
    }

    public bool MoveNext()
    {
        if (++index >= array.Length)
            index = 0;
        Current = array[index];
        return true;
    }

    public void Reset()
    {
        index = -1;
    }

    public void Dispose() { }
}

    InformationsquelleAutor der Antwort Andrii Nemchenko

  7. 2

    Ein-Modul-basierte Lösung.

    Wenn der Ringpuffer implementiert ist als ein raw array (oder jede andere Art von Sammlung für das, was es darauf ankommt)

    T[] array;

    und speichern wir in int current_index den index des aktuellen Elements, können wir Zyklus nach oben und unten der Puffer wie folgt:

    T NextOrFirst()
{
    return array[(current_index + 1) % array.Length];
}

T PreviousOrLast()
{
    return array[(current_index + array.Length - 1) % array.Length];
}

    Der gleiche Ansatz kann verwendet werden, mit jedem XAML-binding collection.

    InformationsquelleAutor der Antwort voccoeisuoi

  9. 0

    Ich denke, die richtige Datenstruktur für dieses problem ist eine zirkuläre doppelt verkettete Liste. Mit dieser Datenstruktur können Sie sich frei nach oben und unten durch die Kontakte-Liste

    InformationsquelleAutor der Antwort omar

  10. 0
    class Program
{
    static void Main(string[] args)
    {
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7 };

        IEnumerable<int> circularNumbers = numbers.AsCircular();

        IEnumerable<int> firstFourNumbers = circularNumbers.Take(4); //1 2 3 4
        IEnumerable<int> nextSevenNumbersfromfourth = circularNumbers
            .Skip(4).Take(7); //4 5 6 7 1 2 3 
    }
}

public static class CircularEnumerable
{
    public static IEnumerable<T> AsCircular<T>(this IEnumerable<T> source)
    {
        if (source == null)
            yield break; //be a gentleman

        IEnumerator<T> enumerator = source.GetEnumerator();

        iterateAllAndBackToStart:
        while (enumerator.MoveNext()) 
            yield return enumerator.Current;

        enumerator.Reset();
        if(!enumerator.MoveNext())
            yield break;
        else
            yield return enumerator.Current;
goto iterateAllAndBackToStart;
    }
}

    Wenn Sie möchten, gehen Sie weiter, machen Sie eine CircularList und halten Sie die gleichen enumerator zu überspringen Skip() beim drehen, so wie in deinem Beispiel.

    InformationsquelleAutor der Antwort Davi Fiamenghi

Schreibe einen Kommentar