Reputation: 379
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);
}
}
Upvotes: 0
Views: 62
Reputation: 2175
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.
Upvotes: 1