DoublyLinkedList使用尾递归 - InsertItem

Question

我目前正在尝试创建使用尾递归的DoublyLinked列表。

我有我的addItem充分工作。我的插入项成功插入并在指定的索引项。但是，它会删除所有项目，并且不会移动所有数据。我的代码在试图在索引1处添加时也崩溃了。我已经注释掉了我试图使其工作的代码。

这里是我的节点类：

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类。任何帮助和提示非常感谢。

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();

因此，我们必须像一个 - “乙 - > C

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

A - >Ç

newNode.setNextNode(currNode.GetNextNode()); 

newNode - “ç

currNode.setNextNode(newNode); 

A - > newNode - 从newNode>Ç

newNode.setPrevious(currNode); 

组反向链接到甲

---

什么，你可能想要做

newNode.setNextNode(currNode.getNextNode()); 

newNode - >乙

现在我们可以从currNode链接更改为newNode

currNode.setNextNode(newNode); 

A - > newNode

所以，现在你应该有像A - > newNode - > B没有n因此永远碰触C.

所以现在你可以修复反向链接，你就完成了。的B

currNode.getNextNode().setPrevious(newNode); 

一套反向链接到newNode

newNode.setPrevious(currNode); 

一套反向从newNode到currNode

P.S：我没有测试这一点。我没有看自己的if条件，我没有考虑你的箱等等。我仍然希望能够告诉你一个错误是从哪里来的，并指出你在正确的方向。 。

pps：遵守standard java naming conventions是一种很好的做法 - 方法名应该以小写字母开头。