streamalism.org

1. Pregled

Što se tiče zbirki, Java standardna knjižnica nudi mnoštvo mogućnosti za odabir. Među tim su mogućnostima dvije poznate Popis implementacije poznate kao ArrayList i LinkedList, svaki sa svojim svojstvima i slučajevima upotrebe.

U ovom uputstvu vidjet ćemo kako se ovo dvoje zapravo provodi. Zatim ćemo procijeniti različite prijave za svaku od njih.

2. ArrayList

Interno, ArrayList koristi niz za implementaciju Popis sučelje. Kako su nizovi fiksne veličine u Javi, ArrayList stvara niz s nekim početnim kapacitetom. Usput, ako trebamo pohraniti više predmeta od zadanog kapaciteta, zamijenit će taj niz novim i prostranijim.

Da bismo bolje razumjeli njegova svojstva, procijenimo ovu strukturu podataka s obzirom na tri glavne operacije: dodavanje stavki, dobivanje jedne indeksom i uklanjanje indeksom.

2.1. Dodati

Kad stvaramo prazno ArrayList, inicijalizira svoj backing niz sa zadanim kapacitetom (trenutno 10):

Dodavanje nove stavke dok taj niz koji još nije popunjen jednostavno je poput dodjeljivanja te stavke određenom indeksu niza. Ovaj indeks niza određen je trenutnom veličinom niza jer se praktički dodajemo na popis:

backingArray [veličina] = newItem; veličina ++;

Tako, u najboljim i prosječnim slučajevima složenost vremena za operaciju zbrajanja je O (1), što je prilično brzo. Kako se sigurnosni niz puni, međutim, implementacija dodavanja postaje manje učinkovita:

Da bismo dodali novu stavku, prvo bismo trebali inicijalizirati potpuno novi niz s većim kapacitetom i kopirati sve postojeće stavke u novi niz. Tek nakon kopiranja trenutnih elemenata možemo dodati novu stavku. Dakle, vremenska složenost je Na) u najgorem slučaju otkad moramo kopirati n elementi prvi.

Teoretski gledano, dodavanje novog elementa radi u amortiziranom stalnom vremenu. Odnosno dodavanje n elementi zahtijeva Na) vrijeme. Međutim, neki pojedinačni dodaci mogu imati lošu izvedbu zbog kopiranja.

2.2. Pristup putem indeksa

Pristup stavkama prema njihovim indeksima je mjesto gdje ArrayList stvarno sja. Za preuzimanje stavke u indeksu ja, samo moramo vratiti predmet koji boravi u i indeks iz pozadinskog niza. Slijedom toga, vremenska složenost pristupa radom indeksa je uvijek O (1).

2.3. Ukloni indeksom

Pretpostavimo da ćemo ukloniti indeks 6 iz našeg ArrayList, što odgovara elementu 15 u našem temeljnom nizu:

Nakon što smo željeni element označili kao izbrisan, trebali bismo premjestiti sve elemente nakon njega za jedan indeks. Očito je, što je element bliži početku niza, to bismo više elemenata trebali premjestiti. Dakle, vremenska složenost je O (1) u najboljem slučaju i Na) u prosjeku i u najgorem slučaju.

2.4. Primjene i ograničenja

Obično, ArrayList je zadani izbor za mnoge programere kada im treba Popis provedba. Zapravo, zapravo je razuman izbor kada je broj čitanja daleko veći od broja upisa.

Ponekad nam trebaju jednako česta čitanja i pisanja. Ako imamo procjenu maksimalnog broja mogućih predmeta, onda to još uvijek ima smisla koristiti ArrayList. Ako je to slučaj, možemo inicijalizirati ArrayList s početnim kapacitetom:

int possibleUpperBound = 10_000; Stavke na popisu = novi ArrayList (possibleUpperBound);

Ova procjena može spriječiti puno nepotrebnih dodjela kopiranja i polja.

Štoviše, nizovi se indeksiraju pomoću int vrijednosti u Javi. Dakle, nije moguće pohraniti više od 232 elementi u Java nizu i, prema tome, u ArrayList.

3. LinkedList

LinkedList, kako mu samo ime govori, koristi zbirku povezanih čvorova za spremanje i dohvaćanje elemenata. Na primjer, evo kako izgleda implementacija Java nakon dodavanja četiri elementa:

Svaki čvor održava dva pokazivača: jedan koji upućuje na sljedeći element i drugi koji se odnosi na prethodni. Proširujući se na ovome, dvostruko povezani popis ima dva pokazivača koji upućuju na prvu i posljednju stavku.

Opet, procijenimo ovu provedbu s obzirom na iste temeljne operacije.

3.1. Dodati

Da bismo dodali novi čvor, prvo bismo trebali povezati trenutni posljednji čvor s novim čvorom:

A zatim ažurirajte zadnji pokazivač:

Kako su obje ove operacije trivijalne, vremenska složenost operacije dodavanja uvijek je O (1).

3.2. Pristup putem indeksa

LinkedList, za razliku od ArrayList, ne podržava brzi nasumični pristup. Dakle, da bismo pronašli element po indeksu, trebali bismo preći neki dio popisaručno.

U najboljem slučaju, kada je tražena stavka blizu početka ili kraja popisa, vremenska složenost bila bi brza kao O (1). Međutim, u prosječnom i najgorem slučaju možemo završiti s Na) pristupno vrijeme jer moramo ispitati mnoge čvorove jedan za drugim.

3.3. Ukloni indeksom

Da bismo uklonili stavku, prvo bismo trebali pronaći traženu stavku, a zatim je prekinuti vezu s popisa. Slijedom toga, vrijeme pristupa određuje vremensku složenost - tj. O (1) u najboljem slučaju i Na) u prosjeku i u najgorem slučaju.

3.4. Prijave

LinkedLists prikladniji su kada je brzina dodavanja mnogo veća od brzine čitanja.

Također, može se koristiti u scenarijima teškim za čitanje kada većinu vremena želimo prvi ili zadnji element. Vrijedno je to spomenuti LinkedList također provodi Deque sučelje - podržava učinkovit pristup oba kraja zbirke.

Općenito, ako znamo njihove razlike u implementaciji, tada bismo lako mogli odabrati jednu za određeni slučaj upotrebe.

Na primjer, recimo da ćemo pohraniti puno događaja vremenskih serija u strukturu podataka nalik popisu. Znamo da bismo svake sekunde dobivali rafalne događaje.

Također, moramo povremeno ispitati sve događaje jedan za drugim i pružiti neke statistike. Za ovaj slučaj upotrebe, LinkedList je bolji izbor jer je stopa dodavanja mnogo veća od brzine čitanja.

Također, pročitali bismo sve stavke, tako da ne možemo pobijediti Na) Gornja granica.

4. Zaključak

U ovom uputstvu prvo smo zaronili kako ArrayList i Popisi veza implementirani su u Javi.

Također smo procijenili različite slučajeve upotrebe za svaki od njih.