Een gids voor de Java LinkedList

1. Inleiding

LinkedList is een dubbel gekoppelde lijstimplementatie van de Lijst en Deque interfaces. Het implementeert alle optionele lijstbewerkingen en staat alle elementen toe (inclusief nul).

2. Kenmerken

Hieronder staan ​​de belangrijkste eigenschappen van de LinkedList:

  • Bewerkingen die in de lijst worden geïndexeerd, zullen de lijst doorlopen vanaf het begin of het einde, afhankelijk van wat het dichtst bij de gespecificeerde index ligt
  • Het is niet gesynchroniseerd
  • Haar Iterator en ListIterator iterators zijn fail-fast (wat betekent dat na het aanmaken van de iterator, als de lijst is gewijzigd, een ConcurrentModificationException zal worden gegooid)
  • Elk element is een knooppunt, dat een verwijzing naar de volgende en vorige behoudt
  • Het handhaaft de invoegvolgorde

Hoewel LinkedList niet gesynchroniseerd is, kunnen we een gesynchroniseerde versie ervan ophalen door de Collections.synchronizedList methode, zoals:

List list = Collections.synchronizedList (nieuwe LinkedList (...));

3. Vergelijking met ArrayList

Hoewel beiden het Lijst interface, ze hebben verschillende semantiek - wat zeker van invloed zal zijn op de beslissing welke te gebruiken.

3.1. Structuur

Een ArrayList is een op een index gebaseerde datastructuur ondersteund door een Array. Het biedt willekeurige toegang tot zijn elementen met een prestatie gelijk aan O (1).

Aan de andere kant is een LinkedList slaat zijn gegevens op als een lijst met elementen en elk element is gekoppeld aan zijn vorige en volgende element. In dit geval heeft de zoekbewerking voor een item een ​​uitvoeringstijd die gelijk is aan O (n).

3.2. Operaties

Het invoegen, toevoegen en verwijderen van een item gaat sneller in een LinkedList omdat het niet nodig is om de grootte van een array te wijzigen of de index bij te werken wanneer een element wordt toegevoegd aan een willekeurige positie binnen de verzameling, zullen alleen verwijzingen in omringende elementen veranderen.

3.3. Geheugengebruik

EEN LinkedList verbruikt meer geheugen dan een ArrayList vanwege elk knooppunt in een LinkedList slaat twee verwijzingen op, een voor het vorige element en een voor het volgende element, terwijl ArrayList bevat alleen gegevens en de bijbehorende index.

4. Gebruik

Hier zijn enkele codevoorbeelden die laten zien hoe u LinkedList:

4.1. Creatie

LinkedList linkedList = nieuwe LinkedList ();

4.2. Element toevoegen

LinkedList werktuigen Lijst en Deque interface, naast standaard toevoegen() en Voeg alles toe() methoden die u kunt vinden addFirst () en addLast (), die respectievelijk een element aan het begin of het einde toevoegt.

4.3. Element verwijderen

Net als bij het toevoegen van elementen, biedt deze lijstimplementatie removeFirst () en removeLast ().

Er is ook een handige methode removeFirstOccurence () en removeLastOccurence () die boolean retourneert (waar als de verzameling een opgegeven element bevat).

4.4. Wachtrijbewerkingen

Deque interface biedt wachtrij-achtig gedrag (eigenlijk Deque strekt zich uit Wachtrij koppel):

linkedList.poll (); linkedList.pop ();

Die methoden halen het eerste element op en verwijderen het uit de lijst.

Het verschil tussen poll () en knal() is dat knal zal gooien NoSuchElementException () op lege lijst, terwijl poll geeft null terug. De API's pollFirst () en pollLast () zijn ook beschikbaar.

Hier is bijvoorbeeld hoe de Duwen API werkt:

linkedList.push (Object o);

Dat voegt het element toe als het hoofd van de collectie.

LinkedList heeft vele andere methoden, waarvan de meeste bekend zouden moeten zijn bij een gebruiker die al gebruikmaakt van Lijsten. Anderen die worden geleverd door Deque kan een handig alternatief zijn voor 'standaard'-methoden.

De volledige documentatie is hier te vinden.

5. Conclusie

ArrayList is meestal de standaardinstelling Lijst implementatie.

Er zijn echter bepaalde gebruiksscenario's waarbij LinkedList zal beter passen, zoals voorkeuren voor constante invoeg- / verwijderingstijd (bijv. frequente invoegingen / verwijderingen / updates), ten opzichte van constante toegangstijd en effectief geheugengebruik.

Codevoorbeelden zijn te vinden op GitHub.