0

I am trying to implement a delete and deleteAll method to remove one occurrence or all occurrences of a string from my linked list using recursion, then returns an LLNode object. In my code I am, conceptually, trying to identify if a node (ie node1) is pointing to a node with an occurrence of the specified element (node2), and if so, have node1 instead point to the node that node2 is pointing to.

My code works for the most part, but the problem I am running into is that it seems to skip over the first node in the list. 

public class LinkedTest {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    LLNode<String>list = new LLNode<>("susan");
    list = addNode(list, "matt");
    list = addNode(list, "susan");
    list = addNode(list, "bob");
    list = addNode(list, "matt");

    printNodes(list);

    list = deleteAll(list, "susan");
    System.out.println("\nPrint nodes forward after delete of susan");
    printNodes(list);

    list = deleteAll(list, "matt");
    System.out.println("\nPrint nodes forward after delete of matt");
    printNodes(list);
}

public static LLNode<String> addNode(LLNode<String> list, String info) {
    LLNode<String> newNode = new LLNode<>(info);
    newNode.setLink(list);
    list = newNode;
    return list;
}

public static void printNodes(LLNode<String> node) {
    System.out.println("Print list forward");
    while (node != null) {
        System.out.println(node.getInfo());
        node = node.getLink();
    }
}

public static LLNode<String> delete(LLNode<String> node, String name){
    if(node.getLink().getInfo() != name){
        delete(node.getLink(), name);
    }
    node.setLink(node.getLink().getLink());
    return node;
}

public static LLNode<String> deleteAll(LLNode<String> node, String name){
    if(node.getLink() != null){
        deleteAll(node.getLink(), name);

        if(node.getLink().getInfo() == name){
            node.setLink(node.getLink().getLink());
        }
    }
    return node;
}

}

When this is run, this is the outcome:

Print list forward
matt
bob
susan
matt
susan

Print nodes forward after delete of susan
Print list forward
matt
bob
matt

Print nodes forward after delete of matt
Print list forward
matt
bob

In the output you can see that the first instance of "matt" has not been deleted. The same problem happens when implementing the delete method. Any help is greatly appreciated!

Mac
  • 1
  • 1

1 Answers1

1

Seeing getLink().getLink() an alarm bell should ring; getLink() could be null, and especially the code is too indirect, the case distinction too complex.

String comparison goes by .equals.

Deletion of the first occurrence would go:

public static LLNode<String> delete(LLNode<String> node, String name){
    if (node == null) { // Simplest case.
        return null;
    }
    if (node.getInfo().equals(name)) { // Actual deletion work.
        return node.getLink(); // First occurrence deleted only.
    }
    node.setLink(delete(node.getLink(), name)); // Recursion.
    return node;
}

Your code's intention was missing a return before the recursive delete or so.

Joop Eggen
  • 107,315
  • 7
  • 83
  • 138
  • I was trying to implement something similar to this before, but what was tripping me up was the location of the recursion call. This makes much more sense, thank you! – Mac Oct 09 '17 at 20:08
  • Also, I was able to catch this, but _delete_ takes in both an LLNode argument and a string argument; I added _name_ as the String argument and this worked perfectly. – Mac Oct 09 '17 at 20:13
  • Corrected for other readers. – Joop Eggen Oct 09 '17 at 20:47