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:
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:
transientint size =0;/**
* Pointer to first node.
*/transientNode<E> first;/**
* Pointer to last node.
*/transientNode<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 =newLinkedList<>();
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.
publicclassMyLinkedTest{publicstaticvoidmain(String[] args){String h1 ="my";String h2 ="favorite";String h3 ="book";// LinkedList implementation in JavaLinkedList<String> linkedList =newLinkedList();
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.
publicclassMyLinkedTest{publicstaticvoidmain(String[] args){String h1 ="my";String h2 ="favorite";String h3 ="book";LinkedList<String> linkedList =newLinkedList();
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:
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
LinkedList Java művelet
Algoritmikus hatékonyság
get(int index)
O(n) , átlagosan — n/4 lépés, ahol n a LinkedList mérete
add (E elem)
O(1)
add(int index, E elem)
O(n) , átlagosan – n/4 lépés; ha index = 0, akkor O(1) , tehát ha valamit hozzá kell adni a lista elejéhez, a LinkedList<E> jó választás lehet
eltávolítás (int index)
O(n) , átlagosan — n/4 lépés
Iterator.remove()
O(1) Ez a fő oka a LinkedList<E> használatának
ArrayList idő összetettsége
LinkedList művelet
Algoritmikus hatékonyság
get(int index)
O(1) , az ArrayList<E> használatának egyik fő oka
add (E elem)
O(n) a legrosszabb eset, mivel a tömböt át kell méretezni és át kell másolni, de a gyakorlatban nem olyan rossz
add(int index, E elem)
O(n) , n/2 lépés átlagosan
eltávolítás (int index)
O(n) , n/2 lépés átlagosan
Iterator.remove()
O(n) , n/2 lépés átlagosan
ListIterator.add(E elem)
O(n) , n/2 lépés átlagosan
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:
importjava.util.*;importjava.util.function.BiPredicate;publicclassListTest2{staticvoidremoveElements(List<Double> list,BiPredicate<Integer,Double> predicate){// start navigation from end to preserve indexes of removed itemsListIterator<Double> iterator = list.listIterator(list.size());while(iterator.hasPrevious()){Double element = iterator.previous();if(predicate.test(iterator.previousIndex()+1, element)){
iterator.remove();}}}staticclassTestCase1{publicstaticvoidmain(String[] args){LinkedList<Double> testedList1 =newLinkedList<>(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 =newArrayList<>(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);}}staticclassTestLinkedListPerformance{publicstaticvoidmain(String[] args){LinkedList<Double> testedList =newLinkedList<>();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);}}staticclassTestArrayListPerformance{publicstaticvoidmain(String[] args){ArrayList<Double> testedList =newArrayList<>();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);}}}
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:
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.
Hozzon létre FirstLast osztályt két attribútummal, a fejjel és a farokkal.
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.