CODEWITHSUNDEEP
javaalgorithmrecursionarraylist
gorgi93
gorgi93

Reputation: 2535

Solve Java ArrayList remove with recursion index?

I have a strange problem to which I know the work around but I want to do it with array list this time. Here is the problem: I have a tree of employees. Employee is a simple class (under is list of employees that work for this employee) :

class Employee
{
    String name;
    ArrayList<Employee> under = new ArrayList<Employee>();

    //fire function
}

My task is to recursively fire all the employees which do not have employees under them. I know how to this with work around with custom made list data structure but I want to do it with array list. Here is my code so far:

public boolean Fire()
{
    if (under.isEmpty())
        return true;
    else
    {
        for (int x = 0; x < under.size(); x ++)
        {
             if (under.get(x).Fire())
                 under.remove(x);

        }

    }

    return false;
}

But problem for this code is that when I remove under.remove(x) the under.size() gets smaller and indexes get messed up. I tried to set x = 0, after every under.remove(x) but it did not do exactly right. One employee to much still left. Any solutions with array list structure?

Upvotes: 0

Views: 2537

Answers (3)

user3458
user3458

Reputation:

That's why Iterator has remove() method. Look up Collection's iterator() call and use it in your for loop.

Upvotes: 0

Gilbert Le Blanc
Gilbert Le Blanc

Reputation: 51475

This is a classic problem with removal or deletion.

You have to iterate backwards through the List. That way, when you remove an element, you don't skip other elements or go past the end of the List.

public boolean Fire()
{
    if (under.isEmpty())
        return true;
    else
    {
        for (int x = under.size() - 1; x >= 0; x--)
        {
             if (under.get(x).Fire())
                 under.remove(x);

        }

    }

    return false;
}

Upvotes: 5

Miquel
Miquel

Reputation: 15675

Try using an iterator. You just keep traversing it using .next() on the iterator and whenever you find someone that doesn't have employees under him, you call .remove() (on the iterator) which will remove the last element that the iterator gave you.

Upvotes: 2

Related Questions