Deleting from head of singly linkedlist

Question

I was writing my own linked list implementation as follows, when I tried to perform operation 'deleteElementFromHead' of the linkedlist, I was curious that what I did was enough or not? The method for deletion of element from head is as follows,

public void deleteAtHead()
{
        Node secondNode = this.head.next;
        this.head = secondNode;
        count--;
}

I am in doubt that while exchanging the pointers to delete element at head, the old head element is still in the memory, and may or may not be collected by the garbage collector. Do I need to set that deleted element to null, or need to add some other piece of code in the above method to avoid memory leak.

The complete code piece for the linkedlist is as follows,

package com.nobalg.Linkedist;

public class Node implements Operations {
int data;
Node next,head,tail;
int count = 1;
public Node(int data)
{
    this.data = data;
    this.head=this;
    this.tail = this;
}

/**********This method takes O(n) time************/
public void addNode(int nodeData)
{
    Node node =  new Node(nodeData);
    Node temp = this;
    while(temp.next!=null){
         temp = temp.next;
    }
    temp.next = node;
    count++;
}

/******This operation takes O(1) time********/
public void addAtTail(int nodeData)
{
    Node node = new Node(nodeData);
    tail.next = node;
    tail = tail.next;
    count++;
}

/********This operation takes O(1) time**************/
public void addAtHead(int nodeData)
{
    Node node = new Node(nodeData);
    node.next = head;
    this.head = node;
    count++;
}

/************This operation takes  O(n) time****************/
public void addAtIndex(int index,int nodeData)
{
    if(index < 0 || index >count)
    {
        throw new IllegalStateException();
    }
    Node node =  new Node(nodeData);
    Node tempLast = this.head;
    Node tempCurrent = this.head;
    int locCount = 0;
    while(locCount!=index){
        tempLast = tempCurrent;
        tempCurrent = tempCurrent.next;
        locCount++;
    }
    node.next = tempCurrent;
    if(index == 0)this.head = node;
    else tempLast.next = node;
    count++;
}

/**********This operation takes O(n) time in case of singly linked list*************/
public void deleteAtTail()
{
    Node temp = this.head;
    Node locLastNode = null;
    while(temp.next!=null)
    {
        locLastNode = temp;
        temp = temp.next;
    }
    this.tail = locLastNode;
    locLastNode.next = null;
    count--;
}

public void deleteAtHead()
{
    Node secondNode = this.head.next;
    this.head = secondNode;
    count--;
}

public void deleteAtIndex()
{
    //implementation pending
}
public int size()
{
    return count;
}

public void display()
{
    Node temp = this.head;
    for(int  i = 0 ; i < count; i++)
    {
        System.out.println(temp.data);
        temp = temp.next;
    }
}
  }

Answer 1

I guess you missed one of the case when tail and head are pointing to the same node. Suppose there is only one element and and you call the deleteAtHead(). In that case the Node has two reference one is head and another is tail and you are only de-referencing the (this.head = secondNode; count--;) head node, What about the tail node. Isn't it still referencing the first node. Here the your program breaks. You should consider the case. If any object has zero reference then you don't need to worry about that object, GC will collect/free that object. But you need to make sure you are de-referencing all those objects properly.

Answer 2

The garbage collector automatically runs in the background of JVM. If a resource is not alloted to any variable or not given any reference it gets cleaned by the garbage collector.

Below is the code for deletion at a position.

    Node deleteAtIndex(Node head, int position) {
        Node temp = head;
        if(head == null)
            return null;
        else if(position == 0){
            head=head.next;
        }
        else{
            int currentIndex = 0;
            while(temp != null && currentIndex <= position-2){
                currentIndex++;
                temp=temp.next;
            }
            Node temp2 = temp.next.next;
            temp.next=temp2;
        }
        return head;
    }

Answer 3

the old head element is still in the memory, and may or may not be collected by the garbage collector. Do I need to set that deleted element to null, or need to add some other piece of code in the above method to avoid memory leak

So, you need to understand this, JVM takes care of GC, you don't have much control there. Also, setting null doesn't mean you get allocated memory back immediately.

For example :

Object obj = new Object ();

Creates an object and allocate\reserve memory in JVM. Now, setting obj=null means obj has null reference, but whatever memory was allocated still exist with no reference (and eligible for GC).

Answer 4

In exchanging of pointers

Node secondNode = this.head.next;
this.head = secondNode;
count--;

in code snippet above, the old element still remains in memory and this is the case of dangling pointers. And for your question how to free the memory from heap refer this question

You can also write this in one line this.head = this.head.next and JVM will most probably take care of GARBAGE COLLECTION...

However, stick with the two line you wrote. It is a better approach.

Hope this helps :)

Answer 5

Below code of yours

public void deleteAtHead()
{
        Node secondNode = this.head.next;
        this.head = secondNode;
        count--;
}

has some of the edge cases missing, like it will throw NPE, when LL is empty and other is when it has just 1 node. anyway your question is below :-

I am in doubt that while exchanging the pointers to delete element at head, the old head element is still in the memory, and may or may not be collected by the garbage collector. Do I need to set that deleted element to null, or need to add some other piece of code in the above method to avoid memory leak.

So yes, in this case, old head element would still be in the memory, but it won't be pointing to the head of your LL, so you won't get the wrong result. and after sometime when GC runs then it would be collected by it, whether you set it to NULL or not.

Read more about what happens when you explicitly assign NULL to a refrence in this SO answer :- Does assigning objects to null in Java impact garbage collection?