streamalism.org

1. Overzicht

Als het om collecties gaat, biedt de Java-standaardbibliotheek tal van opties om uit te kiezen. Onder die opties zijn er twee beroemd Lijst implementaties bekend als ArrayList en LinkedList, elk met hun eigen eigenschappen en use-cases.

In deze tutorial gaan we zien hoe deze twee daadwerkelijk worden geïmplementeerd. Vervolgens zullen we voor elke aanvraag verschillende aanvragen evalueren.

2. ArrayList

Intern, ArrayList gebruikt een array om het Lijst koppel. Omdat arrays een vaste grootte hebben in Java, ArrayList creëert een array met enige initiële capaciteit. Als we onderweg meer items moeten opslaan dan die standaardcapaciteit, zal het die array vervangen door een nieuwe en ruimere.

Laten we, om de eigenschappen ervan beter te begrijpen, deze datastructuur evalueren met betrekking tot de drie belangrijkste bewerkingen: items toevoegen, één per index ophalen en verwijderen per index.

2.1. Toevoegen

Wanneer we een lege creëren ArrayList, het initialiseert zijn ondersteunende array met een standaardcapaciteit (momenteel 10):

Het toevoegen van een nieuw item terwijl die array nog niet vol is, is net zo eenvoudig als het toewijzen van dat item aan een specifieke array-index. Deze array-index wordt bepaald door de huidige array-grootte, aangezien we praktisch aan de lijst worden toegevoegd:

backingArray [size] = newItem; maat ++;

Zo, in de beste en gemiddelde gevallen is de tijdcomplexiteit voor de add-bewerking O (1), wat behoorlijk snel is. Als de backing-array echter vol raakt, wordt de add-implementatie minder efficiënt:

Om een ​​nieuw item toe te voegen, moeten we eerst een geheel nieuwe array met meer capaciteit initialiseren en alle bestaande items naar de nieuwe array kopiëren. Pas na het kopiëren van de huidige elementen kunnen we het nieuwe item toevoegen. Daarom is de tijdcomplexiteit Aan) in het ergste geval omdat we moeten kopiëren n elementen eerst.

Theoretisch gezien verloopt het toevoegen van een nieuw element in afgeschreven constante tijd. Dat wil zeggen, toevoegen n elementen vereist Aan) tijd. Sommige enkele toevoegingen kunnen echter slecht presteren vanwege de overheadkosten voor kopiëren.

2.2. Toegang via Index

Toegang tot items op basis van hun index is waar de ArrayList schijnt echt. Om een ​​item op te halen bij index ik, we hoeven alleen het item dat in de ith index van de achtergrondarray. Bijgevolg, de tijdcomplexiteit voor toegang door indexbewerking is altijd O (1).

2.3. Verwijderen via Index

Stel dat we de index 6 gaan verwijderen uit onze ArrayList, wat overeenkomt met het element 15 in onze backing-array:

Nadat we het gewenste element als verwijderd hebben gemarkeerd, moeten we alle elementen erna één index terug verplaatsen. Het is duidelijk dat hoe dichter het element bij het begin van de array staat, hoe meer elementen we moeten verplaatsen. Dus de tijdcomplexiteit is O (1) in het beste geval en Aan) gemiddeld en in de slechtste gevallen.

2.4. Toepassingen en beperkingen

Meestal ArrayList is de standaardkeuze voor veel ontwikkelaars wanneer ze een Lijst implementatie. Eigenlijk, het is eigenlijk een verstandige keuze als het aantal leesbewerkingen veel meer is dan het aantal schrijfbewerkingen.

Soms moeten we even vaak lezen en schrijven. Als we een schatting hebben van het maximale aantal mogelijke items, dan is het toch zinvol om te gebruiken ArrayList. Als dat het geval is, kunnen we het ArrayList met een initiële capaciteit:

int mogelijkUpperBound = 10_000; Lijstitems = nieuwe ArrayList (mogelijkUpperBound);

Deze schatting kan veel onnodig kopiëren en array-toewijzingen voorkomen.

Bovendien, arrays worden geïndexeerd door int waarden in Java. Het is dus niet mogelijk om meer op te slaan dan 232 elementen in een Java-array en bijgevolg in ArrayList.

3. LinkedList

LinkedList, zoals de naam suggereert, gebruikt een verzameling gekoppelde knooppunten om elementen op te slaan en op te halen. Dit is bijvoorbeeld hoe de Java-implementatie eruitziet na het toevoegen van vier elementen:

Elk knooppunt bevat twee verwijzingen: een die naar het volgende element verwijst en een andere die naar het vorige verwijst. Als aanvulling hierop heeft de dubbel gelinkte lijst twee verwijzingen naar de eerste en laatste items.

Nogmaals, laten we deze implementatie evalueren met betrekking tot dezelfde fundamentele bewerkingen.

3.1. Toevoegen

Om een ​​nieuw knooppunt toe te voegen, moeten we eerst het huidige laatste knooppunt aan het nieuwe knooppunt koppelen:

En werk vervolgens de laatste aanwijzer bij:

Aangezien beide bewerkingen triviaal zijn, is de tijdcomplexiteit voor de optelbewerking altijd O (1).

3.2. Toegang via Index

LinkedList, in tegenstelling tot ArrayList, ondersteunt geen snelle willekeurige toegang. Dus om een ​​element per index te vinden, moeten we een deel van de lijst doorlopenhandmatig.

In het beste geval, wanneer het aangevraagde item bijna aan het begin of einde van de lijst staat, is de tijdcomplexiteit zo snel als O (1). In de gemiddelde en worstcasescenario's kunnen we echter eindigen met een Aan) toegangstijd omdat we veel knooppunten na elkaar moeten onderzoeken.

3.3. Verwijderen via Index

Om een ​​item te verwijderen, moeten we eerst het gevraagde item vinden en het vervolgens uit de lijst verwijderen. Bijgevolg bepaalt de toegangstijd de tijdcomplexiteit - dat wil zeggen, O (1) in het beste geval en Aan) gemiddeld en in het ergste geval.

3.4. Toepassingen

LinkedLists zijn geschikter wanneer de toevoegsnelheid veel hoger is dan de leessnelheid.

Het kan ook worden gebruikt in scenario's met veel leesvoer wanneer we meestal het eerste of laatste element willen. Dat is het vermelden waard LinkedList implementeert ook de Deque interface - ondersteunt efficiënte toegang tot beide uiteinden van de collectie.

Over het algemeen, als we hun implementatieverschillen kennen, kunnen we er gemakkelijk een kiezen voor een bepaald gebruik.

Laten we bijvoorbeeld zeggen dat we veel tijdreeksgebeurtenissen gaan opslaan in een lijstachtige datastructuur. We weten dat we elke seconde uitbarstingen van gebeurtenissen zouden ontvangen.

We moeten ook periodiek alle gebeurtenissen na elkaar bekijken en enkele statistieken verstrekken. Voor deze use-case, LinkedList is een betere keuze omdat de toevoegsnelheid veel hoger is dan de leessnelheid.

We zouden ook alle items lezen, dus we kunnen de Aan) bovengrens.

4. Conclusie

In deze tutorial hebben we eerst gedoken in hoe ArrayList en LinkLists zijn geïmplementeerd in Java.

We hebben voor elk van deze ook verschillende use-cases geëvalueerd.