How to recursively removing an item from linkedList?

Question

Implementing LinkedList in a recursive approach was a bit challenging to me, which I get stuck in implementing of its remove method and wonder how to keep reference to previous item in recursive?

MyLinkedList class

package linkedlist;

public class MyLinkedList {
private Integer value;
private MyLinkedList next;

public MyLinkedList() {
}

public MyLinkedList(Integer value) {
    this.value = value;
}

public void add(Integer value) {
    if (this.value == null) {
        this.value = value;
    } else if (this.next == null) {
        this.next = new MyLinkedList(value);
    } else {
        this.next.add(value);
    }
}

public MyLinkedList remove(Integer index) {
//
//        if (index < 0) {
//            return this;
//        }
//        if (index == 0) {
//            return this.next;
//        }
//        this.next = remove(index - 1);
    return this;
}

public Integer indexOf(Integer value) {
    if (this.value.equals(value)) {
        return 0;
    } else if (this.next == null) {
        return null;
    } else {
        return 1 + this.next.indexOf(value);
    }
}
}

MyLinkedListTester class

package linkedlist;

public class MyLinkedListTester {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.add(1);
        myLinkedList.add(2);
        myLinkedList.add(3);
        myLinkedList.add(4);

        System.out.println("Index Of Array: " + myLinkedList.indexOf(3));
        MyLinkedList linkedList = myLinkedList.remove(3);
    }
}

Answer 1

As mentioned in the comments the iterative approach is easier and more efficient most of the time. Anyway I think you do this as an exercise because in Java you already have a LinkedList.

So first you have a kind of error in your thinking (as far as I'm aware of it). It's also a kind of bad design choice. You create your MyLinkedList and save the data right into it and the next is also of the class MyLinkedList but it's not a list, it's a Node. There should only be one List, and 0 - many nodes.

For example I can't figure out how to do a remove function that will return the removed Node (in your case MyLinkedList) and as well let you keep the list in case you remove the first element in your list.

If you are looking in the implementation that's why they use Nodes and it's also more logical (a list doesn't contain "List elements") and so on...

Some other remark: your indexOf funtion will return an error if you try to get a element that does not exist (1 + null => error).

So anyway. What you have to do is to create a Node. (btw if you really want a real LinkedList you can use generic instead of int/Integer).

Below I post my solution how to do it (may be better out there but that is how I would do it). I also wrote a toString method to see how the List looks like (and it works as far as I can say). In case you want to still use your code without the Node it should give you an idea how to solve your problem with remove. You can also put some of the logic into the Node class but for me Node is only a container and doesn't really contain any logic.

public class MyLinkedList {
    private Node head;

    public MyLinkedList() {
    }

    public class Node{
        private int value;
        private Node next = null;

        public Node(int value){
            this.value = value;
        }

        public int getValue(){
            return value;
        }

        public Node getNext(){
            return next;
        }

        public void setNext(Node next){
            this.next = next;
        }

    }

    public void add(int value) {
        Node next = new Node(value);
        if(head == null){
            head = next;
        } else {
            addRecursive(head,next);
        }
    }

    private void addRecursive(Node node, Node next) {
        if(node.next == null){
            node.setNext(next);
        } else {
            addRecursive(node.getNext(),next);
        }
    }

    public Node remove(int index){
        Node removeNode = head;
        if(index == 0){
            head = head.getNext();
        } else {
            removeNode = removeRecursive(head,index-1);
        }
        return removeNode;
    }

    private Node removeRecursive(Node node, int index){
        Node removeNode = node.getNext();
        if(index == 0){
            node.setNext(removeNode.getNext());
        } else {
            removeNode = removeRecursive(node.getNext(),index-1);
        }
        return removeNode;
    }

    public int indexOf(int value) {
        if (head == null){
            return -1;
        }  else if (head.getValue() == value){
            return 0;
        } else {
            return indexOfRecursive(head,value,0);
        }
    }

    private int indexOfRecursive(Node node, int value, int index) {
        if(node.getNext() == null){
            return -1;
        } else if(node.getNext().getValue() == value){
            return index + 1;
        } else {
            return indexOfRecursive(node.getNext(),value,index+1);
        }
    }

    @Override
    public String toString(){
        if(head == null){
            return "";
        } else {
            return toStringRecursive(head,"["+head.getValue());
        }
    }

    private String toStringRecursive(Node node, String output){
        if(node.getNext() == null){
            return output + "]";
        } else {
            return toStringRecursive(node.getNext(),output + ", " + node.getNext().getValue());
        }
    }
}