java - 使用尾递归的双向链表

Question

我正在努力使我的双向链表使用尾递归。

public class DoublyLinkedList
{
    private int noOfItems;
    private DLLNode head;
    private DLLNode tail;
  // Default constructor
  public DoublyLinkedList()
  {
     head = null;
     tail = null;
     this.noOfItems = 0;

  }

public void AddItem(String value)
{
   DLLNode newNode = new DLLNode(value);

   if (head == null)
   {
       head = newNode;
       noOfItems++;
   }
   else {
       DLLNode current = head;

       while(current != null) {
           if (current.GetNextNode() == null) {
               current.setNextNode(newNode);

               newNode.setPrevious(newNode);
               noOfItems++;
               break;
           }
           current = current.GetNextNode();

           }
       }

   }
}

我的节点类如下:

public class DLLNode
{
    private DLLNode previous;
    public DLLNode next;
    private String value;

    public DLLNode(String value)
    {
        this.value = value;
    }
  /* This method returns the String item of data held in this node */
  public String GetDataItem()
  {
    return value;
  }

  public void setDataItem()
  {
      this.value = value;
  }

  /* This method returns the node immediately prior to this node in the list or
   * null if there is no such node */
  public DLLNode GetPreviousNode()
  {
    return previous;
  }

  public void setPrevious(DLLNode previous)
  {
      this.previous = previous;
  }

  /* This method returns the node immediately after this node in the list or null
   * if there is no such node. */
  public DLLNode GetNextNode()
  {
    return next;
  }

  public void setNextNode(DLLNode next)
  {
      this.next = next;
  }

   public void AddItem(String value)
    {
       if (next == null)
       {
           next = new DLLNode(value);
       }
       else
           next.AddItem(value);
    }



}

这是我添加项目的代码。我也尝试过使用尾递归，代码如下所示:

 public void AddItem(String value)
  {
       if (head == null)
       {
           head = new DLLNode(value);
           noOfItems++;
       }
       else {

          head.AddItem(value);
       }

 }

我写的递归版本有效。但是它不是双向链接的。

我理解它是一个双向链表，一个节点需要知道接下来会发生什么以及它之前发生了什么。因此，在我的添加项目中，我是否需要让下一个节点知道它之前发生了什么？如果是的话，有什么关于如何做到这一点的建议吗？

提前致谢。

Answer 1

使用我自己的假设 Node 类——您可以将其调整为您的 DLLNode:

void addItem(Node head, Node item) {
     if(node.next == null) {
          // Stopping condition
          node.next = item;
          item.previous = node;
     } else {
          // Recurse
          addItem(node.next, item);
     }
}

或者，多一点 OO，假设这段代码是 Node 的一部分，只需将 head 替换为 this，您需要的方法更少参数:

void addItem(Node item) {
     if(this.next == null) {
          // Stopping condition
          this.next = item;
          item.previous = this;
     } else {
          // Recurse
          this.next.addItem(item);
     }
}

或者，如果您不想传递 Node，而是创建一个:

public void addItem(String value) {
     if(this.next == null) {
          // Stopping condition
          Node newNode = new Node(value, this, null);
          this.next = newNode;
     } else {
          // Recurse
          this.next.addItem(value);
     }
}

这里假设有一个构造函数:

public Node(String value, Node previous, Node next) {
     this.value = value;
     this.previous = previous;
     this.next = next;
}

我认为这很好地展示了基础知识。您可以通过使用 getters/setters 等来改进它。

我已经为您提供了 Node 的方法，但是您有一个环绕它的 DoublyLinkedList 类。列表类作为节点上方法的薄包装器是很常见的:

 public class DoublyLinkedList {
       private Node head;

       public addItem(String value) {
            head.addItem(value);
       }
 }

(您还需要处理 head 为 null 的情况。为简洁起见，我将其省略)

请注意，在 Java 中，这种递归解决方案并不理想，因为该语言不会优化尾递归，对于长列表，您会遇到堆栈溢出。迭代解决方案不消耗堆栈。