Linked List Data Structure Java nyelven

Különböző célokra különböző adatstruktúrák jönnek létre. Lehet, hogy ismeri az ArrayList-et (ha még mindig nem, javasoljuk, hogy először olvasson róla). Ebben a cikkben megismerjük a LinkedList-et , és megtudjuk, mire jó ez a gyűjtemény. Ha belenéz a LinkedList Java 8 (vagy a nyelv újabb verziója) osztálykódforrásába (az Oracle webhelyén vagy az IDE-ben, IDEA esetén: crtl+B az osztálynéven), a következő deklarációt fogja látni:

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

A kódból jelenleg az a legfontosabb információ, hogy a LinkedList List és Deque felületeket valósít meg . A Lista felület megtartja az elemek hozzáadásának sorrendjét, és lehetővé teszi az elemekhez való hozzáférést indexenként. A „hétköznapi” sor támogatja az elemek hozzáadását a végéhez, és az elejétől való kibontását. A Deque egy kétirányú várólista, amely mindkét oldalról támogatja az elemek hozzáadását és eltávolítását. Úgy gondolhatja, mint a verem és a sor kombinációja. Tehát a LinkedList ennek a kettőnek a megvalósítása, és lehetővé teszi számunkra, hogy kétirányú sort hozzunk létre, amely bármilyen objektumból áll, beleértve a nullát is. LinkedListelemek gyűjteménye. Az osztály kódforrásában láthatjuk, ezúttal figyeljünk a mezőkre:

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

Minden elem, amelyet általában Csomópontnak hívunk , tartalmaz egy objektumot, és két szomszédos objektumra – az előzőre és a következőre – hivatkozik. Ezért a memóriahasználat szempontjából nem túl hatékony. Mivel a LinkedList valójában egy kétirányú struktúra, könnyen hozzáadhatunk vagy eltávolíthatunk elemeket mindkét oldalról.

LinkedList konstruktorok

Visszatérve a kódforráshoz, megtudhatjuk, hogy a LinkedListnek két konstruktora van

• A paraméterek nélküli LinkedList() egy üres lista létrehozására szolgál.
• A >LinkedList(Collection<? extends E> c) a megadott gyűjtemény elemeit tartalmazó lista létrehozására szolgál, sorrendben, azokat a gyűjtemény iterátora adja vissza.

LinkedList nyilatkozat

Valójában egy linkelt lista (Java vagy bármely más nyelven) csomópontok sorozatából áll. Minden csomópont úgy van kialakítva, hogy a létrehozáskor meghatározott típusú objektumot tárolja. Tehát a LinkedList létrehozásához a Java kód a következő:

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

Van egy objektum, amely egész számokból álló sorozatot és a szomszédokhoz mutató hivatkozásokat tart fenn. Jelenleg azonban üres.

LinkedList fő műveletek

Szokás szerint a Gyűjtemények esetében a LinkedList- be helyezhetünk elemeket (annak végére vagy közepére), onnan távolíthatunk el, és indexenként kaphatunk egy elemet. Szóval itt vannak:

• add(E elem) A megadott elemet hozzáfűzi a lista végéhez;
• add(int index, E elem) Beszúrja az elemet a megadott pozícióindexbe ;
• get(int index) A listában a megadott helyen lévő elemet adja vissza;
• remove(int index) Eltávolítja a pozícióindexen lévő elemet;
• remove(Object o) Eltávolítja a ? o elemet ebből a listából, ha ott van.
• remove() Lekéri és eltávolítja a lista első elemét.

Linkelt lista megvalósítása Java nyelven, elemek hozzáadása és eltávolítása. Példa

Próbáljuk ki ezeket a műveleteket a gyakorlatban. Először is, Java LinkedList megvalósítás: hozzon létre egy LinkedList of Strings listát, és adjon hozzá 3 elemet. Ezután vegyen ki egyet, majd tegyen egyet a közepébe.

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

A program futtatásának eredménye:

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]

A LinkedList a Gyűjtemény keretrendszer része , használhatja az Iteratort elemek eltávolítására, valamint egy speciális iterátort a listákhoz – ListIterator . Sőt, az iterátorral végzett műveletek biztosítják a LinkedList osztály fő előnyeit: a beszúrási/törlési műveletek jó teljesítményét. Az Iterator használatával állandó időt kaphat rájuk. A cikk későbbi részében egy kódpéldát írunk az ArrayList és a LinkedList+Iterator összehasonlításához

• Az Iterator.remove() eltávolítja az iterátor által visszaadott utolsó elemet.
• A ListIterator.add(E elem) beszúr egy elemet a listába

Java LinkedList Példa: hogyan működik az Iterator

Itt van egy kis Java LinkedList példakód, ahol megpróbáljuk hozzáadni és törölni az Iteratoron keresztül.

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

A program futtatásának eredménye:

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

További Java LinkedList műveletek:

• addFirst() , addLast() elemet ad a lista elejére/végére
• clear() eltávolítja az összes elemet a listából
• A include(Object o) igaz értéket ad vissza, ha a lista tartalmazza az o elemet.
• Az indexOf(Object o) az o elem első előfordulásának indexét adja vissza, vagy -1-et, ha az nem szerepel a listában.
• set(int index, E elem) lecseréli az index pozícióban lévő elemet az elemre
• size() A lista elemeinek mennyiségét adja vissza.
• A toArray() egy tömböt ad vissza, amely a lista összes elemét tartalmazza az elsőtől az utolsó elemig.

Mivel a BTW egy két méretű várólista, a Java LinkedList- ben veremspecifikus műveletek vannak:

• pop() , amely kidob egy elemet a veremből (amelyet a lista képvisel)
• push(E e) , amely egy elemet a verembe tol (ez a lista képviseli)

A LinkedList visszafordítása: példa

Íme egy kis példa, népszerű, mégis könnyű feladat kezdőknek. Van egy LinkedListünk , és meg kell fordítanunk. A legegyszerűbb algoritmus az, ha fordított sorrendben végigmegyünk a LinkedList-en , és minden elemet az újba helyezünk. Azonban talán találsz jobb módszert? Íme a fordított linkelt listás java program kódja:

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

Az eredmény:

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

LinkedList vs ArrayList: mikor kell használni az elsőt

Mind a LinkedList , mind az ArrayList a List felület implementációi . A LinkedList duplán linkelt listával valósítja meg. Az ArrayList dinamikusan átméretező tömb segítségével valósítja meg. Mint már tudja, a LinkedList minden csomópontja tartalmaz objektumokat és két hivatkozást a szomszédokra. Ez további memóriaköltséget jelent az elemek közötti hivatkozások tárolására a Java LinkedList esetében . Az ArrayList dinamikusan átméretező tömbbel valósítja meg. Néhány LinkedList és ArrayList művelet ugyanúgy néz ki, de eltérő módon működnek. Az ArrayListbenaz esetet belső tömbökkel, a LinkedListben pedig hivatkozásokkal kezelheti . Az ArrayList a legnépszerűbb lista megvalósítás. Mindenképpen érdemes az ArrayList-et használni , ha az indexelérés prioritást élvez, mivel ezeket a műveleteket állandó időben hajtják végre. A lista végére való felvétel átlagosan szintén állandó időben történik. Sőt, az ArrayListnek nincs többletköltsége egy csomó elem tárolásáért. Hátránynak számíthat a beillesztési és eltávolítási műveletek sebessége, ha az nem a lista végén történik. LinkedListA beszúrási és törlési műveletek teljesítménye esetén bizonyos szempontból hasznosabb: ha iterátorokat használunk, az állandó időben történik. Az index szerinti hozzáférési műveletek végrehajtása a végétől (amelyik közelebb van) a kívánt elemhez keresve. Ne feledkezzünk meg azonban az elemek közötti hivatkozások tárolásának többletköltségeiről sem. Tehát itt szabványos LinkedList és ArrayList műveletek algoritmikus futásidővel. Az N a listán már szereplő elemek számát jelenti. Az O(N) azt jelenti, hogy a legrosszabb esetben a teljes listát végig kell „járnunk”, amíg meg nem találjuk a kívánt pozíciót, például az új elem beillesztéséhez a listába. O(1)azt jelenti, hogy a művelet állandó időben történik, az elemek számától függetlenül.

LinkedList idő összetettsége

ArrayList idő összetettsége

Mikor kell használni a LinkedList-et: Példa

Kétségtelenül az ArrayList a legnépszerűbb List megvalósítás. Azonban előfordulhatnak olyan helyzetek, amikor túl gyakran van szükség az add/remove műveletekre. Ebben az esetben a LinkedList az Iteratorral együtt hasznos lehet. Íme egy példa. Hosszú listánk van, és minden elemet törölnünk kell ebből a listából. Végezzük el ezt a feladatot az ArrayList és a LinkedList + Iterator segítségével . Minden művelet idejét összehasonlítjuk és kinyomtatjuk a konzolra. Itt a kód:

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

Az ArrayList eredménye:

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

A LinkedList eredménye:

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

Mint látható ebben az esetben a LinkedList sokkal hatékonyabb. Legyünk őszinték. A valódi szoftverfejlesztésben a LinkedList használata ritka esemény. Ennek az adatszerkezetnek a létezéséről és előnyeiről azonban szakembernek tudnia kell. Ha valós kódban a LinkedList ritka vendég, a Java Junior interjúkon nagyon népszerű. És mégis, íme, amit Joshua Bloch írt a LinkedListről :

AddOn: Singly Linked List Java

A Java klasszikus gyűjteményében nincs Singly Linked List , a Singly Linked List egy olyan struktúra, amelyben minden csomópont tartalmaz egy objektumot és egy hivatkozást a következő csomópontra, de nem az előzőre. A Java LinkedList kétlinkes, de senki sem zavarja meg saját adatszerkezetének létrehozását, például egy Singly ,code>Linked List. Íme néhány lépés a feladatok megoldásához:

1. Hozzon létre egy Node osztályt két attribútummal, adatokkal és next. A következő egy hivatkozás a következő csomópontra.
2. Hozzon létre FirstLast osztályt két attribútummal, a fejjel és a farokkal.
3. Hozzon létre egy add() metódust egy új csomópont hozzáadásához a listához. Először ellenőrizze, hogy a lista üres-e ( fej == null ). Ha igen, a fej és a farok az új csomópontra utal. Ha a lista nem üres, az új csomópont a végére kerül, így a farok következő attribútuma a hozzáadott csomópontra vonatkozik, és az új csomópont lesz a lista farka.

Egyébként gyakorlatként megpróbálhatod létrehozni saját LinkedList- edet is. Sok sikert a tanuláshoz.