Linked List Data Structure i Java

Forskellige datastrukturer skabes til forskellige formål. Du kender måske til ArrayList (hvis stadig ikke, anbefaler vi dig at læse om det først). I denne artikel skal vi lære om LinkedList og indse, hvad denne samling er god til. Hvis du ser på LinkedList Java 8 (eller nyere version af sproget) klassekodekilde (på Oracle-webstedet eller i din IDE, i tilfælde af IDEA: crtl+B på klassenavnet), vil du se den næste erklæring:

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

I øjeblikket er den vigtigste information fra koden det faktum, at LinkedList implementerer List og Deque- grænseflader. Listegrænsefladen bevarer rækkefølgen af ​​tilføjelse af elementer og giver adgang til elementet efter indeks. Den "almindelige" kø understøtter tilføjelse af elementer til slutningen og udtrækning af dem fra begyndelsen. Deque er en to-vejs kø, og den understøtter tilføjelse og fjernelse af elementer fra begge sider. Du kan tænke på det som en kombination af stak og kø. Så LinkedList er en implementering af disse to, og det giver os mulighed for at oprette en tovejskø bestående af alle objekter inklusive null. LinkedLister en samling af elementer. Vi kan se det i klassens kodekilde, denne gang skal du være opmærksom på felterne:

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

Hvert element, normalt kaldte vi det Node , indeholder et objekt og referencer til to naboobjekter - det forrige og det næste. Derfor er det ikke særlig effektivt med hensyn til at bruge hukommelse. Da LinkedList faktisk er en tovejsstruktur, kan vi nemt tilføje eller fjerne elementer fra begge sider.

LinkedList-konstruktører

Tilbage til kodekilden kan vi finde ud af, at LinkedList har to konstruktører

• LinkedList() uden parametre bruges til at konstruere en tom liste.
• >LinkedList(Collection<? udvider E> c) er til oprettelse af en liste, der indeholder elementerne i den specificerede samling, i rækkefølge, de returneres af samlingens iterator.

LinkedList-erklæring

Faktisk består en sammenkædet liste (Java eller på et hvilket som helst andet sprog) af en sekvens af noder. Hver node er designet til at gemme et objekt af en type defineret ved oprettelse. Så for at oprette LinkedList er Java-kode den næste:

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

Vi har et formål at holde en sekvens af heltal og links til naboerne. Det er dog tomt i øjeblikket.

LinkedList Hovedoperationer

Som sædvanlig kan du i tilfælde af samlinger lægge elementer ind i LinkedList (til slutningen af ​​den eller i midten), fjerne derfra og få et element efter indeks. Så her er de:

• add(E element) Tilføjer det angivne element til slutningen af ​​denne liste;
• add(int index, E element) Indsætter elementet ved det angivne positionsindeks ;
• get(int index) Returnerer elementet på den angivne position i denne liste;
• remove(int index) Fjerner det element, der er på positionsindeks;
• remove(Object o) Fjerner den første forekomst af ? o element fra denne liste, hvis det er der.
• remove() Henter og fjerner det første element på listen.

Linket listeimplementering i Java, tilføjelse og fjernelse af elementer. Eksempel

Lad os prøve disse operationer ud i praksis. Først Java LinkedList implementering: oprettelse af en LinkedList af strenge, tilføjelse af 3 elementer. Fjern derefter en, og tilføj derefter en i midten.

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);
   }

Resultatet af at køre dette program:

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]

En LinkedList er en del af samlingsrammen , du kan bruge Iterator til at fjerne elementer, såvel som en speciel iterator til lister — ListIterator . Endnu mere giver operationer med iterator de vigtigste fordele ved LinkedList- klassen: god ydeevne af indsæt/slet-operationer. Ved at bruge Iterator kan du få en konstant tid til dem. Senere i denne artikel skriver vi et kodeeksempel for at sammenligne ArrayList og LinkedList+Iterator

• Iterator.remove() fjerner det sidste element returneret af denne iterator.
• ListIterator.add(E element) indsætter et element i listen

Java LinkedList Eksempel: hvordan Iterator fungerer

Her har vi en lille Java LinkedList Eksempel kode, hvor vi forsøger at tilføje og slette 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);
 
   }
}

Resultatet af at køre dette program:

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

Flere Java LinkedList- operationer:

• addFirst() , addLast() tilføjer et element til begyndelsen/slutningen af ​​en liste
• clear() fjerner alle elementer fra listen
• indeholder(Objekt o) returnerer sand, hvis listen indeholder o-elementet.
• indexOf(Objekt o) returnerer indekset for den første forekomst af o-elementet, eller -1, hvis det ikke er på listen.
• set(int index, E element) erstatter elementet i indeksposition med elementet
• size()Returnerer antallet af elementer på listen.
• toArray() returnerer et array, der indeholder alle listens elementer fra det første til det sidste element.

BTW er en to-størrelse kø, LinkedList i Java har stak-specifikke operationer:

• pop() der viser et element fra stakken (repræsenteret af listen)
• push(E e) , der skubber et element ind på stakken (repræsenteret af denne liste)

Sådan vender du LinkedList: eksempel

Her er et lille eksempel, en populær, men alligevel nem opgave for begyndere. Vi har en LinkedList og bør vende den om. Den nemmeste algoritme er at gå gennem LinkedList i omvendt rækkefølge og lægge hvert element ind i det nye. Men måske vil du finde en bedre måde? Her er koden for java-program med omvendt linket liste:

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;
   }
}

Resultatet:

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

LinkedList vs ArrayList: hvornår skal den første bruges

Både LinkedList og ArrayList er implementeringer af List- grænsefladen. LinkedList implementerer det med en dobbelt-linket liste. ArrayList implementerer det ved hjælp af en dynamisk ændring af størrelse array. Som du allerede ved, indeholder hver knude i LinkedList objekter og to referencer til naboerne. Det betyder ekstra hukommelsesomkostninger til lagring af referencer mellem elementer i tilfældet med Java LinkedList . ArrayList implementerer det med en dynamisk ændring af størrelse array. Nogle af LinkedList og ArrayList operationer ser ens ud, men de fungerer på en anden måde. I ArrayListtilfælde, du manipulerer med interne arrays, i LinkedList - med referencer. ArrayList er den mest populære listeimplementering . Du bør helt sikkert bruge ArrayList, når indeksadgang er en prioritet, da disse operationer udføres konstant. Tilføjelse til slutningen af ​​listen i gennemsnit sker også i konstant tid. Endnu mere har ArrayList ikke ekstra omkostninger til at opbevare en masse elementer. Du kan tælle som Ulemper hastigheden af ​​indsættelse og fjernelse, når det ikke er gjort i slutningen af ​​listen. LinkedLister mere nyttigt i tilfælde af indsættelse og sletning af operationer på nogle måder: hvis du bruger iteratorer, sker det konstant. Adgangsoperationer efter indeks udføres ved at søge fra begyndelsen af ​​slutningen (alt efter hvad der er tættest på) til det ønskede element. Glem dog ikke ekstra omkostninger til lagring af referencer mellem elementer. Så her standard LinkedList og ArrayList operationer med algoritmiske runtimes. N henviser til antallet af elementer, der allerede er på listen. O(N) betyder, at vi i værste fald skal "gå" gennem hele listen, indtil den nødvendige position er fundet, for eksempel til indsættelse af det nye element i listen. O(1)betyder, at operationen sker i konstant tid, uafhængigt af antallet af varer.

LinkedList Tidskompleksitet

ArrayList Tidskompleksitet

Hvornår skal man bruge LinkedList: Eksempel

ArrayList er bestemt den mest populære listeimplementering . Du kan dog møde de situationer, hvor tilføjelse/fjern-handlingerne er nødvendige for ofte. I så fald kunne LinkedList sammen med Iterator være gavnligt. Her er et eksempel. Vi har en lang liste, og vi bør slette hvert element fra denne liste. Lad os udføre denne opgave med ArrayList og LinkedList + Iterator . Vi sammenligner tidspunktet for hver operation og printer det ud i konsollen. Her er koden:

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);
       }
   }
}

Resultat for ArrayList:

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

Resultat for LinkedList:

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

Som du kan se i dette tilfælde er LinkedList meget mere effektiv. Lad os være ærlige. I ægte softwareudvikling er brug af LinkedList en slags sjælden begivenhed. Ikke desto mindre bør en professionel kende til denne datastrukturs eksistens og dens fordele. Hvis LinkedList i ægte kode er en sjælden gæst, er det meget populært på Java Junior-interviews. Og alligevel, her er hvad Joshua Bloch skrev om LinkedList :

Tilføjelse: Enkeltforbundet liste Java

Der er ingen Singly Linked List blandt klassisk samling i Java, Singly Linked List er en struktur, hvor hver node indeholder et objekt og en reference til den næste node, men ikke for den forrige. Java LinkedList er to-linket, men ingen forstyrrer dig for at oprette din egen datastruktur, såsom en enkelt ,code>Linked List. Her er nogle trin til at løse disse opgaver:

1. Opret en node- klasse med to attributter, data og næste. Næste er en reference til den næste node.
2. Opret FirstLast klasse med to attributter, hoved og hale.
3. Opret en add()- metode for at tilføje en ny node til listen. Tjek først om listen er tom ( head == null ). Hvis ja, refererer hoved og hale til den nye knude. Hvis listen ikke er tom, vil den nye node blive tilføjet til slutningen, så den næste attribut i halen refererer til den tilføjede node, og den nye node bliver listens hale.

I øvrigt kan du prøve at oprette din egen LinkedList som en øvelse. Held og lykke med din læring.