Need help on Linked list delete method

Question

Right now my Linked list is in a queue form. My LList class holds two fields called head and tail which are the head and tail of the list. Head and tail are LNode objects, a LNode is an element of the list that holds a int value, and it's previous LNode and next LNode.

Here's my LNode class:

class LNode{
    private int val;
    private LNode next;//not recursive
    private LNode prev;
    public LNode(int v, LNode n, LNode p){
        next = n;
        prev = p;
        val = v;
    }
    public int getVal(){
        return val;
    }
    public LNode getNext(){
        return next;
    }
    public LNode getPrev(){
        return prev;
    }
    public void setVal(int v){
        val = v;
    }
    public void setNext(LNode n){
        next = n;
    }
    public void setPrev(LNode p){
        prev = p;
    }
}

I am trying to make a delete method in my LList class so that it takes a value and delete the LNode that has that value. My problem is, I don't know how I would deal with the case where the LNode I'm trying to delete is the head or the tail.

public void delete(int v){

    if(head.getVal()==v){//delete head
        head = head.getNext();
        head.setPrev(null);
    }
    else if(tail.getVal()==v){//delete tail
        System.out.println("boiboi");
        tail = tail.getPrev();
        tail.setNext(null);
    }
    else{//delete other element
        LNode tmp = head;
        while(tmp.getVal()!=v){
            tmp = tmp.getNext();
        }
        tmp.getPrev().setNext(tmp.getNext());
        tmp.getNext().setPrev(tmp.getPrev());
    }
}

What i have tried is to set the new head's previous LNode to be null, but Java doesn't allow that. So what should I do?

Thank you.

Can it be a circular list? In that case you can head.setPrev(tail). — icanc
– icanc, Commented Mar 6, 2013 at 4:46
@cookcook maybe you need to null check head.getNext() in case your list has only 1 node. — dlock
– dlock, Commented Mar 6, 2013 at 4:49

Jon Skeet · Accepted Answer · 2013-03-06 05:06:10Z

3

Your code looks okay to me, except in the case that the value you're removing is the sole value - in which case you want to end up with both the head and the tail as null. I suspect all you need to do is change the head case:

if (head.getVal() == v) {
    head = head.getNext();
    if (head != null) {
        head.setPrev(null);
    } else {
        // If head.getNext() returns null, then tail must have been equal to head.
        tail = null;
    }
}

You should also check for the empty list situation first:

if (head == null) {
    return;
}

And in your general case, handle the situation where the value isn't found:

while (tmp != null && tmp.getVal() != v) {
    tmp = tmp.getNext();
}
if (tmp == null) {
    return;
}

answered Mar 6, 2013 at 5:06

Jon Skeet

1.5m893 gold badges9.3k silver badges9.3k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

cook cook Over a year ago

Yeah you are right, I have no problem with my code, I just had an error in my Testing class, that's what made a NullPointerException.

Jon Skeet Over a year ago

@cookcook: In what way do you "have no problem" with your code? Everything I've pointed out is a bug in your code - not with your test. Calling delete on an empty list should not throw NullPointerException, and nor should calling delete with a value which isn't in the list.

cook cook Over a year ago

I do realize my problem with only one element in the list. I'm just saying i didn't know that was the reason and my original code works fine with normal cases of deleting the head and tail element. Thank you for your help and I have already changed my code to work for all the cases you mentioned.

Collectives™ on Stack Overflow

Need help on Linked list delete method

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related