c#中的反向双向链表

Question

我正在尝试反转循环双向链表，它看起来像这样：

这是我的节点 class:

       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;
       }
   }

这是我的链接列表的一部分 class，这是我存储的反向函数：

 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)
       {

       }
    }

我完全坚持使用这个 Reverse() 函数。有帮助吗？

Answer 1

与其反转列表，不如编写几个方法来根据传入的方向标志获取列表的 "next" 和 "previous" 节点：

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;
}

您可以将 bool forward 替换为具有值 Forwards 和 Backwards 的枚举，如果这样会使代码更易于阅读。

Answer 2

反转链表的算法很简单：

列表是空的还是只有一个元素？如果是，那就已经反了。
否则，创建一个新的空列表。在循环中，从旧列表中删除第一项并将其添加到新列表的开头。循环直到第一个列表为空。

所以，把它分解成更小的部分。您能否编写以下方法：(1) 检查列表是否为空 (2) 或是否有一个元素 (3) 从非空列表中删除第一项，(4) 将一项放在列表的头部？如果你会写这四个方法，那么你可以将它们组合在一起写出Reverse。

这就是您解决编程问题的方式；编程就是将复杂问题分解为更简单的问题，解决更简单的问题，然后组合解决方案。

Answer 3

如果您想反转当前列表 - 那么这应该可行：

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)
}

第一行检查空列表或单个元素列表。主循环遍历列表，交换前一个和下一个节点，当它返回到头节点时停止。结果是一个颠倒的列表。

Answer 4

谢谢大家，我已经找到解决方法了

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

c#中的反向双向链表

reverse doubly linked list in c#

c#

linked-list

doubly-linked-list