2

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.

4

1 回答 1

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;
}
于 2013-03-06T05:06:10.427 回答