Koblet listedatastruktur i Java

Ulike datastrukturer lages for ulike formål. Du kjenner kanskje til ArrayList (hvis fortsatt ikke, anbefaler vi deg å lese om det først). I denne artikkelen skal vi lære om LinkedList og innse hva denne samlingen er god for. Hvis du ser på LinkedList Java 8 (eller nyere versjon av språket) klassekodekilde (på Oracle-nettstedet eller i IDE-en din, i tilfelle IDEA: crtl+B på klassenavnet) vil du se neste erklæring:

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

For øyeblikket er den viktigste informasjonen fra koden det faktum at LinkedList implementerer List og Deque -grensesnitt. Liste-grensesnittet beholder sekvensen for å legge til elementer og gir tilgang til elementet etter indeks. Den "vanlige" køen støtter å legge til elementer til slutten og trekke dem ut fra begynnelsen. Deque er en toveiskø, og den støtter å legge til og fjerne elementer fra begge sider. Du kan tenke på det som en kombinasjon av stabel og kø. Så, LinkedList er en implementering av disse to, og den lar oss lage en toveis kø bestående av alle objekter inkludert null. LinkedLister en samling av elementer. Vi kan se det i kodekilden til klassen, denne gangen ta hensyn til feltene:

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

Hvert element, vanligvis kalte vi det Node , inneholder et objekt og referanser til to naboobjekter - det forrige og det neste. Derfor er det ikke veldig effektivt når det gjelder bruk av minne. Siden LinkedList faktisk er en toveis struktur, kan vi enkelt legge til eller fjerne elementer fra begge sider.

LinkedList-konstruktører

Tilbake til kodekilden kan vi finne ut at LinkedList har to konstruktører

• LinkedList() uten parametere brukes til å konstruere en tom liste.
• >LinkedList(Collection<? utvider E> c) er for å lage en liste som inneholder elementene i den spesifiserte samlingen, i rekkefølge at de returneres av samlingens iterator.

LinkedList-erklæring

Faktisk består en koblet liste (Java eller på et annet språk) av en sekvens av noder. Hver node er designet for å lagre et objekt av en type som er definert når du oppretter. Så for å lage LinkedList er Java-kode den neste:

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

Vi har et formål å holde en sekvens av heltall og lenker til naboene. Det er imidlertid tomt for øyeblikket.

LinkedList Hovedoperasjoner

Som vanlig, når det gjelder samlinger, kan du legge elementer inn i LinkedList (til slutten av den eller i midten), fjerne derfra og få et element etter indeks. Så her er de:

• add(E element) Legger til det spesifiserte elementet på slutten av denne listen;
• add(int index, E element) Setter inn elementet på den angitte posisjonsindeksen ;
• get(int index) Returnerer elementet på den angitte posisjonen i denne listen;
• remove(int index) Fjerner elementet som er på posisjonsindeks;
• remove(Object o) Fjerner den første forekomsten av ? o element fra denne listen hvis det er der.
• remove() Henter og fjerner det første elementet i listen.

Koblet listeimplementering i Java, legge til og fjerne elementer. Eksempel

La oss prøve disse operasjonene i praksis. Først, Java LinkedList-implementering: lage en LinkedList of Strings, og legge til 3 elementer. Fjern deretter en, og legg deretter til 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 av å kjøre dette programmet:

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 av samlingsrammeverket , du kan bruke Iterator for å fjerne elementer, samt en spesiell iterator for lister — ListIterator . Enda mer, operasjoner med iterator gir hovedfordelene med LinkedList- klassen: god ytelse av inn-/slettoperasjoner. Ved å bruke Iterator kan du få en konstant tid for dem. Senere i denne artikkelen vil vi skrive et kodeeksempel for å sammenligne ArrayList og LinkedList+Iterator

• Iterator.remove() fjerner det siste elementet returnert av denne iteratoren.
• ListIterator.add(E-element) setter inn et element i listen

Java LinkedList Eksempel: hvordan Iterator fungerer

Her har vi en liten Java LinkedList Eksempel-kode, hvor vi prøver å legge til 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 av å kjøre dette programmet:

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

Flere Java LinkedList- operasjoner:

• addFirst() , addLast() legger til et element i begynnelsen/slutten av en liste
• clear() fjerner alle elementer fra listen
• inneholder(Objekt o) returnerer sann hvis listen inneholder o-elementet.
• indeksOf(Objekt o) returnerer indeksen for den første forekomsten av o-elementet, eller -1 hvis det ikke er i listen.
• set(int index, E element) erstatter elementet i indeksposisjon med elementet
• size()Returnerer antallet elementer i listen.
• toArray() returnerer en matrise som inneholder alle listens elementer fra første til siste element.

Forresten, som en kø i to størrelser, har LinkedList i Java stabelspesifikke operasjoner:

• pop() som spretter et element fra stabelen (representert av listen)
• push(E e) som skyver et element inn på stabelen (representert av denne listen)

Hvordan reversere LinkedList: eksempel

Her er et lite eksempel, en populær, men likevel enkel oppgave for nybegynnere. Vi har en LinkedList og bør reversere den. Den enkleste algoritmen er å gå gjennom LinkedList i omvendt rekkefølge og legge hvert element inn i det nye. Men kanskje du finner en bedre måte? Her er koden til java-programmet med omvendt lenket 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: når du skal bruke den første

Både LinkedList og ArrayList er implementeringer av List- grensesnittet. LinkedList implementerer det med en dobbeltlenket liste. ArrayList implementerer det ved å bruke en dynamisk størrelsesrekke. Som du allerede vet, inneholder hver node i LinkedList objekter og to referanser til naboene. Det betyr ekstra minnekostnader for lagring av referanser mellom elementer i tilfellet med Java LinkedList . ArrayList implementerer det med en dynamisk størrelsesreduksjon. Noen av LinkedList- og ArrayList -operasjonene ser like ut, men de fungerer på en annen måte. I ArrayListtilfelle, du manipulerer med interne arrays, i LinkedList - med referanser. ArrayList er den mest populære listeimplementeringen . Du bør definitivt bruke ArrayList når indekstilgang er en prioritet siden disse operasjonene utføres i konstant tid. Legging til slutten av listen i gjennomsnitt gjøres også i konstant tid. Enda mer, ArrayList har ikke ekstra kostnader for å lagre en haug med elementer. Du kan telle som negativ hastigheten på innsetting og fjerning når det ikke er gjort på slutten av listen. LinkedLister mer nyttig i tilfelle av innsetting og sletting operasjoner ytelse på noen måter: hvis du bruker iteratorer det skjer i konstant tid. Tilgangsoperasjoner etter indeks utføres ved å søke fra begynnelsen av slutten (det som er nærmest) til ønsket element. Men ikke glem ekstra kostnader for lagring av referanser mellom elementer. Så her standard LinkedList og ArrayList operasjoner med algoritmiske kjøretider. N refererer til antall elementer som allerede er på listen. O(N) betyr at vi i verste fall bør "gå" gjennom hele listen til den nødvendige posisjonen er funnet, for eksempel for innsetting av det nye elementet i listen. O(1)betyr at operasjonen skjer i konstant tid, uavhengig av antall varer.

LinkedList-tidskompleksitet

ArrayList Tidskompleksitet

Når du skal bruke LinkedList: Eksempel

ArrayList er definitivt den mest populære listeimplementeringen . Du kan imidlertid møte situasjoner når legg til/fjern-operasjoner er nødvendig for ofte. I så fall kan LinkedList sammen med Iterator være fordelaktig. Her er et eksempel. Vi har en lang liste, og vi bør slette hvert element fra denne listen. La oss gjøre denne oppgaven med ArrayList og LinkedList + Iterator . Vi sammenligner tidspunktet for hver operasjon og skriver det ut 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 tilfellet er LinkedList mye mer effektivt. La oss være ærlige. I ekte programvareutvikling er LinkedList- bruk en slags sjelden hendelse. Likevel bør en profesjonell vite om denne datastrukturens eksistens og dens fordeler. Hvis LinkedList i ekte kode er en sjelden gjest, er det veldig populært på Java Junior-intervjuer. Og likevel, her er hva Joshua Bloch skrev om LinkedList :

AddOn: Enkeltkoblet liste Java

Det er ingen Singly Linked List blant klassisk samling i Java, Singly Linked List er en struktur der hver node inneholder et objekt og en referanse til neste node, men ikke for den forrige. Java LinkedList er to-lenket, men ingen forstyrrer deg for å lage din egen datastruktur, for eksempel en Singly ,code>Linked List. Her er noen trinn for å løse disse oppgavene:

1. Lag en nodeklasse med to attributter, data og neste. Neste er en referanse til neste node.
2. Lag FirstLast- klassen med to attributter, hode og hale.
3. Opprett en add()- metode for å legge til en ny node i listen. Sjekk om listen er tom først ( head == null ). I så fall refererer hode og hale til den nye noden. Hvis listen ikke er tom, vil den nye noden legges til på slutten, så neste attributt til halen refererer til den lagte noden og den nye noden blir halen på listen.

Du kan forresten prøve å lage din egen LinkedList som en øvelse også. Lykke til i læringen.