Don't understand why my addFirst()
method doesn't work. When I ask for the size of list, it returns 1 but I added 3 words. It looks like the program takes only one element and forgets about the previous. I removed all the other irrelevant code and left only the one connected to my question with the addFirst()
method. Here's the code:
Node object:
public class Node<Type> {
private Type data;
private Node<Type> next;
public Node(Type data) {
this.data = data;
next = null;
}
public Type getData() {
return data;
}
public void setData(Type data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
Main Method:
public class MyMain<Type> {
public static void main(String[] args) {
MyList<String> list = new MyList<String>();
System.out.println("The size is: " list.size());
String s1 = "Summer";
String s2 = "Spring";
String s3 = "Winter";
list.addFirst(s2);
list.addFirst(s3);
list.addFirst(s1);
System.out.println("The size is: " list.size());
}
}
Linked List:
public class MyList<Type> {
private Node<Type> head;
public MyList() {
head = null;
}
public int size() {
int length = 0;
Node<Type> current = head;
while (current != null) {
current = current.getNext();
length ;
}
return length;
}
public void addFirst(Type data) {
Node<Type> newFirst = new Node<Type>(data);
if (head == null) {
head = newFirst;
} else {
newFirst = newFirst.getNext();
newFirst = head;
head = newFirst.getNext();
}
}
}
Very confused and would appreciate any help, thank you!
CodePudding user response:
I added comments to your original code, to explain what it actually does.
If you want addFirst
to put the new element at the head of the list, you should change:
public void addFirst(Type data) {
Node<Type> newFirst = new Node<Type>(data);
if (head == null) {
head = newFirst;
} else {
newFirst = newFirst.getNext(); // here you assign null to newFirst
newFirst = head; // head you assign the old head to newFirst
head = newFirst.getNext(); // here you assign null to head, making the list empty
}
}
to:
public void addFirst(Type data) {
Node<Type> newFirst = new Node<Type>(data);
if (head == null) {
head = newFirst;
} else {
newFirst.setNext(head); // the old head of the list should be the
// next element of the new Node
head = newFirst; // make the new Node the head of the list
}
}
CodePudding user response:
Your logic inside the else
block of the addFirst
method is not correct.
Your code in the addFirst
method creates a new node, saves its reference in newFirst
variable but then immediately discards the new node after the following statement:
newFirst = newFirst.getNext();
Following statement then points newFirst
to the node referenced by the head
which is the first node inserted in the list.
newFirst = head;
Finally, you assign null
to head
:
head = newFirst.getNext();
Solution:
What you need to do is:
Set
next
of thenewFirst
to the node referenced by thehead
newFirst.setNext(head);
Point
head
to thenewFirst
nodehead = newFirst;
Full method code:
public void addFirst(Type data) {
Node<Type> newFirst = new Node<Type>(data);
if (head == null) {
head = newFirst;
} else {
newFirst.setNext(head);
head = newFirst;
}
}