HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Singly linked list delete() method

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
deletemethodsinglylistlinked

Problem

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)

Solution

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...

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

public boolean delete(int data) {


-
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;
    }


-
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;
    }


-
Relink the nodes:

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


-
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;
    }

Code Snippets

1, 2, 3, 4, 5
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);

Context

StackExchange Code Review Q#112396, answer score: 4

Revisions (0)

No revisions yet.