streamalism.org

1. Oversikt

Når det gjelder samlinger, gir Java-standardbiblioteket mange alternativer å velge mellom. Blant disse alternativene er to berømte Liste implementeringer kjent som ArrayList og LinkedList, hver med sine egne egenskaper og brukstilfeller.

I denne opplæringen skal vi se hvordan disse to faktisk implementeres. Deretter vil vi evaluere forskjellige applikasjoner for hver enkelt.

2. ArrayList

Internt, ArrayList bruker en matrise til å implementere Liste grensesnitt. Ettersom matriser har fast størrelse i Java, ArrayList oppretter en matrise med en viss startkapasitet. Underveis, hvis vi trenger å lagre flere gjenstander enn standardkapasiteten, vil den erstatte den matrisen med en ny og mer romslig.

For å bedre forstå egenskapene, la oss evaluere denne datastrukturen med hensyn til de tre hovedoperasjonene: legge til elementer, få en etter indeks og fjerne etter indeks.

2.1. Legge til

Når vi lager en tom ArrayList, den initialiserer sitt backing array med en standard kapasitet (for tiden 10):

Å legge til et nytt element mens det arrayet ennå ikke er fullt, er så enkelt som å tilordne det elementet til en bestemt array-indeks. Denne matriseindeksen bestemmes av gjeldende matrisestørrelse siden vi praktisk talt legger til listen:

backingArray [størrelse] = newItem; størrelse ++;

Så, i beste og gjennomsnittlige tilfeller er tidskompleksiteten for tilleggsoperasjonen O (1), som er ganske raskt. Når backing-arrayet blir fullt, blir add-implementeringen imidlertid mindre effektiv:

For å legge til et nytt element, bør vi først initialisere en helt ny matrise med mer kapasitet og kopiere alle eksisterende elementer til den nye matrisen. Først etter kopiering av nåværende elementer kan vi legge til det nye elementet. Derfor er tidskompleksiteten På) i verste fall siden vi må kopiere n elementene først.

Teoretisk sett går det å legge til et nytt element i amortisert konstant tid. Det vil si å legge til n elementer krever På) tid. Noen enkelte tillegg kan imidlertid fungere dårlig på grunn av kopien.

2.2. Tilgang via indeks

Å få tilgang til varer etter indeksene deres er der ArrayList skinner virkelig. Å hente et element i indeksen Jeg, vi må bare returnere varen som bor på ith indeks fra backing-arrayet. Følgelig tidskompleksiteten for tilgang ved indeksoperasjon er alltid O (1).

2.3. Fjern etter indeks

Anta at vi skal fjerne indeks 6 fra vår ArrayList, som tilsvarer elementet 15 i vårt backing array:

Etter å ha merket ønsket element som slettet, bør vi flytte alle elementene etter det med en indeks. Jo nærmere elementet begynner på matrisen, jo flere elementer skal vi selvsagt flytte. Så tidskompleksiteten er O (1) i beste fall og På) i gjennomsnitt og verste tilfeller.

2.4. Søknader og begrensninger

Som oftest, ArrayList er standardvalget for mange utviklere når de trenger en Liste gjennomføring. Faktisk, det er faktisk et fornuftig valg når antall lesinger er langt mer enn antall skriver.

Noen ganger trenger vi like hyppige lesinger og skrivinger. Hvis vi har et estimat på maksimalt antall mulige varer, er det fortsatt fornuftig å bruke ArrayList. Hvis det er tilfelle, kan vi initialisere ArrayList med en innledende kapasitet:

int possibleUpperBound = 10_000; Listeelementer = ny ArrayList (muligUpperBound);

Denne estimeringen kan forhindre mye unødvendig kopiering og matrixallokering.

Videre arrays indekseres av int verdier i Java. Så det er ikke mulig å lagre mer enn 232 elementer i et Java-array og følgelig i ArrayList.

3. LinkedList

LinkedList, som navnet antyder, bruker en samling koblede noder for å lagre og hente elementer. Her er for eksempel hvordan Java-implementeringen ser ut etter å ha lagt til fire elementer:

Hver node opprettholder to pekere: en som peker til neste element og en annen som henviser til den forrige. Utvidet på dette har den dobbeltkoblede listen to pekere som peker på det første og siste elementet.

Igjen, la oss evaluere denne implementeringen med hensyn til de samme grunnleggende operasjonene.

3.1. Legge til

For å legge til en ny node, bør vi først koble den nåværende siste noden til den nye noden:

Og oppdater deretter den siste pekeren:

Siden begge disse operasjonene er trivielle, er tidskompleksiteten for tilleggsoperasjonen alltid O (1).

3.2. Tilgang via indeks

LinkedList, i motsetning til ArrayList, støtter ikke rask tilfeldig tilgang. Så for å finne et element etter indeks, bør vi krysse en del av listenmanuelt.

I beste fall, når det forespurte elementet er nær begynnelsen eller slutten av listen, vil tidskompleksiteten være like rask som O (1). I gjennomsnitt og i verste fall kan vi imidlertid ende opp med en På) tilgangstid siden vi må undersøke mange noder etter hverandre.

3.3. Fjern etter indeks

For å fjerne et element, bør vi først finne det etterspurte elementet og deretter fjerne tilknytningen fra listen. Følgelig bestemmer tilgangstiden tidskompleksiteten - det vil si O (1) i beste fall og På) i gjennomsnitt og i verste fall.

3.4. applikasjoner

LinkedLists er mer passende når tilsetningshastigheten er mye høyere enn lesehastigheten.

Det kan også brukes i lesetunge scenarier når vi mest ønsker det første eller siste elementet. Det er verdt å nevne det LinkedList implementerer også Deque grensesnitt - støtter effektiv tilgang til begge ender av samlingen.

Generelt sett, hvis vi vet implementeringsforskjellene deres, kan vi enkelt velge en for en bestemt brukssak.

La oss for eksempel si at vi skal lagre mange tidsseriehendelser i en listelignende datastruktur. Vi vet at vi vil motta utbrudd av hendelser hvert sekund.

Vi må også undersøke alle hendelsene etter hverandre med jevne mellomrom og gi litt statistikk. For denne brukssaken, LinkedList er et bedre valg fordi tilleggshastigheten er mye høyere enn lesehastigheten.

Vi vil også lese alle elementene, så vi kan ikke slå På) øvre grense.

4. Konklusjon

I denne veiledningen tok vi først et dykk inn i hvordan ArrayList og Linklister er implementert i Java.

Vi vurderte også forskjellige brukssaker for hver av disse.