Länkad listdatastruktur i Java

Olika datastrukturer skapas för olika ändamål. Du kanske känner till ArrayList (om fortfarande inte, rekommenderar vi att du läser om det först). I den här artikeln ska vi lära oss om LinkedList och inse vad den här samlingen är bra för. Om du tittar på LinkedList Java 8 (eller senare version av språkets) klasskodkälla (på Oracle-webbplatsen eller i din IDE, vid IDEA: crtl+B på klassnamnet) kommer du att se nästa deklaration:

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

För tillfället är den viktigaste informationen från koden det faktum att LinkedList implementerar List- och Deque -gränssnitt. Listgränssnittet behåller sekvensen för att lägga till objekt och tillåter åtkomst till objektet via index. Den "vanliga" kön stöder att lägga till element i slutet och extrahera dem från början. Deque är en tvåvägskö, och den stöder att lägga till och ta bort element från båda sidor. Du kanske tänker på det som en kombination av stack och kö. Så, LinkedList är en implementering av dessa två, och den tillåter oss att skapa en dubbelriktad kö som består av alla objekt inklusive null. Länkad listaär en samling av element. Vi kan se det i klassens kodkälla, den här gången var uppmärksam på fälten:

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

Varje element, vanligtvis kallade vi det Node , innehåller ett objekt och refererar till två angränsande objekt - det föregående och nästa. Därför är det inte särskilt effektivt när det gäller att använda minne. Eftersom LinkedList faktiskt är en dubbelriktad struktur, kan vi enkelt lägga till eller ta bort element från båda sidor.

LinkedList-konstruktörer

Tillbaka till kodkällan, vi kan ta reda på att LinkedList har två konstruktorer

• LinkedList() utan parametrar används för att konstruera en tom lista.
• >LinkedList(Collection<? utökar E> c) är till för att skapa en lista som innehåller elementen i den angivna samlingen, i ordningsföljd, de returneras av samlingens iterator.

LinkedList-deklaration

Faktum är att en länkad lista (Java eller på något annat språk) består av en sekvens av noder. Varje nod är utformad för att lagra ett objekt av en typ som definieras vid skapande. Så för att skapa LinkedList är Java-kod nästa:

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

Vi har ett syfte att behålla en sekvens av heltal och länkar till grannarna. Det är dock tomt för tillfället.

LinkedList Main Operations

Som vanligt, när det gäller samlingar kan du lägga in element i LinkedList (till slutet av den eller i mitten), ta bort därifrån och hämta ett element per index. Så här är de:

• add(E element) Lägger till det angivna elementet i slutet av denna lista;
• add(int index, E element) Infogar elementet vid det angivna positionsindexet ;
• get(int index) Returnerar elementet på den angivna positionen i denna lista;
• remove(int index) Tar bort elementet som är på positionsindex;
• remove(Object o) Tar bort den första förekomsten av ? o element från denna lista om det finns där.
• remove() Hämtar och tar bort det första elementet i listan.

Länkad listimplementering i Java, lägga till och ta bort element. Exempel

Låt oss pröva dessa operationer på övning. Först, Java LinkedList-implementering: skapa en LinkedList av strängar, lägga till 3 element. Ta sedan bort en och lägg sedan till en i mitten.

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 att köra detta 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 är en del av samlingsramverket , du kan använda Iterator för att ta bort element, samt en speciell iterator för listor — ListIterator . Ännu mer, operationer med iterator ger de viktigaste fördelarna med LinkedList -klassen: bra prestanda för insert/delete-operationer. Med Iterator kan du få en konstant tid för dem. Senare i den här artikeln kommer vi att skriva ett kodexempel för att jämföra ArrayList och LinkedList+Iterator

• Iterator.remove() tar bort det sista elementet som returneras av denna iterator.
• ListIterator.add(E-element) infogar ett element i listan

Java LinkedList Exempel: hur Iterator fungerar

Här har vi en liten Java LinkedList Exempelkod, där vi försöker lägga till och ta bort 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 att köra detta program:

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

Fler Java LinkedList- operationer:

• addFirst() , addLast() lägger till ett element i början/slutet av en lista
• clear() tar bort alla element från listan
• innehåller(Objekt o) returnerar sant om listan innehåller o-elementet.
• indexOf(Objekt o) returnerar indexet för den första förekomsten av elementet o, eller -1 om det inte finns i listan.
• set(int index, E element) ersätter elementet i indexposition med elementet
• size()Returnerar antalet element i listan.
• toArray() returnerar en array som innehåller alla listelement från första till sista elementet.

BTW är en tvåstor kö, LinkedList i Java har stackspecifika operationer:

• pop() som visar ett element från stacken (representeras av listan)
• push(E e) som skjuter in ett element på stacken (representeras av den här listan)

Hur man vänder LinkedList: exempel

Här är ett litet exempel, en populär men ändå enkel uppgift för nybörjare. Vi har en LinkedList och bör vända på den. Den enklaste algoritmen är att gå igenom LinkedList i omvänd ordning och lägga in alla element i den nya. Men du kanske hittar ett bättre sätt? Här är koden för java-programmet med omvänd länkad lista:

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 ska den första användas

Både LinkedList och ArrayList är implementeringar av List- gränssnittet. LinkedList implementerar det med en dubbellänkad lista. ArrayList implementerar det med en dynamisk storleksändringsarray. Som du redan vet innehåller varje nod i LinkedList objekt och två referenser till grannarna. Det innebär ytterligare minneskostnader för lagring av referenser mellan element i fallet med Java LinkedList . ArrayList implementerar det med en dynamisk storleksändringsarray. Vissa av LinkedList- och ArrayList -operationerna ser likadana ut, men de fungerar på ett annat sätt. I ArrayListfall, du manipulerar med interna arrayer, i LinkedList — med referenser. ArrayList är den mest populära listimplementeringen . Du bör definitivt använda ArrayList när indexåtkomst är en prioritet eftersom dessa operationer utförs i konstant tid. Att lägga till i slutet av listan i genomsnitt görs också i konstant tid. Ännu mer, ArrayList har inga extra kostnader för att lagra ett gäng element. Du kan räkna som Nackdelar hastigheten för insättning och borttagning när det inte görs i slutet av listan. Länkad listaär mer användbar i händelse av att infoga och ta bort operationer prestanda på vissa sätt: om du använder iteratorer det inträffar i konstant tid. Åtkomstoperationer genom index utförs genom att söka från början av slutet (beroende på vilket som är närmast) till det önskade elementet. Glöm dock inte extra kostnader för att lagra referenser mellan element. Så här standardoperationer för LinkedList och ArrayList med algoritmiska körtider. N hänvisar till antalet objekt som redan finns på listan. O(N) betyder att vi i värsta fall ska "gå" igenom hela listan tills den nödvändiga positionen hittas, till exempel för att infoga det nya elementet i listan. O(1)innebär att operationen sker i konstant tid, oberoende av antalet poster.

LinkedList Tidskomplexitet

ArrayList Tidskomplexitet

När ska man använda LinkedList: Exempel

ArrayList är definitivt den mest populära listimplementeringen . Du kan dock möta situationer när lägg till/ta bort operationer behövs för ofta. I så fall kan LinkedList tillsammans med Iterator vara fördelaktigt. Här är ett exempel. Vi har en lång lista och vi bör ta bort alla element från den här listan. Låt oss göra den här uppgiften med ArrayList och LinkedList + Iterator . Vi jämför tiden för varje operation och skriver ut den i konsolen. Här är 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 för ArrayList:

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

Resultat för LinkedList:

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

Som du kan se i det här fallet är LinkedList mycket mer effektivt. Låt oss vara ärliga. I verklig mjukvaruutveckling är LinkedList- användning en sorts sällsynt händelse. Ändå bör en professionell veta om denna datastruktur existens och dess fördelar. Om LinkedList i riktig kod är en sällsynt gäst, är det väldigt populärt på Java Junior-intervjuer. Och ändå, här är vad Joshua Bloch skrev om LinkedList :

Tillägg: Enbart länkad lista Java

Det finns ingen Singly Linked List bland klassisk samling i Java, Singly Linked List är en struktur där varje nod innehåller ett objekt och en referens till nästa nod, men inte för den föregående. Java LinkedList är tvålänkad, men ingen stör dig för att skapa din egen datastruktur, till exempel en Singly ,code>Linked List. Här är några steg för att lösa dessa uppgifter:

1. Skapa en nodklass med två attribut, data och nästa. Nästa är en referens till nästa nod.
2. Skapa FirstLast- klass med två attribut, huvud och svans.
3. Skapa en add() -metod för att lägga till en ny nod i listan. Kontrollera om listan är tom först ( head == null ). Om så är fallet hänvisar huvud och svans till den nya noden. Om listan inte är tom kommer den nya noden att läggas till i slutet, så nästa attribut i svansen refererar till den tillagda noden och den nya noden blir listans svans.

Förresten kan du försöka skapa din egen LinkedList som en övning också. Lycka till i ditt lärande.