Removing a node from a linked list using recursion java

Question

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;
    }

Do you want to create a copy of the list without the element, or change the list inplace? — akuhn
– akuhn, Commented Nov 18, 2012 at 2:23
Can you clarify what List you are using? Is it a java.util.List (docs.oracle.com/javase/7/docs/api/java/util/List.html) or something of your own? Where are the variables value and next coming from? You say you want to return a copy of the list, but in fact you are just returning the same reference this. — jbx
– jbx, Commented Nov 18, 2012 at 2:31
I tried to answer this question but I realized I don't know enough about how your implementation is structured exactly. — durron597
– durron597, Commented Nov 18, 2012 at 2:34
@user1832483 First, I believe you are using your own List structure and not the java.util.List. So can you please post code complete class definition for the List class. — Ankit
– Ankit, Commented Nov 18, 2012 at 2:36

akuhn · Accepted Answer · 2012-11-18 03:31:58Z

2

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());
        }

    }

}

edited Nov 18, 2012 at 3:31

answered Nov 18, 2012 at 2:32

akuhn

27.9k2 gold badges79 silver badges93 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

user1832483 Over a year ago

I tryed implementing your code, maybe im not following right but why exactly are you using next.value, don't you have put .get before value to be able to compare them?

akuhn Over a year ago

In Java, fields are class private, that is an instance can access the private fields of another instance of the same class. (Did the code compile for you?)

user1832483 Over a year ago

no the code wouldn't compile saying it cannot find the symbol variable value which doesn't make sense to me because its declared in the constructor.

user1832483 Over a year ago

So how exactly is the code working? I havent learned the null ? null code yet so that's throwing me off.

akuhn Over a year ago

null works the same way as your EmptyList. Actually using EmptyList is smarter, it is called a nullobject. Google for Nullobject Pattern to learn more.

Sri Harsha Chilakapati · Accepted Answer · 2012-11-18 02:43:00Z

0

Keep two lists.

List nonDuplicates;

List allElements;

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

answered Nov 18, 2012 at 2:43

Sri Harsha Chilakapati

12k6 gold badges54 silver badges91 bronze badges

Collectives™ on Stack Overflow

Removing a node from a linked list using recursion java

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related