How to delete tail in Double Link List?

user_15421750 0
Viewed 350

My teacher guides us in this activity on how to delete the tail of the double link list. He created an step by step process or algorithm for us to follow. I followed it, but it doesn't work. Or maybe I am following it wrong. Here is the algorithm

Check if the list is empty

  • If not Empty
    • Check if there is only one node in the list
      • If only one node, set the head and tail reference to null.
      • if more than one node
        • create a temptail to point to next tail (tail.prev)
        • set the prev of the tail and next of temptail to null
        • assign the temptail value to the tail

Here is my code

    public void delTail(){
    DoubleNode temp;
    
   if(isEmpty()){
       return;
   }
   else if(!isEmpty()){
       if(head == tail){
           head = tail = null;
       }
       else{
            temp = tail.next;
            tail.prev = null;
            temp.next = null;
            temp = tail;
       }
   }
    
}

This is the error that i saw error in my terminal

I think that I am following it right or maybe not? Thank you so much for your help :)

This is my constructor*

public class DoubleNode{

public DoubleNode prev;
public int data;
public DoubleNode next;

public DoubleNode(int d){
    this(null, d, null);
}
public DoubleNode(DoubleNode p, int d, DoubleNode n){
    prev = p;
    data = d;
    next = n;
}
}

this is mt entire operator code*

public class operator{
DoubleNode head;
DoubleNode tail;
DoubleNode laman;

String output = "";

public operator(){
    head = tail = null;
}
public boolean isEmpty(){
    return head == null;
}
public void addHead(int i){
    
    if(isEmpty()){
      head = tail =new DoubleNode(i);
    }
    else{
        head = new DoubleNode(null, i, head);
        head.prev = head;
    }
}
public void addTail(int i){
    DoubleNode last = new DoubleNode(i);  
    if(isEmpty()){
        head = tail = new DoubleNode(i);
    }
    else{
      tail.next = last;
      tail = last;
    }
}
public void delHead(){
    DoubleNode temp = head.next; 
    if(head==tail){ //this if condition is testing if the head and tail is one only, 
        head = tail =null;  //if there is only one this will set the tail and head to null
    }
    else{
        head = head.next;
        head = temp;

    }
}

public void delTail(){
        DoubleNode temp;
        if(isEmpty()) {  
            return;  
        }  
        else {  
            if(head != tail) {   
            tail = tail.prev;
            temp = tail;
               
            }
            
            else {  
                head = tail = null;  
            }  
        }  
}
public void display(){
    DoubleNode tmp = head;
    output = "<html>";
    
    for(tmp = head; tmp != null; tmp = tmp.next){
        output = output + "<br>" + tmp.data + "<b>" + "<br>";
        
    }
    output = output + "</html>";
}
}

This is my entire code so far, i have a main class with a jframe but i think its fine because i also use it for single link list. But I do have a problem here at double link list regarding on deleting the last node

tail double linked-list constructor java
2 Answers

Your problem is that you're just assigning to temp but don't actually use it. Additionally you're not setting the link back to the previous element correctly.

Assuming tail.next points to head again you might do the following:

tail.prev.next = tail.next; //you might need to check for `tail.prev` being null 
tail.next.prev = tail.prev; //you might need to check for `tail.next` being null
//delete tail

To illustrate:

A -next-> Tail -next-> Head
^---prev--+  ^---prev--+

Step 1:

+----next--------------V
A         Tail -next-> Head
^---prev--+  ^---prev--+

Step 2:

+----next--------------V
A         Tail -next-> Head
^---prev--+            |
^--------------prev----+

Actually if tail.next == head removing the tail is no different than removing any other node.

user_6378530

You have two errors in your else block:

  • You never change the tail reference. The last statement should really be an assignment to tail.

  • You seem to assume that the tail has a non-null next reference, but that is a contradiction. The tail is supposed to be the last node, so its next reference will always be null (unless you are supposed to create a circular list). By consequence, temp will be null, and the statement temp.next = tail will trigger the Null Pointer Exception.

    The more interesting property of tail is its prev property, which refers to the node that will become the tail after the current tail node has been removed. This tail.prev is explicitly mentioned in your assignment.

So:

   else {
        temp = tail.prev; // <--- should point to the new tail
        tail.prev = null;
        temp.next = tail;
        tail = temp;  // <--- reverse the assignment
   }

Several other issues...

In addHead you do not set the prev property correctly. You make it a self-reference. Realise that head is already referencing the new node. Change:

head.prev = head;

to:

head.next.prev = head;

In addTail the assignment to prev is missing. Change:

tail.next = last;
tail = last;

to:

tail.next = last;
last.prev = tail; // needed!
tail = last;

In delHead you must make sure the new head's prev is null. So change:

head = temp;

to:

head = head.next;
head.prev = null;

NB: you don't need DoubleNode temp = head.next; in that method.

user_54598390
Related