DoublyLinkedList с использованием хвостовой рекурсии - InsertItem

Question

В настоящее время я пытаюсь создать список DoublyLinked, который использует рекурсию хвоста.

У меня есть мой addItem полностью работающий. Мой InsertItem успешно вставляет и элемент по указанному индексу. Однако он удаляет любой элемент и не перемещает все данные. Мой код также сбой при попытке добавить в индекс 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();

Таким образом, мы имеем что-то вроде A -> B - > C

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

А -> С

newNode.setNextNode(currNode.GetNextNode()); 

newNode -> С

currNode.setNextNode(newNode); 

А -> newNode -> С

newNode.setPrevious(currNode); 

множество Обратной от newNode до А

---

То, что вы, вероятно, хотите сделать

newNode.setNextNode(currNode.getNextNode()); 

newNode -> B

теперь мы можем изменить ссылку от currNode к newNode

currNode.setNextNode(newNode); 

А -> newNode

Итак, теперь у вас должно быть что-то вроде A -> newNode -> B. Нет n чтобы дотронуться до C.

Итак, теперь вы можете исправить обратные ссылки, и все готово.

currNode.getNextNode().setPrevious(newNode); 

набор Обратной от B до newNode

newNode.setPrevious(currNode); 

набор обратной из newNode в currNode

p.s .: Я не проверял это.Я не задумывался о самих условиях if, я не думал о вашем indexToInsert ==1 -case и т. Д., Но я надеюсь, что дал вам представление о том, откуда происходит ошибка, и указал вам в правильном направлении. .

pps: считается хорошей практикой придерживаться standard java naming conventions - имена методов должны начинаться с строчных букв.