AddFirst() method doesn't work in my Linked List

user_17049306 0
Viewed 110

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!

linked-list java
2 Answers

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
    }
}
user_12215710

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 as a result of 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:

  1. Set next of the newFirst to the node referenced by the head

    newFirst.setNext(head);

  2. Point head to the newFirst node

    head = 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;
    }
}
user_60943480
Related