CODEWITHSUNDEEP
javalistrecursionlinked-list
user1832483
user1832483

Reputation: 107

Removing a node from a linked list using recursion java

So i have a linked list that I want to be able to remove the first occurrence of a number,

I'm trying to use recursion but sadly all I end up doing is being able to delete the head of the list and

public List remove(int num){
   if(value == num) {
       return next.remove(value);
   }else{
       next = next.remove(value);
       return this;
   }
}

I know i need to return the new list, but how exactly do i either get rid of the node that I'm trying to avoid or is there a way to work around it, so it continues to the next nod.

Edit. Update on the actual code.

class List{
  int value;  //value at this node 
  List next;  //reference to next object in list
  public List(int value, List next){
      this.value = value;
      this.next  = next;
  }
}

I have three different classes, one for the empty list at the end of this, and a class declaring this method, and the actual list.

  public static List makeSample() {
        EmptyList e = new EmptyList();
        List l1 = new List(5, e);
        List l2 = new List(4, l1);
        List l3 = new List(3, l2);
        List l4 = new List(3, l3);
        List l5 = new List(2, l4);
        List l6 = new List(1, l5);
        return l6;
    }

Upvotes: 2

Views: 6618

Answers (2)

akuhn
akuhn

Reputation: 27793

Try this 

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class List {

    private int value;
    private List next;

    public static final List EMPTY = new List(-1, null) {
        public List remove(int n) { return this; };
        public String toString() { return ""; };
    };

    public List(int value, List next) {
        this.value = value;
        this.next = next;
    }

    public List remove(int n) {
        if (value == n) return next;
        return new List(value,next.remove(n));
    }   

    public String toString() {
        return value + "," + next.toString();
    }

    public static class Examples {

        @Test
        public void shouldRemoveElement() {
            List l = new List(1, new List(2, new List(2, new List(3, EMPTY))));
            assertEquals("1,2,2,3,",l.toString());
            assertEquals("2,2,3,",l.remove(1).toString());
            assertEquals("1,2,3,",l.remove(2).toString());
            assertEquals("1,2,2,",l.remove(3).toString());
            assertEquals("1,2,2,3,",l.toString());
        }

    }

}

Upvotes: 2

Sri Harsha Chilakapati
Sri Harsha Chilakapati

Reputation: 11950

Keep two lists.

List nonDuplicates;

List allElements;

for (Node node : allElements){
    if (!nonDuplicates.contains(node)){
        nonDuplicates.add(node);
    }
}

Upvotes: 0

Related Questions