Reverse doppelt verknüpfte Liste in C#

Question

Ich bin doppelt gelinkten Liste rückgängig zu versuchen, die wie folgt aussieht:

Hier ist meine Klasse Node ist:

 private class Node<T> 
    { 
     public T Data { get; set; } 
     public Node<T> PreviousNode { get; set; } 
     public Node<T> NextNode { get; set; } 

     public Node(object data, Node<T> next, Node<T> previous) 
     { 
      Data = (T) data; 
      PreviousNode = previous; 
      NextNode = next; 
     } 
    } 

Und hier ist ein Teil meiner verlinkte Liste Klasse, hier ist mein Reverse funtion gespeichert ist:

public class DoublyLinkedList<T> :IList<T> 
{ 
    private Node<T> headerNode; 
public DoublyLinkedList() 
{ 
     headerNode = new Node<T>(null, null, null); 

     headerNode.NextNode  = headerNode; 
     headerNode.PreviousNode = headerNode; 
     Count = 0; 
} 

    public void Insert(int index, T item) 
    { 
     Node<T> node; 

     if (index == Count) 
      node = new Node<T>(item, headerNode, headerNode.PreviousNode);                 
     else 
     { 
      Node<T> tmp = FindNodeAt(index); 

      node = new Node<T>(item, tmp, tmp.PreviousNode); 
     } 

     node.PreviousNode.NextNode = node; 
     node.NextNode.PreviousNode = node; 

     Count++; 

    } 
public void Reverse() 
    { 
     Node<T> temp; 
     for (Node<T> node = headerNode.NextNode; node != headerNode; node = node.NextNode) 
     { 

     } 
    } 

ich mit dieser Funktion reverse() komplett fest. Irgendeine Hilfe?

Answer 1

Wenn Sie die aktuelle Liste umkehren wollen - dann sollte diese Arbeit:

public void Reverse() 
{ 
    if (count < 2) 
    return; 

    Node<T> node = headerNode; 
    do 
    { 
     Node<T> temp = node.NextNode; 
     node.NextNode = node.PreviousNode; 
     node.PreviousNode = temp; 
     node = temp; 
    } 
    while (temp != headerNode) 
} 

Die ersten Zeilen prüfen leer oder Einzelelementliste. Die Hauptschleife durchläuft die Liste, indem sie die vorherigen Knoten tauscht und stoppt, wenn sie zum Kopfknoten zurückkehrt. Das Ergebnis ist eine umgekehrte Liste.

Answer 2

Anstatt die Liste zu umkehren, warum nicht ein paar Methoden, die den „next“ und „Zurück“ Knoten der auf einem Richtungs-Flag abhängig Liste erhalten schreiben, die in übergeben wird:

public Node Next(Node current, bool forward) 
{ 
    return forward ? current.NextNode : current.PreviousNode; 
} 

public Node Previous(Node current, bool forward) 
{ 
    return forward ? current.PreviousNode : current.NextNode; 
} 

Sie bool forward ersetzen könnten durch eine Enum mit Werten Forwards & Backwards wenn das den Code leichter lesbar machen würde.

Answer 3

Der Algorithmus für eine verkettete Liste Umkehren ist sehr einfach:

• die Liste leer oder ein Element? Wenn ja, dann ist es bereits umgekehrt.
• Andernfalls erstellen Sie eine neue leere Liste. Entfernen Sie in einer Schleife das erste Element aus der alten Liste und fügen Sie es zum Anfang der neuen Liste hinzu. Schleife, bis die erste Liste leer ist.

Also, zerlegen Sie es in kleinere Stücke. Können Sie Methoden schreiben, die (1) prüfen, ob eine Liste leer ist (2) oder ein Element (3) das erste Element aus einer nicht leeren Liste entfernen, (4) ein Element auf den Kopf einer Liste setzen? Wenn Sie diese vier Methoden schreiben können, können Sie sie kombinieren, um Reverse zu schreiben.

So sollten Sie sich Ihren Programmierproblemen nähern. Beim Programmieren geht es darum, komplexe Probleme in einfachere Probleme zu zerlegen, einfachere Probleme zu lösen und die Lösungen zu kombinieren.

Answer 4

Danke allen, ich habe die Lösung gefunden.

public void Reverse() 
    { 
     var currNode = headerNode; 
     do 
     { 
      var temp = currNode.NextNode; 
      currNode.NextNode = currNode.PreviousNode; 
      currNode.PreviousNode = temp; 
      currNode = currNode.PreviousNode; 
     } 
     while (currNode != headerNode); 
    }