I am currently working on creating a DoublyLinkedList which uses tail recursion.
I have managed to get all my methods fully working except my insert item.
It works for inserting at any Index other than 0. I have tried to write an if statement which deals with this and my code still runs however although it increments the noOfItems. It never adds the item to my list.
Could the issue be with my toString? Or am I missing something in my if case?
This is my DLLNode 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 == 0)
{
DLLNode newNode = new DLLNode(value);
currNode.GetNextNode().setPrevious(newNode);
}
else if (current == indexToInsert-1)
{
DLLNode newNode = new DLLNode(value);
newNode.setNextNode(currNode.GetNextNode());
currNode.setNextNode(newNode);
currNode.GetNextNode().setPrevious(newNode);
newNode.setPrevious(currNode);
}
else
{
InsertItemHelper(value, indexToInsert, current+1, currNode.GetNextNode());
}
}
public void DeleteItemHelper(int indexToDelete, int current, DLLNode currNode)
{
if (current == indexToDelete-1)
{
currNode.setNextNode(currNode.GetNextNode().GetNextNode());
}
else
{
DeleteItemHelper(indexToDelete, current+1, currNode.GetNextNode());
}
}
}
And this is my DoublyLinkedList class:
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;
}
public String GetItemByIndex(int index)
{
int count = 0;
while (count < index)
{
head = head.GetNextNode();
count++;
}
return head.GetDataItem();
}
public DLLNode GetNodeByIndex(int index)
{
int count = 0;
while (count < index)
{
head = head.GetNextNode();
count++;
}
return head;
}
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);
}
public String toString()
{
DLLNode currentNode = head;
StringBuilder sb = new StringBuilder();
while (currentNode != null) {
sb.append(currentNode.GetDataItem());
if (currentNode.GetNextNode() != null)
{
sb.append(",");
}
currentNode = currentNode.GetNextNode();
}
return sb.toString();
}
}
I have added the following code into my insert item:
if (index ==0)
{
DLLNode newNode = new DLLNode(value);
head.setNextNode(head);
// newNode.next= head.GetNextNode();
head = newNode;
noOfItems++;
}
If I include the commented out line I get an error to do with string builder.
With the line commented out it adds in the linked list at position 0, but doesn't add any of the rest. It does however increment noOfItems correctly.
The following error is what appears:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.util.Arrays.copyOf(Arrays.java:2367) at java.lang.AbstractStringBuilder.expandCapacity(AbstractStringBuilder.java:130) at java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:114) at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:415) at java.lang.StringBuilder.append(StringBuilder.java:132) at ads2.DoublyLinkedList.toString(DoublyLinkedList.java:155) at java.lang.String.valueOf(String.java:2847) at java.lang.StringBuilder.append(StringBuilder.java:128) at ads2.Main.printList(Main.java:62) at ads2.Main.main(Main.java:38) Java Result: 1 BUILD SUCCESSFUL (total time: 1 second)
If you need any more details on the error please let me know.
