Linked List - How to make a recursive Adding method that add and " sort "?

Question

Hello i'm creating my own my linked list without implementing java.util.linkedlist

I want to create a recursive adding method that :

should add a Pokemon whose level is between a pokemon who is lower level and higher level Something like this :

Bulbasaur(5) -> Squirtle(15) -> Charmander(20)

then add(Pigeon) whose level is 6 so :

Bulbasaur(5) -> Pigeon(6) -> Squirtle(15) -> Charmander(20)

Adding pigeon is the part where I'm struggling

So far, i've managed to sort them because I've been adding them from the smallest to the biggest :

d1.addPokemon(p1); // level 5

d1.addPokemon(p2); // level 15

d1.addPokemon(p3); //level 20

d1.addPokemon(p4); // level 6 - Not adding, there is something wrong with my method I don't know what to change

Thank you

        public class Trainer{

            public final String name;
            private Pokeball head;

            public Trainer(String name) {
                this.name = name;
            }

            public void display() {
                System.out.print(this.name + " : ");
                this.head.display();
            }

            public void addPokemon(Pokemon pok) {
                if (this.head != null) {
                    this.head.addPokemon(this.head, pok);
                } else {
                    this.head = new Pokeball(pok);
                }
            }

        }

        public class Pokeball {

            private Pokemon pok;
            private Pokeball next;

            public Pokeball(Pokemon pok) {
                this.pok = pok;
            }

  public Pokeball addPokemon(Pokeball current, Pokemon pok) {

        if (current == null) {
            return null;
        }
        if (current.pok.getLevel() > pok.getLevel()) {
            Pokeball newPokeball = new Pokeball(pok);
            newPokeball.next = current;
            return newPokeball;
        }
        // if next is null add it to next
        if (current.next == null) {
            current.next = new Pokeball(pok);
        }
        // if next is not null and value is between two sequences add it between
        else if (pok.getLevel() > current.pok.getLevel() && pok.getLevel() <= current.next.pok.getLevel()) {
            Pokeball newPokeball = new Pokeball(pok);
            newPokeball.next = current.next;
            current.next = newPokeball;
        }
        // If value is not between call recursion again
        else {
            addPokemon(current.next, pok);

        }
        return current;
    }
        public class Pokemon {

            private String name;
            private int level;

            public Pokemon(String name, int level) {
                this.name = name;
                this.level = level;

            }

            public void display() {
                System.out.println();
                System.out.print(this.name + " : " + this.level);

            }

            public String getName() {
                return name;
            }

            public void setName(String name) {
                this.name = name;
            }

            public int getLevel() {
                return level;
            }

            public void setLevel(int level) {
                this.level = level;
            }

        }

        public class test {
            public static void main(String[] args) {

                Pokemon p1 = new Pokemon("Bulbasaur", 5);
                Pokemon p2 = new Pokemon("Squirtle", 15);
                Pokemon p3 = new Pokemon("Charmander", 20);
                Pokemon p4 = new Pokemon("Pigeon", 6);

                Trainer t1 = new Trainer("Pierre");
                t1.addPokemon(p1);
                t1.addPokemon(p2);
                t1.addPokemon(p3);
                t1.addPokemon(p4);

                t1.display();

        // prints :
        Pierre : 
        Bulbasaur : 5 
        Squirtle : 15 
        Charmander : 20 
    // But pigeon is not here ! :(

            }

        }

Ah yes sorry, I've edited now my variables were in french, I forgot to change this one — Blebhebhe
– Blebhebhe, Commented Feb 24, 2018 at 12:39
Is there any obligation about implementing the add method in a recursive form? Since always you have a sorted list and when you want to find the correct position to add the new Pokemon you can do it without recursion and very clear. — STaefi
– STaefi, Commented Feb 24, 2018 at 12:43
I updated the answer, but in the case new Pokeball is the smallest level, it is added in Trainer class addpokemon method — miskender
– miskender, Commented Feb 24, 2018 at 13:32
@Blebhebhe actually it doesn't correspond to SO rules since you asked for recursive method so my answer is wrong. — Russiancold
– Russiancold, Commented Feb 24, 2018 at 20:51

miskender · Accepted Answer · 2018-02-24 13:30:41Z

1

Change addPokemon method in Pokeball class like this.

 public void addPokemon(Pokeball current, Pokemon pok) {
     // if next is null add it to next
     if (current.next == null){
         current.next = new Pokeball(pok); 
     }
    // if next is not null and value is between two sequences add it between
    else if( pok.getLevel() > current.pok.getLevel() && pok.getLevel()<= 
    current.next.pok.getLevel()) {
       Pokeball newPokeball =  new Pokeball(pok);  
       newPokeball.next = current.next;
       current.next = newPokeball;
    } 
  // If value is not between call recursion again
   else {
      addPokemon(current.next, pok);
   }

}

At Trainer class change addPokemon method;

 public void addPokemon(Pokemon pok) {
        if (this.head != null) {
            if(pok.getLevel()<this.head.pok.getLevel()){
                Pokeball newPokeball = new Pokeball(pok);
                newPokeball.next = this.head;
                this.head = newPokeball;
                return;
            }
            this.head.addPokemon(this.head, pok);
        } else {
            this.head = new Pokeball(pok);
        }
    }

edited Feb 24, 2018 at 13:30

answered Feb 24, 2018 at 12:40

miskender

7,9982 gold badges24 silver badges25 bronze badges

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

8 Comments

user9190555 Over a year ago

Why don't you explain why to do so?

Turo Over a year ago

I think the case of pok beeing the first isn't covered, but i think its a flaw in the design, since you have no acces to head of trainer

miskender Over a year ago

@Turo I think It is covered in Trainer class addPokemon method. I wrote the answer directly here, did not test if its working.

Blebhebhe Over a year ago

Thank you It works great ! But as Turo said, what if Pigeon were level 4 ? I've tried to solve this problem first but gave up, I'm not sure how I modify the value head of Trainer from Pokeball

Turo Over a year ago

It's not covered in Trainer class, so it must be added there or give a pokomon/pokoball access to its trainer

|

Russiancold · Accepted Answer · 2020-05-08 18:23:03Z

Ok, let's simply iterate through the list and every time check if the next node is more than a new one. The most straight way is:

public void addPokemon(Pokemon pokemon) {
    if (head == null) {
        head = new Pokeball(pokemon, null);
        return; 
    }
    Pokeball current = head;
    while(current.getPokemon().getLevel() < pokemon.getLevel()) { 
        if(current.getNext() == null) {
            current.getNext() == new Pokeball(pokemon, null);
            return;
        } else {
            if (current.getNext().getPokemon().getLevel() > pokemon.getLevel()) {
                current.setNext(new Pokeball(pokemon, current.getNext()))
                return;
        }
    }
    return;

Don't forget to add needed getters and setters. Read here why it's good practise. Also there are many other ways to implement this, don't forget that you can implement Iterator and Comparable and then use some java tools like sort() or compareTo(), but these ways are more sophisticated and are not needed here.

Collectives™ on Stack Overflow

Linked List - How to make a recursive Adding method that add and " sort "?

2 Answers 2

8 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related