Question

Write a recursive method remove(int target, LLNode list) that removes all occurrences of target from list and returns a reference to the new list. For our example list the statement values = remove(6, values); would result in values referencing the list containing 3 9 12 15 18 19 19 and 20. If target is not contained in list then the list remains unchanged. Please also add a driver class to demonstrate that the method is working correctly.

LLNode.java

//----------------------------------------------------------------------------
// LLNode.java by Dale/Joyce/Weems Chapter 2
//
// Implements <T> nodes for a Linked List.
//----------------------------------------------------------------------------
package support;

public class LLNode<T>
{
protected LLNode<T> link;
protected T info;

public LLNode(T info)
{
this.info = info;
link = null;
}

public void setInfo(T info){ this.info = info;}
public T getInfo(){ return info; }
public void setLink(LLNode<T> link){this.link = link;}
public LLNode<T> getLink(){ return link;}
}

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

package support;

public class Test {

      // recursive method to remove all occurrences of target from list, if exists

      static <T> LLNode<T> remove(T target, LLNode<T> list) {

            // if list is null, returning null (base condition)

            if (list == null) {

                  return null;

            }

            // if current node has target value, ignoring it, and calling recursive

            // method passing target and next node and returning the result

            if (list.getInfo().equals(target)) {

                  return remove(target, list.getLink());

            }

            // creating a Node with this node's value

            LLNode<T> node = new LLNode<T>(list.getInfo());

            // linking the result of recursive remove operation,passing

            // target and next node

            node.setLink(remove(target, list.getLink()));

            // returning resultant node list

            return node;

      }

      // recursive method to print values of a node chain (helper method just for

      // demontration)

      static <T> void print(LLNode<T> list) {

            if (list != null) {

                  System.out.print(list.getInfo());

                  if (list.getLink() != null) {

                        System.out.print(" => ");

                  } else {

                        System.out.println();

                  }

                  print(list.getLink());

            }

      }

      public static void main(String[] args) {

            // creating an array of numbers

            int numbers[] = { 1, 2, 2, 3, 5, 6, 7, 2, 1, 5, 2 };

            // adding first number from array as root value

            LLNode<Integer> nodeList = new LLNode<Integer>(numbers[0]);

            // taking a copy to the head of list

            LLNode<Integer> temp = nodeList;

            // adding each number from the array to the end of node chain

            for (int i = 1; i < numbers.length; i++) {

                  temp.setLink(new LLNode<Integer>(numbers[i]));

                  temp = temp.getLink();

            }

            //displaying node chain

            print(nodeList);

            //removing all occurrences of 2

            System.out.println("removing all occurrences of 2");

            nodeList = remove(2, nodeList);

            //printing node chain

            print(nodeList);

      }

}

/*OUTPUT*/

1 => 2 => 2 => 3 => 5 => 6 => 7 => 2 => 1 => 5 => 2

removing all occurrences of 2

1 => 3 => 5 => 6 => 7 => 1 => 5