CODEWITHSUNDEEP
javaarraysfor-loop
Vig Killa
Vig Killa

Reputation: 19

Can someone explain how this method works?

The method is about to delete a city for the smallest population!

The method: 

public void delCity(long population) {
    if (population== 0) {
        System.out.println("There is no city!");
        return;
    }

    for (int i = 0; i < index; i++) {
        if (cities[i].getPopulation() < population) {
            for (int j = i; j < index - 1; j++) {
                cities[j] = cities[j + 1];
            }
            cities[--index] = null;
            i--;
        }
    }
}

So the part i don't understand is the body of the second for-loop, for example how cities[j] = cities[j + 1]; works and what does the cities[--index] = null; i--;? I would really appreciate your responses.

Upvotes: 0

Views: 185

Answers (4)

granmirupa
granmirupa

Reputation: 2790

This loop is shifting all the values of the array [from the position i, that is the city to delete]. (Because the array is static, otherwise there is null between elements )

for (int j = i; j < index - 1; j++) {
    cities[j] = cities[j + 1];
}

Then is setting last element to null and decreasing index;

 cities[--index] = null;

Here an explaination of the shifting: enter image description here enter image description here

As mentioned into comments. Your complexity is O(N²). But just changing your data structure (for example, using Lists), you can improve it to O(N).

Upvotes: 5

Margaret Bloom
Margaret Bloom

Reputation: 44146

I commented the code as any more elaborate explanation would be superfluous in such simple context.

//Scan all the cities, from i = 0 to i = index -1
for (int i = 0; i < index; i++) 
{
    //Check it cities[i] has LESS population than specified
    if (cities[i].getPopulation() < population) 
    {
         //We need to remove cities[i]
         //We shift all the subsequent cities 
         //(cities[i+1], cities[i+2], ... cities[index-1] one position LEFT,
         //thereby overwriting cities[i] and so deleting it

         //Shift all the subsequent cities left
         //We start this for FROM i, so the first iteration is
         //cities[i] = cities[i + 1];
         //The second is
         //cities[i + 1] = cities[i + 2];
         //and so on. We STOP AT index - 2 (note the strict less than)
         //So that j + 1 is AT MOST index - 1
         for (int j = i; j < index - 1; j++) 
         {
                cities[j] = cities[j + 1];
         }

         //Since j was at most index - 2, the cities[index - 1] was not
         //overwritten with the next one. Naturally as there is no next one
         //for it.
         //This last city is now duplicated (the copy is at index - 2) and
         //Must be overwritten with null.
         //Also index, which keep track of the number of cities must be
         //decremented (here the pre-decrement -- is used)
         cities[--index] = null;

         //cities[i] was the deleted city. But now it contains cities[i + 1]
         //Which is a totally different city!
         //If we continue the for now, we will go to the NEXT city, as i 
         //will be incremented, to keep i the same one more iteration, we
         //decrement it. This way we process (the new) cities[i] one more time.
         i--;
    }
}

Use the old pencil and rubber until you fully understand the algorithm, really, there is no better way.

Upvotes: 1

Adnan Isajbegovic
Adnan Isajbegovic

Reputation: 2307

index is the size of array cities. So, when you come to specific position where cities[i].getPopulation() < population is true, you will move all cities from position i + 1 to the end of array index - 1 to positions i to index - 2, and you do that with:

for (int j = i; j < index - 1; j++) {
                cities[j] = cities[j + 1];
            }

So, city with small population on position i, now j, will be deleted by overriding it with citiescities[j + 1], and the citiescities[j + 1] will be overrided with citiescities[j + 2], etc until the end of array. So, on position citiescities[index - 2] will be same as citiescities[index - 1], so we need to delete it to, so you place cities[--index] = null;, where index will be first decremented (thats why -- will be left from index), and cities[oldIndex - 1] will be null. This will also help with for loop not to go until first index value location in array, but until the last city in the array, that is present.

Now, since your index i will be incremented in next for loop step, but you moved next city on position i, you must decrement i to check that city, thats why i at the end.

Note, that with this you will still have a full long array as before, so filled with some nulls if there are cities with less population than stated. Maybe better approach will be to copy it to new array with size index, that you got at the end of for (note: something similar what ArrayList does when you remove item from it).

Upvotes: 0

Bilesh Ganguly
Bilesh Ganguly

Reputation: 4141

cities[j] = cities[j + 1];

The above statement sets the city at index j to the city at index j + 1.

cities[--index] = null;

This statement just sets the last index of cities to null.

As such, there is no removal of an element. The element to be removed just gets overwritten with the next element. And the loop does this for all elements following the one to be deleted. At the end, we are left with the last element which is set to null.

Leaving the explanation aside, the code is quite inefficient.

Upvotes: 2

Related Questions