Delete Item - Doppelt verknüpfte Liste mit Tail Rekursion

Question

Ich lerne gerade Doubly Linked Lists.

Ich habe es geschafft, eine doppelt verknüpfte Liste zu schreiben, die fast 100% funktional war. Allerdings muss ich lernen, wie man es mit Tail-Rekursion schreibt.

Unten ist mein DLLNode Code:

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) { 
      // Stopping condition 
      DLLNode newNode = new DLLNode(value); 
      this.next = newNode; 
     } else { 
      // Recurse 
      this.next.addItem(value); 
     } 
    } 

} 

ich haben es geschafft, meine AddItem bekommen arbeiten Endrekursion mit und ich suche jetzt in Arbeits löschen Artikel zu bekommen. Ich vermute, dass ich wie addItem deleteItem zu meinem DLLNode hinzufügen muss.

Unten ist meine DoublyLinkedList Klasse:

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 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 
     { 
      int position = 0; 
      DLLNode currentNode = head; 

      while (currentNode != null) { 
       if (position == index-1) { 
        currentNode.setNextNode(
          currentNode.GetNextNode().GetNextNode()); 
        noOfItems--; 
        break; 
       } 
       currentNode = currentNode.GetNextNode(); 
       position++; 
      } 
     } 
    } 
} 

Irgendwelche Tipps, wo kann ich mit der Umwandlung von diesem Code beginnen würde sehr geschätzt werden.

Mit freundlichen Grüßen, Ben.

P.S. Entschuldigung für die Art und Weise, wie der Code formatiert wurde - ich habe versucht, es zu reparieren, aber es scheint nicht zu sortieren. Kann jemand gut darin sein, Code auf ihr zu formatieren, bitte versuchen Sie es zu sortieren?

Answer 1

private void DeleteItemHelper(final int indexToDelete, int curIndex, DLLNode curNode) { 
    if (curIndex == indexToDelete) { 
     // Handle removing a node with both a previous and next nodes. 
    } 

    else { 
     DeleteItemHelper(indexToDelete, curIndex + 1, curNode.getNextNode()); 
    } 
} 


public void DeleteItem(int index) { 
    DeleteItemHelper(index, 0, head); 
} 

Answer 2

Ohne weitere Tests denke ich, dass Sie den Kopf Referenz des Knotens nach dem entfernt Knoten neu eingestellt werden vergessen zu:

if (position == index-1) { 
    // Tail of currentNode is set to the node following 
    // next node, but head of that node still points to the 
    // node which should be removed from list 
    currentNode.setNextNode(
     currentNode.GetNextNode().GetNextNode()); 
    noOfItems--; 
    break; 
}