4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! Good job on your first question. \$\endgroup\$ – SirPython Dec 1 '15 at 0:26
4
\$\begingroup\$

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;
    }
\$\endgroup\$
  • \$\begingroup\$ Don't forget to unlink the 'next' from the deleted node too.... it helps with Grabage collection, and prevents people from entering the remainder of the linked list from deleted locations. \$\endgroup\$ – rolfl Dec 1 '15 at 0:59
  • \$\begingroup\$ Doesn't this have a problem if data is the second last node? It seems like it would assign the null from "next.getNext()" to be the next element after nodeBeforeDelete, correct? Also, is it pointless to keep track of the tail element in a singly linked list, then? Only useful for doubly linked? \$\endgroup\$ – WarSame Dec 1 '15 at 3:45
  • \$\begingroup\$ Thanks for your answer! It turns out your while loop handles the case I was talking about properly. \$\endgroup\$ – WarSame Dec 1 '15 at 15:23
  • \$\begingroup\$ @WarSame yes, it is actually supposed to set it to null, as it is the last element, right? \$\endgroup\$ – TheCoffeeCup Dec 1 '15 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.