0

In java linked lists if head=null then the LinkedList is empty. However when I set head=null and print value of tail the value is displayed. Why is it that we say head==null means that the LinkedList is empty? Why is tail value being displayed when the linked list should be empty? Shouldn't we check id(tail==null)as well?

public class SinglyLinkedList{
  public Node head;
  public Node tail;
  public int size;

  public Node createLL(int num){
    Node node=new Node();
    node.value=num;
    node.next=null;
    head=node;
    tail=node;

    size=1;
    return head;
  }

  public void insertNode(int num,int location){
    Node node=new Node();
    node.value=num;
    
    if(head==null){//Check
      createLL(num);
      return;
    }

    else if(location==0){
      node.next=head;
      head=node;
    }

    else if(location>=size){
      node.next=null;
      tail.next=node;
      tail=node;
    }

    else{
      Node tempNode=head;
      int index=0;

      while(index<location-1){
        tempNode=tempNode.next;
        index++;
      }
     node.next=tempNode.next;
     tempNode.next=node;
    }
    size++;
  }

  public void traverse(){
    if(head==null){//Check
      System.out.println("The linked list is empty");
    }
    Node tempNode=head;
    for(int i=0;i<size;i++){
      System.out.print(tempNode.value);
      if(i!=size-1){
        System.out.print("->");
      }
      tempNode=tempNode.next;
    }
    System.out.println();
  }

  public void deleteNode(int location){
    if(head==null){//Check
      System.out.println("The linked list is not present");
      return;
    }

    else if(location==0){
      head=head.next;
      size--;
      if(size==0){
        tail=null;
      }
    }

    else if(location>=size){
      Node tempNode=head;
      for(int i=0;i<size-1;i++){
        tempNode=tempNode.next;
      }
      if(head==null){
        tail=null;
        size--;
        return;
      }
      tempNode.next=null;
      tail=tempNode;
      size--;
    }

    else{
      Node tempNode=head;
      int index=0;

      while(index<location-1){
        tempNode=tempNode.next;
        index++;
      }
      tempNode.next=tempNode.next.next;
      size--;
    }
  }

Main class

class Main {
  public static void main(String[] args) {
    SinglyLinkedList sLL=new SinglyLinkedList();
    sLL.createLL(5);
    sLL.insertNode(15, 1);
    sLL.insertNode(20, 2);
    sLL.insertNode(39, 3);
    sLL.insertNode(45, 4);

    sLL.traverse();
    
    sLL.head=null;
    System.out.println(sLL.tail.value);
  }
}

Output: 5->15->20->39->45

45

Improve this question

2 Answers 2

Reset to default
0

head being null just means that you cannot reach the first Node anymore. This also implies that you cannot access the whole chain via the next reference, since you've no starting point.
The garbage collector is allowed to "free" all objects which aren't reachable anymore. In your case all nodes except the tail Node, since you still keep a reference to it in your SinglyLinkedList.

So in fact you've an kind-of empty LinkedList, since you cannot correctly access it anymore. But you still keep the tail node alive, since you reference it. The correct solution would be to set tail to null as well, so the garbage collector can also free this node.

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

In insert node and delete node, I have checked if(head==null). If this is true it means that the LinkedList is empty and it returns. However, shouldn't it be if(head==null && tail==null)? Why is it that we only check head as tail still points to the last node after we set head=null? Isn't tail->node also not a LinkedList?
@2019079925 The assumption can be that the list is empty when head is null. But it's not consistent to keep the tail pointing at the "old" end node. Just clear it also up and you are good to go. You are currently simply remembering the last end node you had. This information is of no use when the linked list is no longer there
How do I clear it up? Do I write if(head==null) set tail=null. Where should I put this code?
@2019079925 Usually you'd have a clear method, similar to the official API. The tail reference is simply a helper that is no longer valid nor necessary when you set the head to null. Hence you must set it to null when you clear the list itself (by setting head to null).
@2019079925 You can have a look at the openjdk implementation here. The relevant part is first = last = null; in clear(). last is your tail. It's helpful for adding nodes, but is no longer valid when you cleared your LinkedList.
|
0

By that assignment you make your list instance inconsistent. An empty list would have both its head and tail member set to null and its size equal to 0.

That's why you should not just alter a member of your class like that. You should probably even make them private to prevent the caller from doing such manipulations. If you want to have a way to empty a list, then create a proper method for it, which takes care of keeping the properties consistent:

public void clear() {
    head = tail = null;
    size = 0;
}

And in your main code, just call that sLL.clear() method.

If you keep a reference to a node, you will always be able to access it. To really lose a node, you must get rid of all references to it.

Improve this answer

7 Comments

In insert node and delete node, I have checked if(head==null). If this is true it means that the LinkedList is empty and it returns. However, shouldn't it be if(head==null && tail==null)? Why is it that we only check head as tail still points to the last node after we set head=null? Isn't tail->node also not a LinkedList?
No, it is OK as it is. You must assume that the list is consistent, i.e. when head is null it follows that tail is null. This consistency must be maintained by all operations executed on the list, and that is why I propose to make these members private, so that only the class methods are responsible for manipulating these members, and can at the same time guarantee their consistency.
So every time head is set to null, also tail should be set to null. This should be imposed by your code. If ever you have the situation that head is null and tail is not, you have an inconsistency, and that must be avoided.
This is the thing that I don't understand "head is null it follows that the tail is null". How is it that when the head becomes null tail automatically becomes null? Where is this given in the above code? This is a code from a Udemy course that I am learning so please be understanding.
I am not saying it automatically becomes null. I am saying that the code of this class is responsible for doing all that is necessary that this invariant is maintained. So it should not be allowed that any code out there just decides to assign null to head. This should not be allowed, as indeed then tail will still be a node reference (and also size would not be reset to 0, so also that would be inconsistent).
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.