DoublyLinkedList using tail recursion - InsertItem

Question

I'm currently trying to create a DoublyLinked list that uses tail recursion.

I have my addItem fully working. My InsertItem successfully inserts and item at the specified index. However it removes whatever item was there and doesn't move all the data along. My code also crashes when trying to add at index 1. I have commented out the code I attempted to get this working.

Here is my Node 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());
      }
  }



}

And here is my DoublyLinkedList class. Any help and tips much appreciated.

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


}

In my DLLNode class - the methods I am using for Add, Delete and Insert all need to be using tail recursion. So each of them call themselves at the last stage of the function. — benjano
You should start off small. Instead of trying to implement all 3 methods at once, do them one at a time. If you have trouble with a specific one, then it'll be easier to ask for help. — byxor
I'm not asking for help on all 3? My Delete and Add work fine it's just the insertMethod I'm requesting help with. — benjano

dingalapadum dingalapadum · Accepted Answer · 2016-12-13T15:57:17

Think about what's going on here:

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

Analysis of your snippet

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

So we have something like A -> B -> C

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

A ->C

newNode.setNextNode(currNode.GetNextNode());

newNode -> C

currNode.setNextNode(newNode);

A -> newNode -> C

newNode.setPrevious(currNode);

set backlink from newNode to A

What you probably want to do

newNode.setNextNode(currNode.getNextNode());

newNode -> B

now we can change the link from currNode to the newNode

currNode.setNextNode(newNode);

A -> newNode

So now you should have something like A -> newNode -> B. No need to ever touch C.

So now you can fix the backlinks and you're done.

currNode.getNextNode().setPrevious(newNode);

set backlink from B to newNode

newNode.setPrevious(currNode);

set backlink from newNode to currNode

p.s.: I didn't test this. I didn't look into the if-conditions themselves, I didn't think about your indexToInsert ==1-case, etc.. still I hope to have given you an idea where the mistake is coming from and pointed you in the right direction...

p.p.s.: It is considered good practice to stick to the standard java naming conventions - method-names should start with lowercase letters.

DoublyLinkedList using tail recursion - InsertItem

1 Answers