CODEWITHSUNDEEP
javalinked-list
Scarl
Scarl

Reputation: 950

deleting a specific item from a java LL

So I'm trying to delete an item from a linked list in java.I'm not using java's predefined LL but I'm working with my own.

I know the concept to delete an item is to traverse in the link and compare the data in the list one by one.

so here's what I came up with, but it doesn't work!

public void delStudent(int regN) {
    Node current = head;
    Node q = head;

    if (current.getStudent().getRegN() == regN) {
        head = head.link;
    }
        for (int i = 0; i < this.length() - 1; i++) {
            if (current.getStudent().getRegN() != regN) {
                current = current.link;
                q = current;
            }
        }
        q.link= current.link.link;

    }

Upvotes: 0

Views: 134

Answers (3)

slider
slider

Reputation: 12990

Well, if your list is empty, the execution of the if statement in the beginning will immediately give a NullPointerException (because current will be null). Generally, for the LinkedList delete method, you must consider three cases: size == 0, size == 1, and size > 1 (where size is the number of nodes in the Linked List).

public void delStudent(int regN) {
    Node current = head;
    Node previous = head;       
    while (current != null ){ // keep traversing till end of list
        if (current.getStudent().getRegN() == regN) { // found it!
            previous.link = current.link; // relink
            if (current == head){ // edge case : removed first element
                head = current.link; // move head forward.
            }
            break;
        } else {
            previous = current;
            current = current.link;
        }   
    }
}

The above code assumes regN is unique and that there is only one student with that regN. Hope this helps.

Upvotes: 1

Daniel Jacobson
Daniel Jacobson

Reputation: 121

When you are checking each node you need to delete the node or break once you find a match. You need to maintain a node for the previous node to be able to delete the current node once you find a match.

I just realized that you were attempting to to that with Node q

for (int i = 0; i < this.length() - 1; i++) {
    if (current.getStudent().getRegN() != regN) {
        q = current;
        current = current.link;           
    } else{ //we have a match
        //remove the link to the current item
        q.link = current.link; 
        break; 
    }

if you are using a doubly linked list you can use node.prev().link = current.link;

Upvotes: 0

subsub
subsub

Reputation: 1857

The mistake is (I think) in these three lines:

current = current.link;
q = current;

(where you set q to be the same as current) and

q.link= current.link.link;

(and maybe also in using length() depending on it's implementation)

To see why let's look at how to delete in more detail: Let's consider there are three nodes in your list x->y->z and you want to delete y. In order to do so you need to set x.link = z.

To return to you example it means that the variable q should store the element before current, then deleting current can be done by 

q.link = current.link;

In order order to have q be the predecessor of current you have to reverse the two lines above, i.e., use 

q = current;
current = current.link;

Why am I saying depending on the implementation of length ? If you implementation of length just returns some number maintained by increasing whenever you add a value to the list, you should also decrement it when deleting one. If length traverses the list in order to find the number of elements then its ok, although not very efficient.

One last comment: your code will not work (even with the fixes I explain above) when there is no element with the given regN. Why? Because you always delete one element. Moreover, you might want to rethink the logic inside the loop. Currently if the element to delete is the second one and there is 1000000 elements you will run the loop nearly 1000000 times.

Upvotes: 0

Related Questions