Java egyperces – Törlés listából megoldása

Csak akkor olvass tovább, ha a Törlés listából feladatot megoldottad, vagy nem sikerült megoldani.

Az alap feladatot a fenti linken megtalálod, az ott megadott osztályt és a feltöltött listát fogom használni. A feladat tehát az volt, hogy töröljük ki a vizslák adatait a listából. Lássuk akkor a megoldások evolúcióját, mely a hibás megoldásoktól a jobbak felé halad:

1. változat

for( int i = 0; i < kutyak.size(); i++ )
{
  if( kutyak.get(i).getNev().equalsIgnoreCase("vizsla") )
  {
    kutyak.remove(i);
  }
}

Első megoldásként valami ilyesmit szoktak megadni a diákok. A gond az, hogy ez a megoldás nem jó. Miért? Mert ez a kimenete:

Kutya{fajta=tacsko, kor=3, szin=fekete}
Kutya{fajta=vizsla, kor=3, szin=fekete}
Kutya{fajta=labrador, kor=7, szin=zsemle}
Kutya{fajta=labrador, kor=5, szin=arany}
Kutya{fajta=labrador, kor=7, szin=fekete}
Kutya{fajta=labrador, kor=7, szin=barna}
Kutya{fajta=labrador, kor=1, szin=zsemle}
Kutya{fajta=tacsko, kor=2, szin=fekete}

Egy vizsla benne maradt. Valóban csak vizslákat töröltünk ki, de nem mindet. Miért? Az algoritmus, ha az aktuális objektum fajtája vizsla, akkor eltávolítja az adott helyen lévő elemet. Akkor mi a gond? Az, hogy a lista ettől kezdve rövidebb lesz, hiszen a mögötte lévő elemek, eggyel előrelépnek.

Nem, nem az a gond, hogy túlszaladnánk a lista végén, mert a for ciklus futási feltételében folyamatosan követjük a lista méretét, így a végén biztosan nem szaladunk túl. A gond akkor jelentkezik, ha két vagy több törlendő elem egymás után helyezkedik el. Kitörlöd az elsőt, akkor a mögötte lévők előrelépnek, vagyis a mögötte lévő sorszáma is i lesz. De a következő ciklusban az i már eggyel megnő, vagyis a két egymás melletti elemből csak az elsőt törölheted! Egy viszonylag egyszerű trükkel azonban ez kikerülhető:

2. változat

for( int i = 0; i < kutyak.size(); i++ )
{
  if( kutyak.get(i).getNev().equalsIgnoreCase("vizsla") )
  {
    kutyak.remove(i--);
  }
}

Nagyon elegáns megoldás. Amikor eltávolítom a megfelelő elemet, az eltávolítás után az első teendő az, hogy az i-t is visszaléptetem, így utána hiába lép egyet előre a következő ciklusban, az helyesen ismét a megfelelő elemre mutat. Lehet ezt még fokozni? Hogyne 🙂

3. változat

for( int i = kutyak.size()-1; i != -1; i-- )
{
  if( kutyak.get(i).getNev().equalsIgnoreCase("vizsla") )
  {
    kutyak.remove(i);
  }
}

Mit is csináltam? Most nincs ott az i csökkentése. Nincs is rá szükség, mivel a listát hátulról kezdtem feldolgozni! Ha találok egy megfelelő elemet, eltávolítom. A mögötte lévők előrelépnek, de ez engem egyáltalán nem érdekel, mert az eltávolított elem mögött már biztosan nem lehetnek törlölni valók, hiszen onnan érkeztem! Haladok előre, törlöm a megfelelő elemeket, és a lista végét meg húzom magam mögött előre, de az i mindig a megfelelő elemre mutat.

Apróság, mondhatnád, hiszen látszólag csak annyit spóroltunk, hogy törléskor egy i– kimarad. Nem, nem csak ennyit. A for ciklus esetében a futási feltételt minden ciklusban kiértékeli. Vagyis nem csak egy i csökkentést spóroltál meg, hanem azt is, hogy nem kell mindig újra meg újra lekérdezni a lista méretét.

Nem is olyan bonyolult, igaz?

Vélemény, hozzászólás?

Az e-mail címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük

*

Ez az oldal az Akismet szolgáltatást használja a spam csökkentésére. Ismerje meg a hozzászólás adatainak feldolgozását .