Gekoppelde lijstgegevensstructuur in Java

Er worden verschillende datastructuren gemaakt voor verschillende doeleinden. Misschien ken je ArrayList (zo niet, dan raden we je aan om er eerst over te lezen). In dit artikel gaan we leren over LinkedList en beseffen waar deze collectie goed voor is. Als u de klassecodebron van LinkedList Java 8 (of latere versie van de taal) bekijkt (op de Oracle-website of in uw IDE, in het geval van IDEA: crtl+B op de klassenaam), ziet u de volgende declaratie:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Op dit moment is de belangrijkste informatie uit de code het feit dat LinkedList List- en Deque- interfaces implementeert . De List-interface houdt de volgorde van het toevoegen van items bij en biedt toegang tot het item per index. De "gewone" wachtrij ondersteunt het toevoegen van elementen aan het einde en het extraheren ervan vanaf het begin. Deque is een tweerichtingswachtrij en ondersteunt het toevoegen en verwijderen van elementen van beide kanten. U kunt het zien als een combinatie van stapel en wachtrij. LinkedList is dus een implementatie van deze twee, en het stelt ons in staat om een ​​bidirectionele wachtrij te maken die bestaat uit alle objecten, inclusief null. Gelinkte lijstis een verzameling elementen. We kunnen het zien in de codebron van de klasse, let deze keer op de velden:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

Elk element, meestal noemden we het Node , bevat een object en verwijzingen naar twee naburige objecten - het vorige en het volgende. Daarom is het niet erg effectief in termen van geheugengebruik. Omdat LinkedList eigenlijk een bidirectionele structuur is, kunnen we eenvoudig elementen van beide kanten toevoegen of verwijderen.

LinkedList-constructeurs

Terug naar de codebron kunnen we ontdekken dat LinkedList twee constructors heeft

• LinkedList() zonder parameters wordt gebruikt om een ​​lege lijst samen te stellen.
• >LinkedList(Collection<? extends E> c) is voor het maken van een lijst met de elementen van de gespecificeerde collectie, in de volgorde waarin ze worden geretourneerd door de iterator van de collectie.

LinkedList-verklaring

In feite bestaat een gekoppelde lijst (Java of in een andere taal) uit een reeks knooppunten. Elk knooppunt is ontworpen om een ​​object op te slaan van een type dat bij het maken is gedefinieerd. Dus om LinkedList te maken , is Java-code de volgende:

LinkedList<Integer> myList = new LinkedList<>();

We hebben een doel om een ​​reeks gehele getallen en links naar de buren te behouden. Op dit moment staat het echter leeg.

LinkedList Hoofdbewerkingen

Zoals gewoonlijk kun je in het geval van Collections elementen in LinkedList plaatsen (tot het einde ervan of in het midden), daaruit verwijderen en een element per index ophalen. Dus hier zijn ze:

• add(E element) Voegt het gespecificeerde element toe aan het einde van deze lijst;
• add(int index, E element) Voegt het element in op de gespecificeerde positie index ;
• get(int index) Geeft het element terug op de gespecificeerde positie in deze lijst;
• remove(int index) Verwijdert het element dat op positie index staat;
• remove(Object o) Verwijdert de eerste keer dat ? o element uit deze lijst als het er is.
• remove() Haalt het eerste element van de lijst op en verwijdert het.

Implementatie van gekoppelde lijsten in Java, elementen toevoegen en verwijderen. Voorbeeld

Laten we deze bewerkingen uitproberen in de praktijk. Eerst Java LinkedList-implementatie: een LinkedList of Strings maken, daar 3 elementen aan toevoegen. Verwijder er vervolgens een en voeg er dan een in het midden toe.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Het resultaat van het uitvoeren van dit programma:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

Een LinkedList maakt deel uit van het Collection- framework, u kunt Iterator gebruiken om elementen te verwijderen, evenals een speciale iterator voor lijsten — ListIterator . Sterker nog, bewerkingen met iterator bieden de belangrijkste voordelen van de LinkedList- klasse: goede prestaties van invoeg-/verwijderbewerkingen. Als u Iterator gebruikt, krijgt u mogelijk een constante tijd voor hen. Later in dit artikel zullen we een codevoorbeeld schrijven om ArrayList en LinkedList+Iterator te vergelijken

• Iterator.remove() verwijdert het laatste element dat door deze iterator is geretourneerd.
• ListIterator.add(E element) voegt een element in de lijst in

Java LinkedList Voorbeeld: hoe Iterator werkt

Hier hebben we een kleine Java LinkedList- voorbeeldcode, waar we proberen toe te voegen en te verwijderen via Iterator.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

Het resultaat van het uitvoeren van dit programma:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

Meer Java LinkedList- bewerkingen:

• addFirst() , addLast() voeg een element toe aan het begin/einde van een lijst
• clear() verwijdert alle elementen uit de lijst
• bevat(Object o) retourneert true als de lijst het o-element bevat.
• indexOf(Object o) geeft de index terug van het eerste voorkomen van het element o, of -1 als het niet in de lijst staat.
• set(int index, E element) vervangt het element op de indexpositie door het element
• size()Retourneert het aantal elementen in de lijst.
• toArray() retourneert een array die alle elementen van de lijst bevat, van het eerste tot het laatste element.

Trouwens, omdat het een wachtrij van twee maten is, heeft LinkedList in Java stack-specifieke bewerkingen:

• pop() die een element uit de stapel haalt (weergegeven door de lijst)
• push(E e) dat een element op de stapel duwt (weergegeven door deze lijst)

Hoe LinkedList om te keren: voorbeeld

Hier is een klein voorbeeld, een populaire, maar toch gemakkelijke taak voor beginners. We hebben een LinkedList en zouden deze moeten omdraaien. Het eenvoudigste algoritme is om de LinkedList in omgekeerde volgorde te doorlopen en elk element in de nieuwe te plaatsen. Maar misschien vindt u een betere manier? Hier is de code van het Java-programma met omgekeerde gekoppelde lijst:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

Het resultaat:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList versus ArrayList: wanneer de eerste te gebruiken

Zowel LinkedList als ArrayList zijn implementaties van de List- interface. LinkedList implementeert het met een dubbel gekoppelde lijst. ArrayList implementeert het met behulp van een dynamisch wijzigende array. Zoals je al weet, bevat elk knooppunt van LinkedList Objecten en twee verwijzingen naar de buren. Dat betekent extra geheugenkosten voor het opslaan van referenties tussen elementen in het geval van Java LinkedList . ArrayList implementeert het met een dynamisch wijzigende array. Sommige bewerkingen van LinkedList en ArrayList zien er hetzelfde uit, maar ze werken op een andere manier. In de ArrayLijstgeval manipuleer je met interne arrays, in LinkedList - met referenties. ArrayList is de meest populaire List- implementatie. U moet zeker ArrayList gebruiken wanneer toegang tot de index een prioriteit is, aangezien deze bewerkingen in een constante tijd worden uitgevoerd. Gemiddeld toevoegen aan het einde van de lijst gebeurt ook in constante tijd. Sterker nog, ArrayList heeft geen extra kosten voor het opslaan van een heleboel elementen. U mag als nadelen meetellen voor de snelheid van invoegen en verwijderen als deze niet aan het einde van de lijst staat. Gelinkte lijstis op de een of andere manier nuttiger in het geval van de prestaties van invoeg- en verwijderbewerkingen: als u iterators gebruikt, gebeurt dit in een constante tijd. Toegangsbewerkingen per index worden uitgevoerd door te zoeken vanaf het begin van het einde (wat het dichtst bij is) naar het gewenste element. Vergeet echter niet de extra kosten voor het opslaan van referenties tussen elementen. Dus hier standaard LinkedList- en ArrayList- bewerkingen met algoritmische runtimes. N verwijst naar het aantal items dat al op de lijst staat. O(N) betekent dat we in het slechtste geval door de hele lijst moeten "lopen" totdat de benodigde positie is gevonden, bijvoorbeeld voor het invoegen van het nieuwe element in de lijst. O(1)betekent dat de bewerking in constante tijd plaatsvindt, onafhankelijk van het aantal items.

LinkedList Tijdcomplexiteit

ArrayList Tijdcomplexiteit

Wanneer LinkedList gebruiken: Voorbeeld

Absoluut, ArrayList is de meest populaire List- implementatie. U kunt echter situaties tegenkomen waarin de bewerkingen voor toevoegen/verwijderen te vaak nodig zijn. In dat geval zou LinkedList samen met Iterator nuttig kunnen zijn. Hier is een voorbeeld. We hebben een lange lijst en we zouden elk element van deze lijst moeten verwijderen. Laten we deze taak uitvoeren met ArrayList en LinkedList + Iterator . We vergelijken de tijd van elke bewerking en printen deze uit in de console. Hier de code:

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

Resultaat voor ArrayList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

Resultaat voor LinkedList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

Zoals u kunt zien, is LinkedList in dit geval veel effectiever. Laten we eerlijk zijn. In echte softwareontwikkeling is het gebruik van LinkedList een zeldzame gebeurtenis. Desalniettemin moet een professional op de hoogte zijn van het bestaan ​​van deze datastructuur en de voordelen ervan. Als LinkedList in echte code een zeldzame gast is, is hij op Java Junior-interviews erg populair. En toch, hier is wat Joshua Bloch schreef over LinkedList :

AddOn: enkelvoudig gekoppelde lijst Java

Er is geen enkelvoudig gekoppelde lijst onder de klassieke verzameling in Java, enkelvoudig gekoppelde lijst is een structuur waarin elk knooppunt een object bevat en een verwijzing naar het volgende knooppunt, maar niet voor het vorige. Java LinkedList is two-linked, maar niemand bemoeit zich met u om uw eigen datastructuur te creëren, zoals een Singly ,code>Linked List. Hier zijn enkele stappen om deze taken op te lossen:

1. Maak een Node- klasse met twee attributen, data en volgende. Next is een verwijzing naar het volgende knooppunt.
2. Maak de FirstLast- klasse met twee attributen, kop en staart.
3. Maak een methode add() om een ​​nieuw knooppunt aan de lijst toe te voegen. Controleer eerst of de lijst leeg is ( head == null ). Als dat zo is, verwijzen kop en staart naar het nieuwe knooppunt. Als de lijst niet leeg is, wordt het nieuwe knooppunt aan het einde toegevoegd, dus het volgende attribuut van de staart verwijst naar het toegevoegde knooppunt en het nieuwe knooppunt wordt het einde van de lijst.

Je kunt trouwens ook proberen om als oefening je eigen LinkedList te maken. Veel succes met leren.