使用尾递归的 DoublyLinkedList - InsertItem

Question

我目前正在尝试创建一个使用尾递归的双向链表。

我的 addItem 已完全正常工作。我的 InsertItem 在指定索引处成功插入和项目。但是它会删除那里的任何项目并且不会移动所有数据。当尝试在索引 1 处添加时，我的代码也会崩溃。我已经注释掉了我试图让它工作的代码。

这是我的节点 class:

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

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

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

  public String GetDataItem()
  {
    return value;
  }

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

  public DLLNode GetPreviousNode()
  {
    return previous;
  }

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

  public DLLNode GetNextNode()
  {
    return next;
  }

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

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


  public void InsertItemHelper(String value, int indexToInsert, int current, DLLNode currNode)
  {
      /*if (indexToInsert == 1)
      {
          DLLNode newNode = new DLLNode(value);
          currNode.setNextNode(newNode);
      }*/
      if (current == indexToInsert-2)
      {
          DLLNode newNode = new DLLNode(value); 
          currNode.setNextNode(currNode.GetNextNode().GetNextNode());
          newNode.setNextNode(currNode.GetNextNode());
          currNode.setNextNode(newNode);
          newNode.setPrevious(currNode);   
      }
      else
      {
          InsertItemHelper(value, indexToInsert, current+1, currNode.GetNextNode());
      }
  }

    public void DeleteItemHelper(int indexToDelete, int current, DLLNode currNode)
  {
      if (current == indexToDelete-2)
      {
          currNode.setNextNode(currNode.GetNextNode().GetNextNode());
      }
      else
      {
          DeleteItemHelper(indexToDelete, current+1, currNode.GetNextNode());
      }
  }



}

这是我的 DoublyLinkedList class。非常感谢任何帮助和提示。

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

  }


  public int GetNoOfItems()
  {
    return noOfItems;
  }

  /* Returns the String value held at index (base zero) or null if the index
   * is out of bounds */
  public String GetItemByIndex(int index)
  {
    return null;
  }


  public DLLNode GetNodeByIndex(int index)
  {
    return null;
  }


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



  public void InsertItem(int index, String value)
  {
      if (index > noOfItems)
      {
          AddItem(value);
      }
      else {
        head.InsertItemHelper(value, index, 0, head); 
        noOfItems++;
      }


  }


  public void DeleteItem(int index)
  {

          if (index ==0)
          {
              System.out.println("Out of Bounds");
          }
          if (index > noOfItems)
          {
             System.out.println("Out of Bounds");
          }
          if (head == null)
          {
              System.out.println("No Item to remove");
          }
          else if (index == 1)
          {
              head = head.GetNextNode();
              noOfItems--;
          }
          else
          {
              head.DeleteItemHelper(index, 0, head);
              noOfItems--;
          }

  }

  public int getNoOfItems()
  {
      return this.noOfItems;
  }

  public boolean isEmpty()
  {
      return (head == null);
  }


}

Answer 1

想想这里发生了什么：

currNode.setNextNode(currNode.GetNextNode().GetNextNode());
newNode.setNextNode(currNode.GetNextNode());
currNode.setNextNode(newNode);
newNode.setPrevious(currNode);

对您的代码段的分析

让A:= currnode; B:=currnode.getNextNode(); C:=currnode.getNextNode();

所以我们有 A -> B -> C

currNode.setNextNode(currNode.GetNextNode().GetNextNode());

A ->C

newNode.setNextNode(currNode.GetNextNode());

新节点 -> C

currNode.setNextNode(newNode);

A -> 新节点 -> C

newNode.setPrevious(currNode);

从 newNode 退回link 到 A

你可能想做什么

newNode.setNextNode(currNode.getNextNode());

新节点 -> B

现在我们可以将 link 从 currNode 更改为 newNode

currNode.setNextNode(newNode);

A -> 新节点

所以现在你应该有类似 A -> newNode -> B 的东西。不需要再碰 C。

所以现在你可以修复背部links 就大功告成了。

currNode.getNextNode().setPrevious(newNode);

从 B 退回link 到新节点

newNode.setPrevious(currNode);

从 newNode 退回 link 到 currNode

p.s.: 我没有测试这个。我没有研究 if 条件本身，我没有考虑你的 indexToInsert ==1-case 等等。我仍然希望让你知道错误是从哪里来的，并指出你正确的方向...

p.p.s.: 坚持 standard java naming conventions 被认为是好的做法 - 方法名称应以小写字母开头。

使用尾递归的 DoublyLinkedList - InsertItem

DoublyLinkedList using tail recursion - InsertItem

java

algorithm

linked-list

doubly-linked-list