LinkedList in Java met voorbeeld

Net als arrays in Java, is LinkedList een lineaire gegevensstructuur . LinkedList-elementen worden echter niet opgeslagen op aangrenzende locaties zoals arrays, ze worden aan elkaar gekoppeld met behulp van pointers. Elk element van de LinkedList heeft de verwijzing (adres / pointer) naar het volgende element van de LinkedList.

Inhoudsopgave

1. LinkedList-vertegenwoordiging
2. Waarom hebben we een gekoppelde lijst nodig?
3. Hiërarchie van de klasse LinkedList in Java
4. Java Linked List-voorbeeld voor het toevoegen van elementen
5. Java Linked List-voorbeeld van het verwijderen van elementen
6. Voorbeeld van LinkedList in Java
7. Methoden van klasse LinkedList
8. Tutorials op LinkedList - Alle methoden van de LinkedList-klasse worden gedetailleerd behandeld in afzonderlijke tutorials

LinkedList-weergave

Elk element in de LinkedList wordt het knooppunt genoemd . Elke Node van de LinkedList bevat twee items: 1) Inhoud van het element 2) Pointer / Address / Reference to the Next Node in de LinkedList.

Zo ziet een LinkedList eruit:

Notitie:
1. Hoofd van de LinkedList bevat alleen het adres van het eerste element van de lijst.
2. Het laatste element van de LinkedList bevat null in het pointergedeelte van de knoop omdat het het einde van de lijst is, zodat het nergens op wijst, zoals in het bovenstaande diagram.
3. Het diagram dat hierboven wordt weergegeven, vertegenwoordigt een afzonderlijk gekoppelde lijst . Er is een andere complexe variant van LinkedList die dubbel gekoppelde lijst wordt genoemd, knooppunt van een dubbel gekoppelde lijst bestaat uit drie delen: 1) Aanwijzer naar het vorige knooppunt van de gekoppelde lijst 2) inhoud van het element 3) aanwijzer naar het volgende knooppunt van de gekoppelde lijst.

Waarom hebben we een gekoppelde lijst nodig?

U moet zich bewust zijn van de arrays die ook een lineaire gegevensstructuur zijn, maar arrays hebben bepaalde beperkingen, zoals:
1) De grootte van de array is vast, wat wordt besloten wanneer we een array maken, dus het is moeilijk om vooraf het aantal elementen te voorspellen. Als de opgegeven grootte tekortschiet, kunnen we de grootte van een array niet vergroten en als we een grote array en hoeft u niet zoveel elementen op te slaan, dan is het verspilling van geheugen.

2) Matrixelementen hebben aangrenzende geheugenlocaties nodig om hun waarden op te slaan.

3) Het invoegen van een element in een array is qua prestaties duur, omdat we verschillende elementen moeten verplaatsen om ruimte te maken voor het nieuwe element. Bijvoorbeeld:
Laten we zeggen dat we een array hebben met de volgende elementen: 10, 12, 15, 20, 4, 5, 100, nu als we een nieuw element 99 willen invoegen na het element met waarde 12, moeten we alle elementen verschuiven na 12 aan hun recht om ruimte te maken voor een nieuw element.

Op dezelfde manier is het verwijderen van een element uit de array ook een prestatiewijze dure bewerking omdat alle elementen na het verwijderde element naar links moeten worden verschoven.

Deze beperkingen worden behandeld in de gekoppelde lijst door de volgende functies te bieden:
1. Gekoppelde lijst maakt dynamische geheugentoewijzing mogelijk , wat betekent dat geheugentoewijzing wordt gedaan tijdens de uitvoering door de compiler en we hoeven de grootte van de lijst niet te vermelden tijdens de aangifte van de gekoppelde lijst.

2. Gekoppelde lijstelementen hebben geen aaneengesloten geheugenlocaties nodig omdat elementen met elkaar zijn verbonden via het referentiedeel van het knooppunt dat het adres van het volgende knooppunt van de lijst bevat.

3. Bewerkingen in de gekoppelde lijst invoegen en verwijderen zijn qua prestaties niet duur, omdat voor het toevoegen en verwijderen van een element uit de gekoppelde lijst geen elementverschuiving nodig is, alleen de aanwijzer van het vorige en het volgende knooppunt moet worden gewijzigd.

Hiërarchie van klasse LinkedList in Java

Java Linked List-voorbeeld voor het toevoegen van elementen

In het volgende voorbeeld gebruiken we add() , addFirst() en addLast() methoden om de elementen op de gewenste locaties in de LinkedList toe te voegen, er zijn verschillende van dergelijke handige methoden in de klasse LinkedList die ik aan het einde van dit heb genoemd artikel.

  pakket com.beginnersbook; import java.util. *; public class JavaExample {public static void main (String args []) {  LinkedList <String> lijst = nieuwe LinkedList <String> ();  // Elementen toevoegen aan de gekoppelde lijst  list.add ( "Steve");  list.add ( "Carl");  list.add ( "Raj");  // Een element toevoegen aan de eerste positie  list.addFirst ( "Negan");  // Een element toevoegen aan de laatste positie  list.addLast ( "Rick");  // Een element toevoegen aan de 3e positie  list.add (2, "Glenn");  // Iterating LinkedList  Iterator <String> iterator = list.iterator ();  while (iterator.hasNext ()) {System.out.println (iterator.next ());  }}  } 

Output:

Java-voorbeeld van het verwijderen van elementen van de LinkedList

In het volgende voorbeeld bekijken we enkele populaire verwijderingsmethoden in de LinkedList die worden gebruikt om elementen van bepaalde posities in de LinkedList te verwijderen. Gedetailleerde uitleg van deze methoden samen met voorbeelden worden behandeld in de afzonderlijke tutorials, links worden aan het einde van dit artikel gegeven.

  pakket com.beginnersbook; import java.util. *; public class JavaExample {public static void main (String args []) {   LinkedList <String> lijst = nieuwe LinkedList <String> ();   // Elementen toevoegen aan de gekoppelde lijst   list.add ( "Steve");   list.add ( "Carl");   list.add ( "Raj");   list.add ( "Negan");   list.add ( "Rick");   // Eerste element verwijderen   // Hetzelfde als list.remove (0);   list.removeFirst ();   // Laatste element verwijderen   list.removeLast ();   // Iterating LinkedList   Iterator <String> iterator = list.iterator ();   while (iterator.hasNext ()) {  System.out.print (iterator.next () + "");   }   // 2e element verwijderen, index begint met 0   list.remove (1);   System.out.print ("\ nNa het verwijderen van het tweede element:");   // Opnieuw LinkedList   Iterator <String> iterator2 = list.iterator ();   while (iterator2.hasNext ()) {  System.out.print (iterator2.next () + "");   }} }

Output:

Voorbeeld van LinkedList in Java

  import java.util. *; openbare klasse LinkedListExample {  public static void main (String args []) {/ * Verklaring gekoppelde lijst * /LinkedList <String> linkedlist = nieuwe LinkedList <String> ();/ * add (String Element) wordt gebruikt voor het toevoegen  * de elementen aan de gekoppelde lijst * /linkedlist.add ( "Item1");linkedlist.add ( "item5");linkedlist.add ( "Item3");linkedlist.add ( "item6");linkedlist.add ( "Item2");/ * Inhoud gekoppelde lijst weergeven * /System.out.println ("Inhoud gekoppelde lijst:" + gekoppelde lijst);/ * Eerste en laatste element toevoegen * /linkedlist.addFirst ("First Item");linkedlist.addLast ("Last Item");System.out.println ("LinkedList Content na toevoeging:" + linkedlist);/ * Zo kunt u waarden verkrijgen en instellen * /Object firstvar = linkedlist.get (0);System.out.println ("First element:" + firstvar);linkedlist.set (0, "Eerste item gewijzigd");Object firstvar2 = linkedlist.get (0);System.out.println ("Eerste element na update volgens ingestelde methode:" + firstvar2);/ * Eerste en laatste element verwijderen * /linkedlist.removeFirst ();linkedlist.removeLast ();System.out.println ("LinkedList na verwijdering van eerste en laatste element:" + linkedlist);/ * Toevoegen aan een positie en verwijderen uit een positie * /linkedlist.add (0, "Nieuw item toegevoegd");linkedlist.remove (2);System.out.println ("Final Content:" + gekoppelde lijst);   } } 

Output:

  Inhoud gekoppelde lijst: [Item1, Item5, Item3, Item6, Item2] LinkedList Inhoud na toevoeging: [Eerste item, Item1, Item5, Item3, Item6, Item2, Laatste item] Eerste element: eerste item Eerste element na update volgens ingestelde methode: eerste item gewijzigd LinkedList na verwijdering van eerste en laatste element: [Item1, Item5, Item3, Item6, Item2] Definitieve inhoud: [Nieuw toegevoegd item, Item1, Item3, Item6, Item2] 

Methoden van klasse LinkedList:

Hier heb ik de korte beschrijving van de LinkedList-methoden genoemd, ik heb elk van deze methoden in afzonderlijke tutorials behandeld, links staan ​​aan het einde van dit artikel.

Overweeg llistobj voor alle voorbeelden in de onderstaande methoden als referentie voor LinkedList<String> .

LinkedList<String> llistobj = new LinkedList<String>();

1) boolean add (objectitem) : hiermee wordt het item aan het einde van de lijst toegevoegd.

  llistobj.add ( "Hello"); 

Het zou de tekenreeks "Hallo" aan het einde van de gekoppelde lijst toevoegen.

2) void add (int index, Object item) : het voegt een item toe aan de gegeven index van de lijst.

  llistobj.add (2, "doei"); 

Hiermee wordt de tekenreeks 'tot ziens' toegevoegd op de 3e positie (index 2 is 3e positie, index begint met 0).

3) boolean addAll (Collection c) : het voegt alle elementen van de opgegeven collection c toe aan de lijst. Het gooit NullPointerException als de opgegeven verzameling null is. Beschouw het onderstaande voorbeeld -

  LinkedList <String> llistobj = nieuwe LinkedList <String> (); ArrayList <String> arraylist = new ArrayList <String> (); arraylist.add ( "Tekenreeks1"); arraylist.add ( "String2"); llistobj.addAll (arraylist); 

Dit stuk code zou alle elementen van ArrayList aan de LinkedList toevoegen.

4) boolean addAll (int index, Collection c) : het voegt alle elementen van collection c toe aan de lijst, te beginnen met een index in de lijst. Het gooit NullPointerException als de verzameling c null is en IndexOutOfBoundsException wanneer de opgegeven index buiten het bereik valt.

  llistobj.add (5, arraylist); 

Het zou alle elementen van de ArrayList toevoegen aan de LinkedList vanaf positie 6 (index 5).

5) void addFirst (objectitem) : hiermee wordt het item (of element) op de eerste positie in de lijst toegevoegd.

  llistobj.addFirst ( "tekst"); 

Het zou de string "tekst" aan het begin van de lijst toevoegen.

6) void addLast (objectitem) : hiermee wordt het opgegeven item aan het einde van de lijst ingevoegd.

  llistobj.addLast ( "Chaitanya"); 

Deze verklaring voegt een tekenreeks 'Chaitanya' toe aan de eindpositie van de gekoppelde lijst.

7) void clear () : het verwijdert alle elementen van een lijst.

  llistobj.clear (); 

8) Object clone () : hiermee wordt de kopie van de lijst geretourneerd.

Want bijvoorbeeld My linkedList heeft vier items: text1, text2, text3 en text4.

  Object str = llistobj.clone ();  System.out.println (str); 

Output: De output van bovenstaande code zou zijn:

[text1, text2, text3, text4]

9) boolean bevat (objectitem) : het controleert of het gegeven item al dan niet in de lijst voorkomt. Als het item aanwezig is, retourneert het true else false.

  boolean var = llistobj.contains ("TestString"); 

Het zal controleren of de string "TestString" in de lijst voorkomt of niet.

10) Object get (int index) : hiermee wordt het item van de opgegeven index uit de lijst geretourneerd.

  Object var = llistobj.get (2); 

Het haalt het derde item uit de lijst.

11) Object getFirst () : hiermee wordt het eerste item uit de lijst opgehaald.

  Object var = llistobj.getFirst (); 

12) Object getLast () : hiermee wordt het laatste item uit de lijst opgehaald .

  Object var = llistobj.getLast (); 

13) int indexOf (objectitem) : hiermee wordt de index van het opgegeven item geretourneerd.

  llistobj.indexOf ( "bye"); 

14) int lastIndexOf (objectitem) : het retourneert de index van het laatste exemplaar van het opgegeven element.

  int pos = llistobj.lastIndexOf ("hallo); 

integer variabele pos zal de index hebben van de laatste keer dat string "hallo" voorkomt.

15) Object poll () : hiermee wordt het eerste item van de lijst geretourneerd en verwijderd.

  Object o = llistobj.poll (); 

16) Object pollFirst () : hetzelfde als poll () methode. Hiermee verwijdert u het eerste item uit de lijst.

  Object o = llistobj.pollFirst (); 

17) Object pollLast () : hiermee wordt het laatste element van de lijst geretourneerd en verwijderd.

  Object o = llistobj.pollLast (); 

18) Object remove () : hiermee wordt het eerste element van de lijst verwijderd.

  llistobj.remove (); 

19) Object remove (int index) : hiermee wordt het item verwijderd uit de lijst met de opgegeven index.

  llistobj.remove (4); 

Hiermee wordt het 5e element uit de lijst verwijderd.

20) Object remove (Object obj) : hiermee wordt het opgegeven object uit de lijst verwijderd.

  llistobj.remove ("testitem"); 

21) Object removeFirst () : hiermee wordt het eerste item uit de lijst verwijderd.

  llistobj.removeFirst (); 

22) Object removeLast () : hiermee wordt het laatste item uit de lijst verwijderd.

  llistobj.removeLast (); 

23) Object removeFirstOccurrence (objectitem) : hiermee wordt het eerste exemplaar van het opgegeven item verwijderd.

  llistobj.removeFirstOccurrence ( "tekst"); 

Hiermee wordt het eerste exemplaar van de tekenreeks 'tekst' uit de lijst verwijderd.

24) Object removeLastOccurrence (objectitem) : hiermee wordt het laatste exemplaar van het gegeven element verwijderd.

  llistobj.removeLastOccurrence ( "String1); 

Hiermee wordt de laatste reeks "String1" verwijderd.

25) Object set (int index, Object item) : het werkt het item van de opgegeven index bij met de geefwaarde.

  llistobj.set (2, "Test"); 

Het zal het 3e element bijwerken met de tekenreeks "Test".

26) int size () : hiermee wordt het aantal elementen van de lijst geretourneerd.

  llistobj.size (); 

Tutorials voor LinkedList

Hier zijn de tutorials die ik heb gedeeld op LinkedList.

LinkedList Basics

• Hoe LinkedList te herhalen

Toevoegen verwijderen

• Een element toevoegen aan LinkedList
• Element toevoegen aan specifieke index in LinkedList
• Voeg element toe aan het begin en einde van LinkedList
• Een element toevoegen aan de voorkant van LinkedList
• Verwijder eerste en laatste elementen van LinkedList
• Element verwijderen uit specifieke index
• Verwijder het opgegeven element uit LinkedList
• Verwijder alle elementen uit LinkedList
• Voeg alle elementen van een lijst toe aan LinkedList

Get / Zoeken

• Download eerste en laatste elementen van LinkedList
• Haal element uit specifieke index van LinkedList
• Zoekelement in LinkedList
• Download sublijst van LinkedList

Iterator / ListIterator

• Voorbeeld van LinkedList Iterator
• Voorbeeld van LinkedList ListIterator
• Voer een LinkedList in omgekeerde volgorde uit

Andere zelfstudies

• Vervang element door een nieuwe waarde in LinkedList
• Controleer of een bepaald element bestaat in LinkedList
• Een LinkedList klonen naar een andere LinkedList
• Haal de index op van het laatste exemplaar van een element in LinkedList
• LinkedList push () en pop () methoden
• LinkedList poll (), pollFirst () en pollLast () methoden
• LinkedList methoden peek (), peekFirst () en peekLast ()

conversie

• Converteer LinkedList naar ArrayList
• Converteer LinkedList naar Array

verschillen

• LinkedList versus ArrayList

Referentie

• LinkedList-documentatie