Vijay Bhore Vijay Bhore - 2 months ago 12
Java Question

Delete k-th element in a linked list (Java implementation)

I am trying this program but i am not able to achieve deletion. The execution is going into infinite loop. Also, i am not sure if i am forming linked list properly.

What am i missing in the following program:

public class SpecificNodeRemoval {
private static class Node {
String item;
Node next;
Node prev;

private Node(String item, Node next, Node prev) {
this.item = item;
this.next = next;
this.prev = prev;
}
}

public static void main(String[] args) {
int k = 3;

Node fourth = new Node("Fourth", null, null);
Node third = new Node("Third", fourth, null);
Node second = new Node("Second", third, null);
Node first = new Node("First", second, null);

second.prev = first;
third.prev = second;
fourth.prev = third;
Node list = first;

Node result = removalKthNode(list, k);

int j = 1;
while(result.next!=null){
System.out.println(j+": "+result.item);
}
}

private static Node removalKthNode(Node first, int k) {
Node temp = first;

for(int i=1; i < k; i++) {
temp = temp.next;
}

temp.prev.next = temp.next;
temp.next.prev = temp.prev;

return temp;
}
}





THANKS A TON for answer and comments.. the working program is listed below:

public class SpecificNodeRemoval {
private static class Node {
String item;
Node next;
Node prev;

private Node(String item, Node next, Node prev) {
this.item = item;
this.next = next;
this.prev = prev;
}
}

public static void main(String[] args) {
int k = 3;

Node fourth = new Node("Fourth", null, null);
Node third = new Node("Third", fourth, null);
Node second = new Node("Second", third, null);
Node first = new Node("First", second, null);

second.prev = first;
third.prev = second;
fourth.prev = third;
Node list = first;

Node result = removalKthNode(list, k);

int j = 1;
while(result != null){
System.out.println(j+": "+result.item);
result = result.next;
j++;
}
}

private static Node removalKthNode(Node first, int k) {
Node temp = first;

for(int i=1; i < k; i++) {
temp = temp.next;
}

temp.prev.next = temp.next;
temp.next.prev = temp.prev;

return first;
}
}


The output is:
1: First
2: Second
3: Fourth

Answer

This looks like the culprit.

while(result.next!=null){
    System.out.println(j+": "+result.item);
}

you are not progressing forward in the linked list.

I'm not exactly sure what you intended, but you may want to write as follows to avoid infinite loop...

while(result !=null){
    System.out.println(j+": "+result.item);
    result = result.next;
    j++;
}

But again if you want to print whole linked list, you should not initialise result with the value returned from removalKthNode function. You should start from first.

Hope this makes sense.