Távolítsa el egy adott érték minden előfordulását a listáról

1. Bemutatkozás

A Java-ban egyszerű egy adott érték eltávolítása az a-ból Lista felhasználásával List.remove (). Azonban, hatékonyan eltávolítja az érték minden előfordulását sokkal nehezebb.

Ebben az oktatóanyagban több megoldást fogunk látni erre a problémára, ismertetve az előnyöket és hátrányokat.

Az olvashatóság érdekében szokást használunk lista (int…) módszer a tesztekben, amely egy Tömb lista mely elemeket elhaladtuk.

2. Használja a míg Hurok

Mivel tudjuk, hogyan kell távolítson el egyetlen elemet, ciklusban ismételten elvégezve elég egyszerűnek tűnik:

void removeAll (List list, int element) {while (list.contains (element)) {list.remove (element); }}

Ez azonban nem a várt módon működik:

// megadott Lista lista = lista (1, 2, 3); int értékToRemove = 1; // when assertThatThrownBy (() -> removeAll (list, valueToRemove)) .isInstanceOf (IndexOutOfBoundsException.class);

A probléma a 3. sorban van: hívunk List.remove (int), amely az argumentumát indexként kezeli, nem pedig az eltávolítani kívánt értéket.

A fenti tesztben mindig hívunk list.remove (1), de az elem indexe, amelyet el akarunk távolítani, az 0. Hívás List.remove () az eltávolított elem után az összes elemet kisebb indexekre tolja.

Ebben a forgatókönyvben azt jelenti, hogy az első kivételével minden elemet törölünk.

Ha csak az első marad, az index 1 törvényellenes lesz. Ezért kapunk egy Kivétel.

Ne feledje, hogy csak akkor nézünk szembe ezzel a problémával, ha hívunk List.remove () egy primitívvel byte, rövid, char vagy int argumentum, mivel az első dolog, amit a fordító tesz, amikor megpróbálja megtalálni a megfelelő túlterhelt metódust, szélesedik.

Korrigálhatjuk, ha az értéket átadjuk Egész szám:

void removeAll (Lista lista, Egész elem) {while (list.contains (element)) {list.remove (element); }}

Most a kód a várt módon működik:

// megadott Lista lista = lista (1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));

Mivel List.contains () és List.remove () mindkettőnek meg kell találnia az elem első előfordulását, ez a kód felesleges elemjárást okoz.

Jobban tehetünk, ha tároljuk az első előfordulás indexét:

void removeAll (Lista lista, Egész elem) {int index; while ((index = list.indexOf (elem))> = 0) {list.remove (index); }}

Ellenőrizhetjük, hogy működik-e:

// megadott Lista lista = lista (1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));

Míg ezek a megoldások rövid és tiszta kódot hoznak létre, még mindig gyenge a teljesítményük: mert nem követjük nyomon a haladást, List.remove () meg kell találnia a megadott érték első előfordulását annak törléséhez.

Továbbá, amikor egy Tömb lista, az elemeltolás sok referencia másolást okozhat, akár többször is átcsoportosíthatja a háttér tömböt.

3. Eltávolítás, amíg a Lista Változtatások

List.remove (E elem) van egy olyan jellemzője, amelyet még nem említettünk: ez visszatér a logikai érték, ami igaz ha a Lista a művelet miatt megváltozott, ezért tartalmazta az elemet.

Vegye figyelembe, hogy List.remove (int index) érvénytelen, mert ha a megadott index érvényes, akkor a Lista mindig eltávolítja. Ellenkező esetben dob IndexOutOfBoundsException.

Ezzel eltávolításokat hajthatunk végre a Lista változtatások:

void removeAll (List list, int elem) {while (list.remove (element)); }

A várakozásoknak megfelelően működik:

// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));

Annak ellenére, hogy rövid, ennek a megvalósításnak ugyanazok a problémái vannak, mint az előző szakaszban.

3. Használja a mert Hurok

Nyomon követhetjük fejlődésünket, ha végigjárjuk az elemeket a-val mert hurok, és távolítsa el az aktuálisat, ha megfelel:

void removeAll (List list, int element) {for (int i = 0; i <list.size (); i ++) {if (Objects.equals (element, list.get (i))) {list.remove (i ); }}}

A várakozásoknak megfelelően működik:

// megadott Lista lista = lista (1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));

Ha azonban más bemenettel próbáljuk ki, akkor helytelen kimenetet ad:

// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (1, 2, 3));

Vizsgáljuk meg lépésről lépésre a kód működését:

  • i = 0
    • elem és list.get (i) mindkettő egyenlő 1 a 3. sorban, így a Java belép a ha nyilatkozat,
    • eltávolítjuk az elemet az indexnél 0,
    • így lista most tartalmazza 1, 2 és 3
  • i = 1
    • list.get (i) visszatér 2 mivel amikor eltávolítunk egy elemet a Lista, az összes folyamatot kisebb indexekre tereli

Tehát akkor szembesülünk ezzel a problémával két szomszédos értékünk van, amelyeket el akarunk távolítani. Ennek megoldásához fenn kell tartanunk a ciklusváltozót.

Csökkentése az elem eltávolításakor:

void removeAll (List list, int element) {for (int i = 0; i <list.size (); i ++) {if (Objects.equals (element, list.get (i))) {list.remove (i ); én--; }}}

Csak akkor növeli, ha nem távolítjuk el az elemet:

void removeAll (List list, int element) {for (int i = 0; i <list.size ();) {if (Objects.equals (element, list.get (i))) {list.remove (i) ; } else {i ++; }}}

Ne feledje, hogy az utóbbiban eltávolítottuk az állítást i ++ a 2. vonalon.

Mindkét megoldás a várakozásoknak megfelelően működik:

// megadott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));

Ez a megvalósítás első látásra helyesnek tűnik. Mégis van komoly teljesítményproblémák:

  • elem eltávolítása az Tömb lista, az összes elemet eltolja utána
  • elemekhez való hozzáférés index alapján a LinkedList azt jelenti, hogy egyenként haladunk az elemeken, amíg meg nem találjuk az indexet

4. A az egyes Hurok

A Java 5 óta használhatjuk a az egyes hurok iterálni a Lista. Használjuk az elemek eltávolításához:

void removeAll (Lista lista, int elem) {for (Egész szám: lista) {if (Objektumok.egyenlő (szám, elem)) {list.remove (szám); }}}

Ne feledje, hogy használjuk Egész szám mint a ciklusváltozó típusa. Ezért nem kapunk egy NullPointerException.

Továbbá, így hivatkozunk List.remove (E elem), amely az eltávolítani kívánt értéket várja, nem pedig az indexet.

Bármennyire is tiszta, sajnos nem működik:

// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when assertThatThrownBy (() -> removeWithForEachLoop (list, valueToRemove)) .isInstanceOf (ConcurrentModificationException.class);

A az egyes hurok használ Iterátor hogy áthaladjon az elemeken. Azonban, amikor módosítjuk a Lista, a Iterátor következetlen állapotba kerül. Ezért dob ConcurrentModificationException.

A tanulság: nem szabad módosítanunk a Lista, miközben elemeihez hozzáférünk a az egyes hurok.

5. A Iterátor

Használhatjuk a Iterátor közvetlenül átmenni és módosítani a Lista ezzel:

void removeAll (Lista lista, int elem) {for (Iterator i = list.iterator (); i.hasNext ();) {Egész szám = i.next (); if (Objektumok.egyenlő (szám, elem)) {i.remove (); }}}

Ily módon, a Iterátor nyomon tudja követni a Lista (mert elvégzi a módosítást). Ennek eredményeként a fenti kód a várt módon működik:

// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));

Mivel minden Lista osztály biztosíthatja a sajátját Iterátor megvalósítását nyugodtan feltételezhetjük a lehető leghatékonyabban valósítja meg az elemek bejárását és eltávolítását.

Azonban felhasználva Tömb lista még mindig sok elemváltást jelent (és talán tömbök átcsoportosítása). Ezenkívül a fenti kód kissé nehezebben olvasható, mert eltér a szabványtól mert loop, amelyet a legtöbb fejlesztő ismer.

6. Gyűjtés

Addig módosítottuk az eredetit Lista objektum eltávolításával a nem szükséges elemeket. Inkább tehetjük újat csinálni Lista és gyűjtsük össze a megtartani kívánt tárgyakat:

Lista removeAll (Lista lista, int elem) {Lista megmaradt Elemek = új ArrayList (); mert (Egész szám: lista) {if (! Objects.equals (szám, elem)) {fennmaradóElementek.add (szám); }} return leftElements; }

Mivel egy új eredményt adunk Lista objektum, vissza kell adnunk a metódusból. Ezért a módszert más módon kell használnunk:

// megadott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // amikor a List eredmény = removeAll (list, valueToRemove); // majd assertThat (eredmény) .isEqualTo (lista (2, 3));

Ne feledje, hogy most már használhatjuk a az egyes ciklus, mivel nem módosítjuk a Lista jelenleg iterálunk.

Mivel nincs eltávolítás, nincs szükség az elemek áthelyezésére. Ezért ez a megvalósítás jól teljesít, ha egy Tömb lista.

Ez a megvalósítás bizonyos szempontból eltérően viselkedik, mint a korábbiak:

  • nem módosítja az eredetit Lista de egy újat ad vissza egy
  • a módszer eldönti, hogy mit adott vissza Lista’Végrehajtása az, eltérhet az eredetitől

Emellett módosíthatjuk megvalósításunkat a kapja meg a régi viselkedést; kitisztítjuk az eredetit Lista és adja hozzá az összegyűjtött elemeket:

void removeAll (Lista lista, int elem) {Lista megmaradt Elemek = új ArrayList (); mert (Egész szám: lista) {if (! Objects.equals (szám, elem)) {fennmaradóElementek.add (szám); }} list.clear (); list.addAll (többiElement); }

Ugyanúgy működik, mint korábban:

// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));

Mivel nem módosítjuk a Lista folytonosan nem kell helyenként hozzáférnünk az elemekhez, és nem kell elmozdítanunk őket. Ezenkívül csak két lehetséges tömb átcsoportosítás lehetséges: amikor hívunk List.clear () és List.addAll ().

7. A Stream API használata

A Java 8 bevezette a lambda kifejezéseket és a stream API-t. Ezekkel az erőteljes funkciókkal nagyon tiszta kóddal tudjuk megoldani a problémánkat:

Lista removeAll (Lista lista, int elem) {return list.stream () .filter (e ->! Objects.equals (e, element)) .collect (Collectors.toList ()); }

Ez a megoldás ugyanúgy működik, mint amikor a maradék elemeket gyűjtöttük.

Ennek eredményeként ugyanazokkal a tulajdonságokkal rendelkezik, és az eredmény visszaadásához használnunk kell:

// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // amikor a List eredmény = removeAll (list, valueToRemove); // majd assertThat (eredmény) .isEqualTo (lista (2, 3));

Ne feledje, hogy átalakíthatjuk úgy, hogy a többi megoldáshoz hasonlóan működjön, az eredeti „gyűjtő” megvalósítással megegyező megközelítéssel.

8. Használata removeIf

A lambdas és a funkcionális interfészek segítségével a Java 8 néhány API kiterjesztést is bevezetett. Például a List.removeIf () módszer, amely megvalósítja az utolsó szakaszban látottakat.

Arra számít, hogy a Állítmány, amelynek vissza kellene térnie igaz amikor el akarjuk távolítani az elem, szemben az előző példával, ahová vissza kellett térnünk igaz amikor meg akartuk tartani az elemet:

void removeAll (Lista lista, int elem) {list.removeIf (n -> Objects.equals (n, element)); }

Úgy működik, mint a fenti megoldások:

// adott Lista lista = lista (1, 1, 2, 3); int értékToRemove = 1; // when removeAll (list, valueToRemove); // majd assertThat (lista) .isEqualTo (lista (2, 3));

Annak a ténynek köszönhetően, hogy a Lista maga alkalmazza ezt a módszert, nyugodtan feltételezhetjük, hogy az elérhető legjobb teljesítményt nyújtja. Ráadásul ez a megoldás biztosítja a legtisztább kódot.

9. Következtetés

Ebben a cikkben sokféle megoldást láttunk egy egyszerű probléma megoldására, beleértve a helytelen problémákat is. Elemeztük őket, hogy megtaláljuk a legjobb megoldást minden forgatókönyvre.

Szokás szerint a példák elérhetők a GitHub oldalon.