Java >> Java tutorial >  >> Tag >> ArrayList

Vend en ArrayList i Java

ArrayList

1. Oversigt

ArrayList er en ofte brugt Liste implementering i Java.

I denne øvelse vil vi undersøge, hvordan man vender en ArrayList om .

2. Introduktion til problemet

Lad os som sædvanligt forstå problemet gennem et eksempel. Lad os sige, at vi har en liste af Heltal :

​List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));

Efter vendingen forventer vi at have resultatet:

List<Integer> EXPECTED = new ArrayList<>(Arrays.asList(7, 6, 5, 4, 3, 2, 1));

Så kravet ser ret ligetil ud. Problemet kan dog have et par varianter:

  • Tilbageførsel af en liste på plads
  • Tilbageførsel af en liste og returnere resultatet som en ny liste objekt

Vi vil dække begge tilfælde i dette selvstudie.

Java-standardbiblioteket har givet en hjælpemetode til at udføre jobbet. Vi vil se, hvordan vi hurtigt kan løse problemet ved hjælp af denne metode.

I betragtning af, at nogle af os måske lærer Java, vil vi desuden behandle to interessante, men effektive implementeringer af at vende en liste .

Lad os derefter se dem i aktion.

3. Brug af standard Collections.reverse Metode

Java-standardbiblioteket har leveret Collections.reverse metode til at vende rækkefølgen af ​​elementerne i den givne liste .

Denne praktiske metode udfører vending på stedet, hvilket vil vende rækkefølgen i den oprindelige liste, den modtog. Men lad os først oprette en enhedstestmetode for at forstå den:

List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
Collections.reverse(aList);
assertThat(aList).isEqualTo(EXPECTED);

Når vi udfører testen ovenfor, består den. Som vi har set, har vi bestået aList gøre indsigelse mod det omvendte metode, og derefter rækkefølgen af ​​elementerne i aList objekt bliver vendt.

I tilfælde af at vi ikke ønsker at ændre den originale liste , og forvent at få en ny liste objekt til at indeholde elementerne i omvendt rækkefølge, kan vi sende en ny Liste  gøre indsigelse mod omvendt metode:

List<Integer> originalList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
List<Integer> aNewList = new ArrayList<>(originalList);
Collections.reverse(aNewList);

assertThat(aNewList).isNotEqualTo(originalList).isEqualTo(EXPECTED);

På denne måde beholder vi originalList uberørt, og rækkefølgen af ​​elementerne i aNewList er omvendt.

Som vi kan se fra de to eksempler ovenfor, er standarden Collections.reverse metoden er ret praktisk til at vende en Liste .

Men hvis vi lærer Java, vil vi sandsynligvis øve os i at implementere en "omvendt" metode selv.

Lad os derefter udforske et par gode implementeringer:en ved hjælp af rekursion og en anden ved hjælp af en simpel løkke.

4. Reversere en liste Brug af rekursion

Lad os først implementere vores egen liste-omvendte metode ved hjælp af rekursionsteknikken. Lad os først tage et kig på implementeringen:

public static <T> void reverseWithRecursion(List<T> list) {
    if (list.size() > 1) {
        T value = list.remove(0);
        reverseWithRecursion(list);
        list.add(value);
    }
}

Som vi kan se, ser implementeringen ovenfor ret kompakt ud. Lad os nu forstå, hvordan det virker.

Stopbetingelsen i vores rekursionslogik er list.size() <=1 . Med andre ord, hvis listen objektet er tomt eller kun indeholder et enkelt element, stopper vi rekursionen .

I hvert rekursionskald udfører vi "T value =list.remove(0) “, viser det første element fra listen. Det fungerer på denne måde:

recursion step 0: value = null, list = (1, 2, 3, ... 7)
   |_ recursion step 1: value = 1, list = (2, 3, 4,...7)
      |_ recursion step 2: value = 2, list = (3, 4, 5, 6, 7)
         |_ recursion step 3: value = 3, list = (4, 5, 6, 7)
            |_ ...
               |_ recursion step 6: value = 6, list = (7)

Som vi kan se, når listen objektet kun indeholder ét element (7), stopper vi rekursionen og begynder derefter at udføre list.add(value)  fra bunden. Det vil sige, at vi først tilføjer 6 til slutningen af ​​listen, derefter 5, så 4, og så videre. I sidste ende er rækkefølgen af ​​elementerne på listen blevet omvendt. Yderligere, denne metode kører i lineær tid .

Lad os derefter lave en test for at bekræfte, om vores rekursionsimplementering fungerer som forventet:

List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
ReverseArrayList.reverseWithRecursion(aList);
assertThat(aList).isEqualTo(EXPECTED);

Hvis vi kører testen, består den. Så vores rekursionsimplementering løser problemet.

5. Reversere en liste Brug af iteration

Vi har lige vendt listen ved hjælp af rekursion. Alternativt kan vi løse problemet ved hjælp af iteration.

Lad os først se på implementeringen:

public static <T> void reverseWithLoop(List<T> list) {
    for (int i = 0, j = list.size() - 1; i < j; i++) {
        list.add(i, list.remove(j));
    }
}

Som vi kan se, er iterationsimplementeringen også ret pæn. Vi har dog kun én for loop, og i loop-kroppen har vi kun én enkelt sætning.

Lad os derefter forstå, hvordan det virker.

Vi definerede to pointere, i og j , på den givne liste. Markøren j peger altid på det sidste element på listen. Men pointen i  trin fra 0 til j-1 .

Vi fjerner det sidste element ved hvert iterationstrin og udfylder det til i-th position ved hjælp af list.add(i, list.remove(j)) . Når i når j-1 , løkken slutter, og vi har vendt listen om:

Iteration step 0: i = j = null, list = (1, 2, 3,...7)
Iteration step 1: i = 0; j = 6 
                  |_ list.add(0, list.remove(6))
                  |_ list = (7, 1, 2, 3, 4, 5, 6)
Iteration step 2: i = 1; j = 6 
                  |_ list.add(1, list.remove(6))
                  |_ list = (7, 6, 1, 2, 3, 4, 5)
...
Iteration step 5: i = 4; j = 6 
                  |_ list.add(4, list.remove(6))
                  |_ list = (7, 6, 5, 4, 3, 1, 2)
Iteration step 6: i = 5; j = 6 
                  |_ list.add(5, list.remove(6))
                  |_ list = (7, 6, 5, 4, 3, 2, 1)

Metoden kører i lineær tid også.

Lad os endelig teste vores metode, og se om den virker som forventet:

List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
ReverseArrayList.reverseWithLoop(aList);
assertThat(aList).isEqualTo(EXPECTED);

Når vi kører testen ovenfor, består den.

6. Konklusion

I denne artikel har vi behandlet, hvordan man vender en ArrayList om gennem eksempler. Standarden Collections.reverse metoden er ret praktisk til at løse dette problem.

Men hvis vi gerne vil skabe vores egne reverserende implementeringer, har vi lært to effektive reverseringsmetoder på stedet.

Som sædvanlig kan den komplette kode til denne artikel findes på GitHub.


No
Java tag