Szia! Az összes legújabb leckét az ArrayListnek szentelték . Ez az adatstruktúra nagyon kényelmes és hasznos. Rengeteg feladatot elbír. De a Java sok más adatstruktúrával rendelkezik. Miért? Mindenekelőtt azért, mert a feladatok köre óriási, és a leghatékonyabb adatstruktúrák is eltérőek a különböző feladatokhoz. Ma egy új szerkezettel találkozunk: Java LinkedList , egy duplán linkelt lista.
![LinkedList – 1]()
Nézzük meg, hogyan szerveződik, miért hívják duplán linkeltnek, miben különbözik az ArrayListtől . A Java LinkedList elemei valójában egyetlen lánc linkjei. Az adatokon kívül minden elem hivatkozásokat tárol az előző és a következő elemekre. Ezek a hivatkozások lehetővé teszik, hogy egyik elemről a másikra léphessen. Így hozhat létre egyet:
![LinkedList – 2]()
Nézzük meg, hogyan adjunk hozzá új elemet. Ez az add() metódussal történik .
![LinkedList – 3]()
Ennek eredményeként az str2 és str1 összekapcsolódik a lista ezen csomópontjaiban tárolt következő és előző![LinkedList – 4]()
hivatkozásokon keresztül: Most meg kell értenie a duplán linkelt lista fő gondolatát. Pontosan ez a linklánc teszi a LinkedList elemeket egyetlen listává. Az ArrayListtel ellentétben a LinkedList nem tartalmaz tömböt vagy bármi tömbszerűt. Bármilyen (jó, a legtöbb) az ArrayListtel végzett munka a belső tömbbel való munkavégzésre vezethető vissza. Bármilyen munka a Java LinkedList- tela linkek megváltoztatásában merül ki. Ez nagyon jól látható, ha hozzáadunk egy elemet a lista közepéhez:
![LinkedList – 5]()
A belső hivatkozások megváltoztatása után az str2 sikeresen felkerült a listára: ![LinkedList – 6]()
Most mind a 3 elem csatlakoztatva van. A következő linken keresztül léphet a lánc első elemétől az utolsóig, majd vissza. Tehát elég kényelmesek vagyunk a beillesztéssel, de mi a helyzet az elemek eltávolításával? Az elv pontosan ugyanaz. Csak frissítjük a linkeket az eltávolítandó elemtől "balra és jobbra" lévő két elemben:
![LinkedList – 7]()
A hivatkozások frissítése után a kívánt eredményt kapjuk: Az ArrayList![LinkedList - 8]()
eltávolítási művelettel ellentétben itt nem kell eltolni a tömb elemeit, ill. bármi ilyesmi. Csak frissítjük az str1 és str3 hivatkozásait . Most egymásra mutatnak, és az str2 " kiesett " a linkek láncából, és már nem szerepel a listán.
public class Main {
public static void main(java.lang.String[] args) {
String str1 = new String("Hello World!");
String str2 = new String("My name is Earl");
String str3 = new String("I love Java");
String str4 = new String("I live in Canada");
LinkedList<String> earlBio = new LinkedList<>();
earlBio.add(str1);
earlBio.add(str2);
earlBio.add(str3);
earlBio.add(str4);
System.out.println(earlBio);
}
}
Nézzük meg, hogyan adjunk hozzá új elemet. Ez az add() metódussal történik .
earlBio.add(str2);
Ennek eredményeként az str2 és str1 összekapcsolódik a lista ezen csomópontjaiban tárolt következő és előző
hivatkozásokon keresztül: Most meg kell értenie a duplán linkelt lista fő gondolatát. Pontosan ez a linklánc teszi a LinkedList elemeket egyetlen listává. Az ArrayListtel ellentétben a LinkedList nem tartalmaz tömböt vagy bármi tömbszerűt. Bármilyen (jó, a legtöbb) az ArrayListtel végzett munka a belső tömbbel való munkavégzésre vezethető vissza. Bármilyen munka a Java LinkedList- tela linkek megváltoztatásában merül ki. Ez nagyon jól látható, ha hozzáadunk egy elemet a lista közepéhez:
public class Main {
public static void main(java.lang.String[] args) {
String str1 = new String("Hello World!");
String str2 = new String("My name is Earl");
String str3 = new String("I love Java");
String str4 = new String("I live in Canada");
LinkedList<String> earlBio = new LinkedList<>();
earlBio.add(str1);
earlBio.add(str3);
earlBio.add(1, str2);
System.out.println(earlBio);
}
}
A belső hivatkozások megváltoztatása után az str2 sikeresen felkerült a listára: 
Most mind a 3 elem csatlakoztatva van. A következő linken keresztül léphet a lánc első elemétől az utolsóig, majd vissza. Tehát elég kényelmesek vagyunk a beillesztéssel, de mi a helyzet az elemek eltávolításával? Az elv pontosan ugyanaz. Csak frissítjük a linkeket az eltávolítandó elemtől "balra és jobbra" lévő két elemben:
public class Main {
public static void main(java.lang.String[] args) {
String str1 = new String("Hello World!");
String str2 = new String("My name is Earl");
String str3 = new String("I love Java");
String str4 = new String("I live in Canada");
LinkedList<String> earlBio = new LinkedList<>();
earlBio.add(str1);
earlBio.add(str3);
earlBio.add(1, str2);
earlBio.remove(1);
System.out.println(earlBio);
}
}
A hivatkozások frissítése után a kívánt eredményt kapjuk: Az ArrayList
eltávolítási művelettel ellentétben itt nem kell eltolni a tömb elemeit, ill. bármi ilyesmi. Csak frissítjük az str1 és str3 hivatkozásait . Most egymásra mutatnak, és az str2 " kiesett " a linkek láncából, és már nem szerepel a listán.
A módszerek áttekintése
A LinkedListnek sok közös metódusa van az ArrayListtel . Például mindkét osztálynak vannak olyan metódusai, mint add() , remove() , indexOf() , clear() , include() (jelzi, hogy egy elem szerepel-e a listában), set() (egy meglévő elemet helyettesít), és méret () . Bár sok másképp működik belülről (ahogyan az add() és remove() esetén is tapasztaltuk ), a végeredmény ugyanaz. A LinkedListnek azonban külön módszerei vannak a lista elején és végén történő munkavégzéshez, amelyekkel az ArrayList nem rendelkezik:- addFirst() , addLast() : Ezek a módszerek egy elem hozzáadására a lista elejére/végére
public class Car {
String model;
public Car(String model) {
this.model = model;
}
public static void main(String[] args) {
LinkedList<Car> cars = new LinkedList<>();
Car ferrari = new Car("Ferrari 360 Spider");
Car bugatti = new Car("Bugatti Veyron");
Car lambo = new Car("Lamborghini Diablo");
Car ford = new Car("Ford Mondeo");
Car fiat = new Car("Fiat Ducato");
cars.add(ferrari);
cars.add(bugatti);
cars.add(lambo);
System.out.println(cars);
cars.addFirst(ford);
cars.addLast(fiat);
System.out.println(cars);
}
@Override
public String toString() {
return "Car{" +
"model='" + model + '\'' +
'}';
}
}
- peekFirst() , peekLast() : A metódusok a lista első/utolsó elemét adják vissza. Ha a lista üres, nullát adnak vissza .
public static void main(String[] args) {
LinkedList<Car> cars = new LinkedList<>();
Car ferrari = new Car("Ferrari 360 Spider");
Car bugatti = new Car("Bugatti Veyron");
Car lambo = new Car("Lamborghini Diablo");
cars.add(ferrari);
cars.add(bugatti);
cars.add(lambo);
System.out.println(cars.peekFirst());
System.out.println(cars.peekLast());
}
- pollFirst() , pollLast() : Ezek a metódusok a lista első/utolsó elemét adják vissza, és eltávolítják a listából. Ha a lista üres, nullát adnak vissza
public static void main(String[] args) {
LinkedList<Car> cars = new LinkedList<>();
Car ferrari = new Car("Ferrari 360 Spider");
Car bugatti = new Car("Bugatti Veyron");
Car lambo = new Car("Lamborghini Diablo");
cars.add(ferrari);
cars.add(bugatti);
cars.add(lambo);
System.out.println(cars.pollFirst());
System.out.println(cars.pollLast());
System.out.println ("What's on the list?");
System.out.println(cars);
}
- toArray() : Ez a metódus a listaelemeket tartalmazó tömböt adja vissza
public static void main(String[] args) {
LinkedList<Car> cars = new LinkedList<>();
Car ferrari = new Car("Ferrari 360 Spider");
Car bugatti = new Car("Bugatti Veyron");
Car lambo = new Car("Lamborghini Diablo");
cars.add(ferrari);
cars.add(bugatti);
cars.add(lambo);
Car[] carsArray = cars.toArray(new Car[3]);
System.out.println(Arrays.toString(carsArray));
}
- ellenőrizze, hogy van-e elég hely (behelyezéskor)
- ha nem, akkor létrehozunk egy új tömböt és oda másoljuk az adatokat (beszúráskor)
- eltávolítjuk/beszúrjuk az elemet, az összes többi elemet pedig jobbra/balra mozgatjuk (művelet típusától függően). És ennek a folyamatnak a bonyolultsága nagymértékben függ a lista méretétől. Egy dolog 10 elemet másolni/áthelyezni, és egészen más megtenni ugyanezt millió elemmel.
Elméletben
public class Main {
public static void main(String[] args) {
List<Integer> list = new LinkedList<>();
for (int i = 0; i < 5_000_000; i++) {
list.add(new Integer(i));
}
long start = System.currentTimeMillis();
for (int i = 0; i < 100; i++) {
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
}
System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
}
}
public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 5_000_000; i++) {
list.add(new Integer(i));
}
long start = System.currentTimeMillis();
for (int i = 0; i < 100; i++) {
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
}
System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
}
}
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
public class Main {
public static void main(String[] args) {
getTimeMsOfInsert(new ArrayList());
getTimeMsOfInsert(new LinkedList());
}
public static long getTimeMsOfInsert(List list) {
// Write your code here
Date currentTime = new Date();
insert1000000(list);
Date newTime = new Date();
long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
System.out.println("The result in milliseconds: " + msDelay);
return msDelay;
}
public static void insert1000000(List list) {
for (int i = 0; i < 1000000; i++) {
list.add(0, new Object());
}
}
}
- Egy adott gyűjtemény elméleti előnyei közül nem minden működik a valóságban (ezt láttuk a lista közepén lévő példánál)
- Ne foglaljon el szélsőséges álláspontot a gyűjtemény kiválasztásakor (" Az ArrayList mindig gyorsabb. Használja, és nem hibázhat. A LinkedList-et már régóta nem használja").
|
További olvasnivalók: |
|---|
GO TO FULL VERSION