Solve Java ArrayList remove with recursion index?

Question

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?

Gilbert Le Blanc · Accepted Answer · 2013-05-03 17:01:11Z

5

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

answered May 3, 2013 at 17:01

Gilbert Le Blanc

51.7k6 gold badges73 silver badges120 bronze badges

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

1 Comment

Gilbert Le Blanc Over a year ago

I tend to remember problems that bite me in the rear. :-)

Miquel · Accepted Answer · 2013-05-03 17:00:40Z

2

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.

answered May 3, 2013 at 17:00

Miquel

15.7k8 gold badges56 silver badges88 bronze badges

Comments

user3458 · Accepted Answer · 2013-05-03 17:01:50Z

0

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

answered May 3, 2013 at 17:01

user3458

Collectives™ on Stack Overflow

Solve Java ArrayList remove with recursion index?

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related