I am trying to implement a singly-linked-list with head and tail references. In order to test my script, I created a toString() method that would be able to print out each node in the list. However, it appears that I am entering an infinite loop every time I call the method and I cannot seem to figure out why. Would anyone be able to give me some insight on this? See below for my SinglyLinkedList.java file.
import java.util.NoSuchElementException;
import java.util.*;
/**
* Your implementation of a Singly-Linked List.
*/
public class SinglyLinkedList<T> {
/*
* Do not add new instance variables or modify existing ones.
*/
private SinglyLinkedListNode<T> head;
private SinglyLinkedListNode<T> tail;
private int size;
/*
* Do not add a constructor.
*/
/**
* Adds the element to the front of the list.
*
* Method should run in O(1) time.
*
* @param data the data to add to the front of the list
* @throws java.lang.IllegalArgumentException if data is null
*/
public void addToFront(T data) {
if (data == null){
throw new IllegalArgumentException("Data cannot be null");
}
SinglyLinkedListNode<T> newNode = new SinglyLinkedListNode<T>(data);
if (head == null){
head = newNode;
tail = newNode;
}
newNode.setNext(head);
head = newNode;
size ;
}
/**
* Adds the element to the back of the list.
*
* Method should run in O(1) time.
*
* @param data the data to add to the back of the list
* @throws java.lang.IllegalArgumentException if data is null
*/
public void addToBack(T data) {
if (data == null){
throw new IllegalArgumentException("Data cannot be null");
}
if (head == null){
head = new SinglyLinkedListNode<T>(data);
}
else {
SinglyLinkedListNode<T> current = head;
while (current.getNext() != null){
current = current.getNext();
}
current.setNext(new SinglyLinkedListNode<T>(data));
}
size ;
}
/**
* Removes and returns the first data of the list.
*
* Method should run in O(1) time.
*
* @return the data formerly located at the front of the list
* @throws java.util.NoSuchElementException if the list is empty
*/
public T removeFromFront() {
if (head == null){
throw new NoSuchElementException("You cannot remove elements from the front of an empty list");
}
SinglyLinkedListNode<T> var = head;
head = head.getNext();
size--;
return var.getData();
}
/**
* Removes and returns the last data of the list.
*
* Method should run in O(n) time.
*
* @return the data formerly located at the back of the list
* @throws java.util.NoSuchElementException if the list is empty
*/
public T removeFromBack() {
if (head == null){
throw new NoSuchElementException("You cannot remove an element from the back of an empty list");
}
else if (head.getNext() == null){
SinglyLinkedListNode<T> var = head;
head = null;
}
SinglyLinkedListNode<T> current = head;
while (current.getNext().getNext() != null){
current = current.getNext();
}
SinglyLinkedListNode<T> var = current.getNext();
current.setNext(null);
size--;
return var.getData();
}
/**
* Returns the head node of the list.
*
* For grading purposes only. You shouldn't need to use this method since
* you have direct access to the variable.
*
* @return the node at the head of the list
*/
public SinglyLinkedListNode<T> getHead() {
// DO NOT MODIFY THIS METHOD!
return head;
}
/**
* Returns the tail node of the list.
*
* For grading purposes only. You shouldn't need to use this method since
* you have direct access to the variable.
*
* @return the node at the tail of the list
*/
public SinglyLinkedListNode<T> getTail() {
// DO NOT MODIFY THIS METHOD!
return tail;
}
/**
* Returns the size of the list.
*
* For grading purposes only. You shouldn't need to use this method since
* you have direct access to the variable.
*
* @return the size of the list
*/
public int size() {
// DO NOT MODIFY THIS METHOD!
return size;
}
public String toString() {
String answer = "";
SinglyLinkedListNode<T> current = head;
while (current != null){
answer = current "";
current = current.getNext();
}
return answer;
}
public static void main(String[] args){
SinglyLinkedList<Integer> list = new SinglyLinkedList<>();
list.addToFront(1);
System.out.println(list.toString());
}
}
And here is my SinglyLinkedListNode.java file.
/**
* Node class used for implementing the SinglyLinkedList.
*
* DO NOT MODIFY THIS FILE!!
*
public class SinglyLinkedListNode<T> {
private T data;
private SinglyLinkedListNode<T> next;
/**
* Constructs a new SinglyLinkedListNode with the given data and next node
* reference.
*
* @param data the data stored in the new node
* @param next the next node in the list
*/
SinglyLinkedListNode(T data, SinglyLinkedListNode<T> next) {
this.data = data;
this.next = next;
}
/**
* Creates a new SinglyLinkedListNode with only the given data.
*
* @param data the data stored in the new node
*/
SinglyLinkedListNode(T data) {
this(data, null);
}
/**
* Gets the data.
*
* @return the data
*/
T getData() {
return data;
}
/**
* Gets the next node.
*
* @return the next node
*/
SinglyLinkedListNode<T> getNext() {
return next;
}
/**
* Sets the next node.
*
* @param next the new next node
*/
void setNext(SinglyLinkedListNode<T> next) {
this.next = next;
}
}
CodePudding user response：
Note that there are various errors in your code; this question is specifically about why your toString seems to 'hang' so I'll answer just that one here. But, just to give an example, your toString just "prints" current, which is an object, hence, short for current.toString(), but SLLN has no toString method and thus isn't going to produce useful information. You presumably want current.getData().toString() instead.
It has nothing in particular to do with your toString method. It's your addToFront method that is broken in a way that causes endless loops.
Learn to debug. It's easy! You think up some example input, then you 'run the code in your head' - you go through your code line by line and you become the computer: Get a scratch pad out if you have to, but write down every change to every variable, every effect. Then, use a debugger, or if you don't want to learn how to use one right now, you can fake it by adding a ton of System.out.println statements that print the values of various expressions/variables, and compare what you think ought to happen with what actually happens. Every time you find a disagreement: You found a bug.
For example, imagine that your SinglyLinkedList is empty, and then add an element to it by invoking addToFront:
if (data == null){ throw new IllegalArgumentException("Data cannot be null"); }
It's not null so this part does what we'd expect: 'hop over' the if block, nothing happens here. You could debug this by simply witnessing the IAEx is not occurring.
SinglyLinkedListNode<T> newNode = new SinglyLinkedListNode<T>(data); if (head == null){ head = newNode; tail = newNode; }
This is a brand new list so that if block should be entered. If you're not 100% certain you should add some sysout statements in there so that you know this happens. Point is, head and tail and newNode are now all variables that are all pointing at the exact same object - that one node you just made to represent the data being added.
newNode.setNext(head); head = newNode; size ;
Perhaps you missed this, but, this code will run too! Why wouldn't it?
newNode is pointing at the object you just made. So is head. So now you're telling your new node that its next node is.. itself. Which means that any attempt to traverse this node will be infinite - it's just a thing that points to itself. Perhaps you intended this part to be in an else block.
An alterate route to debug this is to debug the toString process. Use a debugger, or add some sysout statements to toString itself (a tad dangerous, make sure you just print strings and primitives - or you may end up with infinite recursion; at least that will cause a StackOverflowError that'll give away what is happening, though) - and you'd have noticed that it keeps calling itself over and over again. Then use some common sense which should lead you to the conclusion that a node must be pointing at itself or otherwise there is now a 'loop' in the node's .next chain, and from there you'd get back to figuring it out, or at least you'd know to look at addToFront once you've drawn that conclusion.
This never goes away - expert programmers just become better at the process and can intuit more. In other words, getting experienced at debugging is, pretty much by definition, a significant and requisite step in becoming a programmer.
CodePudding user response：
From your addToFront() method:
[...] SinglyLinkedListNode<T> newNode = new SinglyLinkedListNode<T>(data); if (head == null){ head = newNode; tail = newNode; } newNode.setNext(head); [...]
When you start with a fresh linked list and add the first element ever with this method, you will create a new node newNode, which you save in this.head and this.tail. However, you also change the next field in the new created SinglyLinkedListNode<T> instance to head via the newNode.setNext(head); method call. This will set the next field of the newNode instance to the newNode instance itself, creating a loop.
Maybe you want to do something like if-else to check if it is a new list or an existing list like this:
SinglyLinkedListNode<T> newNode = new SinglyLinkedListNode<T>(data);
if (head == null){
head = newNode;
tail = newNode;
} else {
newNode.setNext(head);
head = newNode;
}