public class DoubleLinkedList<T> implements DoubleLinkedListADT<T> { // Double l
ID: 3556346 • Letter: P
Question
public class DoubleLinkedList<T> implements DoubleLinkedListADT<T> {
// Double linked list node class
public class DoubleLinkedListNode<T> implements Cloneable {
T info;
DoubleLinkedListNode<T> next;
DoubleLinkedListNode<T> back;
public DoubleLinkedListNode() {
info = null;
next = null;
back = null;
}
public String toString() {
return info.toString();
}
}
protected int count; // number of nodes
protected DoubleLinkedListNode<T> first; // reference to first node
protected DoubleLinkedListNode<T> last; // reference to last node
public DoubleLinkedList() {
first = null;
last = null;
count = 0;
}
public void initializeList() {
first = null;
last = null;
count = 0;
}
public boolean isEmptyList() {
return (first == null);
}
public T front() {
return first.info;
}
public T back() {
return last.info;
}
public int length() {
return count;
}
public void print() {
DoubleLinkedListNode<T> current;
current = first;
while (current != null) {
System.out.print(current + " ");
current = current.next;
}
}
public void reversePrint() {
DoubleLinkedListNode<T> current;
current = last;
while (current != null) {
System.out.print(current.info + " ");
current = current.back;
}
}
public boolean search(T searchItem) {
boolean found;
DoubleLinkedListNode<T> current;
found = false;
current = first;
while (current != null && !found) {
Comparable<T> temp = (Comparable<T>) current.info;
if (temp.compareTo(searchItem) >= 0)
found = true;
else
current = current.next;
}
if (found)
found = current.info.equals(searchItem);
return found;
}
public void insertNode(T insertItem) {
DoubleLinkedListNode<T> current;
DoubleLinkedListNode<T> trailCurrent = null;
DoubleLinkedListNode<T> newNode;
boolean found;
newNode = new DoubleLinkedListNode();
newNode.info = insertItem;
newNode.next = null;
newNode.back = null;
if (first == null) {
first = newNode;
last = newNode;
count++;
} else {
found = false;
current = first;
while (current != null && !found) {
Comparable<T> temp = (Comparable<T>) current.info;
if (temp.compareTo(insertItem) >= 0)
found = true;
else {
trailCurrent = current;
current = current.next;
}
}
if (current == first) {
first.back = newNode;
newNode.next = first;
first = newNode;
count++;
} else {
if (current != null) {
trailCurrent.next = newNode;
newNode.back = trailCurrent;
newNode.next = current;
current.back = newNode;
} else {
trailCurrent.next = newNode;
newNode.back = trailCurrent;
last = newNode;
}
count++;
}
}
}
public void deleteNode(T deleteItem) {
DoubleLinkedListNode<T> current;
DoubleLinkedListNode<T> trailCurrent;
boolean found;
if (first == null)
System.err.println("Cannot delete from an " + "empty list.");
else {
if (first.info.equals(deleteItem)) {
current = first;
first = first.next;
if (first != null) {
first.back = null;
} else
last = null;
count--;
} else {
found = false;
current = first;
while (current != null && !found) {
Comparable<T> temp = (Comparable<T>) current.info;
if (temp.compareTo(deleteItem) >= 0)
found = true;
else
current = current.next;
}
if (current == null)
System.out.println("The item to be deleted "
+ "is not in the list.");
else if (current.info.equals(deleteItem)) {
trailCurrent = current.back;
trailCurrent.next = current.next;
if (current.next != null)
current.next.back = trailCurrent;
if (current == last)
last = trailCurrent;
count--;
} else
System.out.println("The item to be " + "deleted is not in "
+ "list.");
}
}
}
public String recursiveToString() {
DoubleLinkedListNode<T> current = first;
String name = "";
while (current != null) {
name = (String) current.info;
current = current.next;
return name + " - ";
}
recursiveToString();
return name;
}
public String backwardsString() {
DoubleLinkedListNode<T> current = last;
String name = (String) current.info;
current = current.back;
while (current != null) {
name = name + " - " + (String) current.info;
current = current.back;
}
return name;
}
public String recursiveBackwardsString() {
// TODO Auto-generated method stub
return null;
}
public void copy(DoubleLinkedList<T> otherList) {
DoubleLinkedListNode<T> newNode;
DoubleLinkedListNode<T> current;
first = null;
if (otherList.first == null) {
first = null;
last = null;
count = 0;
} else {
count = otherList.count;
current = otherList.first;
first = new DoubleLinkedListNode();
first.info = current.info;
first.next = null;
last = first;
current = current.next;
while (current != null) {
newNode = new DoubleLinkedListNode();
newNode.info = current.info;
newNode.next = null;
last.next = newNode;
last = newNode;
current = current.next;
}
}
}
public void reversedCopy(DoubleLinkedList<T> otherList) {
DoubleLinkedListNode<T> newNode;
DoubleLinkedListNode<T> current;
count = otherList.count;
current = otherList.last;
last.info = current.info;
last.next = null;
first = last;
current = current.next;
while (current != null) {
newNode = new DoubleLinkedListNode();
newNode.info = current.info;
newNode.next = null;
first.next = newNode;
first = newNode;
current = current.next;
}
}
public boolean equals(Object o) {
if (this == o) {
return true;
} else
return false;
}
public String toString() {
DoubleLinkedListNode<T> current = first;
String name = (String) current.info;
current = current.next;
while (current != null) {
name = name + " - " + (String) current.info;
current = current.next;
}
return name;
}
}
I get these errors when i run my client.
Exception in thread "main" java.lang.StackOverflowError
at Assignment4.DoubleLinkedList.recursiveToString(DoubleLinkedList.java:212)
at Assignment4.DoubleLinkedList.recursiveToString(DoubleLinkedList.java:212)
at Assignment4.DoubleLinkedList.recursiveToString(DoubleLinkedList.java:212)
at Assignment4.DoubleLinkedList.recursiveToString(DoubleLinkedList.java:212)
at Assignment4.DoubleLinkedList.recursiveToString(DoubleLinkedList.java:212)
at Assignment4.DoubleLinkedList.recursiveToString(DoubleLinkedList.java:212)
Explanation / Answer
public String recursiveToString() {
return recursiveToString(first);
}
private String recursiveToString(DoubleLinkedListNode<T> node) {
if (node == null)
return "";
String left = recursiveToString(node.next);
if (left.isEmpty())
return node.info.toString();
return node.info.toString() + " - " + left;
}
public String recursiveBackwardsString() {
return recursiveBackwardsString(last);
}
private String recursiveBackwardsString(DoubleLinkedListNode<T> node) {
if (node == null)
return "";
String left = recursiveBackwardsString(node.back);
if (left.isEmpty())
return node.info.toString();
return node.info.toString() + " - " + left;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.