Singly linked list delete() method

Question

I would like a quick review on my method to delete a node from a singly linked list. I'm fairly certain that this is not near optimally done, and would love to get feedback.

It uses a SinglyLinkedNode element as the node:

public class SinglyLinkedNode {
    private SinglyLinkedNode next = null;
    int data;
    public SinglyLinkedNode(int data){
        this.data=data;
    }
    public int getData(){
        return this.data;
    }
    public void setNext(SinglyLinkedNode next){
        this.next = next;
    }
    public SinglyLinkedNode getNext(){
        return this.next;
    }
}

The element definitions and the delete function are as so:

import data_structures.LinkedLists.SinglyLinkedNode;

public class SinglyLinkedList{
    private SinglyLinkedNode head = null;
    private SinglyLinkedNode tail = null;
    private int length = 0;
    public SinglyLinkedList(int data){
        this.head = new SinglyLinkedNode(data);
        this.tail = this.head;
        this.length = 1;
    }

    public void delete(int data){
        SinglyLinkedNode n = this.head;
        if (n==null){
            return;
        }
        if (n.getData()==data){//If the head is the data we want
            if (n.getNext()==null){//If it's the only node, null the head and tail
                this.tail = null;
                this.head = null;
                this.length = 0;
            }
            else {//Or move the head to the next node
                this.head = n.getNext();
                this.length--;
            }
            return;
        }
        while (n.getNext()!=null && n.getNext().getData()!=data){//Get the data node or the last node at n.next
            n=n.getNext();
        }
        if (n.getNext() == null){//If n is the last element in the list
            if (n.getData()!=data){//If data wasn't in array then we're done
                return;
            }
            //If we're deleting the only remaining element
            if (this.length <=1){
                this.tail = null;
                this.head = null;
                this.length=0;
            }
            else {//If we're just moving the tail
                n.setNext(null);
                this.tail = n;
                this.length--;
            }
        }
        else {//If n is not the last element
            if (n.getNext().getNext()==null){//If n.next is the last element
                n.setNext(null);
                this.tail = n;
                this.length--;
            }
            else {//If n.next is not the last element
                n.setNext(n.getNext().getNext());
                this.length--;
            }
        }
    }
}

As you can see, this is quite a lot of lines of code - 46 to be exact. In particular, the section below the while loop seems redundant - but I can't figure out how to replace any of it.

Answer 1

That's a very lengthly piece of code. To delete a Node, it's not about doing something confusing; it's about changing links around. Imaging this list:

1, 2, 3, 4, 5

In this case, 1 links to 2, which links to 3, and so on. So what if you want to remove 3, for example? Well, change the links so that 2 links to 4!

How? Well...

1. Rewrite the method so that it returns a boolean depending on if the delete was a success:

   public boolean delete(int data) {
   

2. Handle special case head and empty list:

       SinglyLinkedNode nodeBeforeDelete = this.head;
       if (nodeBeforeDelete == null) { // List in empty
           return false;
       } else if (nodeBeforeDelete.getData() == data) {
           this.head = this.head.getNext();
           return true;
       }
   

3. Loop until you find the data:

       while (true) {
           SinglyLinkedNode next = nodeBeforeDelete.getNext()
           if (next == null) { // No data found in list
               return false;
           } else if (next.getData() == data) {
               break;
           }
           nodeBeforeDelete = next;
       }
   

4. Relink the nodes:

       SinglyLinkedNode next = nodeBeforeDelete.getNext();
       nodeBeforeDelete.setNext(next.getNext());
       next.setNext(null);
   

5. End the method:

       return true;
   }
   

Result:

    public boolean delete(int data) {
        SinglyLinkedNode nodeBeforeDelete = this.head;
        if (nodeBeforeDelete == null) { // List in empty
            return false;
        } else if (nodeBeforeDelete.getData() == data) {
            this.head = this.head.getNext();
            return true;
        }
        while (true) {
            SinglyLinkedNode next = nodeBeforeDelete.getNext()
            if (next == null) { // No data found in list
                return false;
            } else if (next.getData() == data) {
                break;
            }
            nodeBeforeDelete = next;
        }
        SinglyLinkedNode next = nodeBeforeDelete.getNext();
        nodeBeforeDelete.setNext(next.getNext());
        next.setNext(null);
        return true;
    }