streamalism.org

1. Oversigt

Når det kommer til samlinger, giver Java-standardbiblioteket masser af muligheder at vælge imellem. Blandt disse muligheder er to berømte Liste implementeringer kendt som ArrayList og LinkedList, hver med deres egne egenskaber og brugssager.

I denne vejledning skal vi se, hvordan disse to faktisk implementeres. Derefter vurderer vi forskellige applikationer for hver enkelt.

2. ArrayList

Internt, ArrayList bruger en matrix til at implementere Liste interface. Da arrays er faste i Java, ArrayList opretter en matrix med en vis startkapacitet. Undervejs, hvis vi har brug for at gemme flere varer end den standardkapacitet, vil den erstatte den matrix med en ny og mere rummelig.

For bedre at forstå dens egenskaber, lad os evaluere denne datastruktur med hensyn til dens tre hovedoperationer: tilføje elementer, få en efter indeks og fjerne efter indeks.

2.1. Tilføje

Når vi opretter en tom ArrayList, det initialiserer sit backing-array med en standardkapacitet (i øjeblikket 10):

Tilføjelse af et nyt element, mens det array endnu ikke er fuldt, er så simpelt som at tildele dette element til et specifikt array-indeks. Dette array-indeks bestemmes af den aktuelle array-størrelse, da vi praktisk talt føjes til listen:

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

Så, i bedste og gennemsnitlige tilfælde er tidskompleksiteten for tilføjelsesoperationen O (1), hvilket er ret hurtigt. Da backing-arrayet bliver fuldt, bliver implementeringen af ​​add dog mindre effektiv:

For at tilføje et nyt element skal vi først initialisere et helt nyt array med mere kapacitet og kopiere alle eksisterende elementer til det nye array. Først efter kopiering af aktuelle elementer kan vi tilføje det nye element. Derfor er tidskompleksiteten På) i værste fald siden vi er nødt til at kopiere n elementerne først.

Teoretisk set løber tilføjelse af et nyt element i afskrevet konstant tid. Det vil sige tilføje n elementer kræver På) tid. Nogle enkelte tilføjelser kan dog fungere dårligt på grund af kopien.

2.2. Adgang via indeks

Adgang til varer efter deres indekser er hvor ArrayList virkelig skinner. For at hente et element i indekset jeg, vi er bare nødt til at returnere varen, der bor på med indeks fra baggrundsarrayet. Følgelig, tidskompleksiteten for adgang ved indeksoperation er altid O (1).

2.3. Fjern efter indeks

Antag, at vi vil fjerne indeks 6 fra vores ArrayList, der svarer til elementet 15 i vores backing array:

Efter markering af det ønskede element som slettet, skal vi flytte alle elementer efter det tilbage med et indeks. Jo nærmere elementet til arrayets start er, jo flere elementer skal vi bevæge os. Så tidskompleksiteten er O (1) i bedste fald og På) i gennemsnit og værste tilfælde.

2.4. Ansøgninger og begrænsninger

Som regel, ArrayList er standardvalget for mange udviklere, når de har brug for en Liste implementering. Faktisk, det er faktisk et fornuftigt valg, når antallet af læsninger er langt mere end antallet af skrivninger.

Nogle gange har vi brug for lige hyppige læser og skriver. Hvis vi har et skøn over det maksimale antal mulige varer, er det stadig fornuftigt at bruge det ArrayList. Hvis det er tilfældet, kan vi initialisere ArrayList med en indledende kapacitet:

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

Dette skøn kan forhindre masser af unødvendig kopiering og arrayallokeringer.

I øvrigt, arrays indekseres af int værdier i Java. Så det er ikke muligt at gemme mere end 232 elementer i et Java-array og følgelig i ArrayList.

3. LinkedList

LinkedList, som navnet antyder, bruger en samling af sammenkædede noder til at gemme og hente elementer. For eksempel er her, hvordan Java-implementeringen ser ud efter at have tilføjet fire elementer:

Hver node opretholder to markører: en peger på det næste element og en anden henviser til den forrige. Udvidet til dette har den dobbeltkoblede liste to markører, der peger på det første og det sidste.

Lad os igen evaluere denne implementering med hensyn til de samme grundlæggende operationer.

3.1. Tilføje

For at tilføje en ny node skal vi først linke den aktuelle sidste node til den nye node:

Og opdater derefter den sidste markør:

Da begge disse operationer er trivielle, er tidskompleksiteten for tilføjelsesoperationen altid O (1).

3.2. Adgang via indeks

LinkedList, i modsætning til ArrayList, understøtter ikke hurtig tilfældig adgang. Så for at finde et element efter indeks, skal vi krydse en del af listenmanuelt.

I bedste fald, når det ønskede element er nær starten eller slutningen af ​​listen, vil tidskompleksiteten være så hurtig som O (1). I de gennemsnitlige og værst tænkelige scenarier kan vi dog ende med en På) adgangstid, da vi skal undersøge mange noder efter hinanden.

3.3. Fjern efter indeks

For at fjerne et element skal vi først finde det ønskede emne og derefter fjerne linket fra det fra listen. Derfor bestemmer adgangstiden tidskompleksiteten - det vil sige O (1) i bedste fald og På) i gennemsnit og i værste tilfælde.

3.4. Ansøgninger

LinkedLists er mere egnede, når tilsætningshastigheden er meget højere end læsehastigheden.

Det kan også bruges i læsetunge scenarier, når vi for det meste ønsker det første eller sidste element. Det er værd at nævne det LinkedList implementerer også Deque interface - understøtter effektiv adgang til begge ender af samlingen.

Generelt, hvis vi kender deres forskelle i implementering, kunne vi let vælge en til en bestemt brugssag.

Lad os for eksempel sige, at vi gemmer mange tidsseriebegivenheder i en liste-lignende datastruktur. Vi ved, at vi ville modtage udbrud af begivenheder hvert sekund.

Vi er også nødt til periodisk at undersøge alle begivenheder efter hinanden og give nogle statistikker. Til denne brugskasse LinkedList er et bedre valg, fordi tilføjelseshastigheden er meget højere end læsehastigheden.

Vi vil også læse alle emnerne, så vi ikke kan slå På) øvre grænse.

4. Konklusion

I denne vejledning begyndte vi først at dykke ned i hvordan ArrayList og Linklister implementeres i Java.

Vi evaluerede også forskellige brugssager for hver enkelt af disse.