Hi! Ang lahat ng pinakabagong mga aralin ay nakatuon sa ArrayList . Ang istraktura ng data na ito ay napaka-maginhawa at kapaki-pakinabang. Kaya nitong humawak ng maraming gawain. Ngunit ang Java ay may maraming iba pang mga istruktura ng data. Bakit? Higit sa lahat, dahil ang hanay ng mga gawain ay napakalaki, at ang pinakamahusay na istruktura ng data ay iba para sa iba't ibang gawain. Ngayon ay makakatagpo tayo ng bagong istraktura: Java LinkedList , isang dobleng naka-link na listahan.
Tingnan natin kung paano ito nakaayos, kung bakit ito tinatawag na double-linked, kung paano ito naiiba sa ArrayList . Ang mga elemento sa isang Java LinkedList ay talagang mga link sa iisang chain. Bilang karagdagan sa data, ang bawat elemento ay nag-iimbak ng mga sanggunian sa nakaraan at susunod na mga elemento. Hinahayaan ka ng mga reference na ito na lumipat mula sa isang elemento patungo sa isa pa. Ganito ka lumikha ng isa:
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);
}
}
Output: [Hello World! Ang pangalan ko ay Earl, mahal ko ang Java, nakatira ako sa Canada] Ganito ang hitsura ng aming listahan: Tingnan natin kung paano magdagdag ng bagong elemento. Ginagawa ito gamit ang add() na paraan.
earlBio.add(str2);
Sa punto sa code, ang aming listahan ay binubuo ng isang elemento: ang String str1 . Tingnan natin kung ano ang susunod na mangyayari sa larawan: Bilang resulta, ang str2 at str1 ay na-link sa pamamagitan ng susunod at nakaraang mga link na nakaimbak sa mga node na ito ng listahan: Ngayon ay dapat mong maunawaan ang pangunahing ideya ng isang dobleng naka-link na listahan. Ang hanay ng mga link na ito ay tiyak na ginagawang isang listahan ang mga elemento ng LinkList . Hindi tulad ng ArrayList , ang LinkedList ay walang array o anumang array-like sa loob. Anumang (mabuti, karamihan) na gumagana sa ArrayList ay bumababa sa pagtatrabaho sa panloob na hanay. Anumang gawain sa Java LinkedListbumababa sa pagbabago ng mga link. Malinaw itong makikita sa pamamagitan ng pagdaragdag ng elemento sa gitna ng listahan:
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);
}
}
Gaya ng nakikita mo, hinahayaan ka ng overloaded na paraan ng add() na tumukoy ng isang partikular na index para sa isang bagong item. Sa kasong ito, gusto naming magdagdag ng String str2 sa pagitan ng str1 at str3 . Ito ang mangyayari sa loob: Pagkatapos baguhin ang mga panloob na link, matagumpay na naidagdag ang str2 sa listahan: Ngayon lahat ng 3 elemento ay konektado. Maaari kang lumipat sa susunod na link mula sa unang elemento sa chain hanggang sa huli at pabalik muli. Kaya, medyo komportable kami sa pagpapasok, ngunit paano ang pag-alis ng mga elemento? Ang prinsipyo ay eksaktong pareho. Ina-update lang namin ang mga link sa dalawang elemento "sa kaliwa at kanan" ng elementong inaalis:
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);
}
}
Ganito ang mangyayari kung tatanggalin natin ang item na may index 1 (nasa gitna ito ng listahan): Pagkatapos i-update ang mga link, makukuha natin ang ninanais na resulta: Hindi tulad ng operasyon sa pagtanggal sa ArrayList , dito hindi na kailangang maglipat ng mga elemento ng array o gawin anumang uri. Ina-update lang namin ang mga link para sa str1 at str3 . Nakaturo na sila ngayon sa isa't isa, at ang str2 ay " bumaba " sa kadena ng mga link at hindi na bahagi ng listahan.
Pangkalahatang-ideya ng mga pamamaraan
Ang LinkList ay may maraming mga pamamaraan na karaniwan sa ArrayList . Halimbawa, ang parehong mga klase ay may mga pamamaraan tulad ng add() , remove() , indexOf() , clear() , contains() (nagsasaad kung ang isang item ay nasa listahan), set() (papalitan ang isang umiiral na elemento), at laki() . Bagama't marami sa kanila ang gumagana nang iba sa loob (tulad ng nakita namin sa add() at remove() ), pareho ang resulta. Gayunpaman, ang LinkedList ay may magkahiwalay na pamamaraan para sa pagtatrabaho sa simula at dulo ng listahan, na wala sa ArrayList :
addFirst() , addLast() : Ang mga pamamaraang ito para sa pagdaragdag ng elemento sa simula/tapos ng listahan
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 + '\'' +
'}';
}
}
Output: [Kotse{model='Ferrari 360 Spider'}, Kotse{model='Bugatti Veyron'}, Kotse{model='Lamborghini Diablo'}] [Kotse{model='Ford Mondeo'}, Kotse{model=' Ferrari 360 Spider'}, Kotse{model='Bugatti Veyron'}, Kotse{model='Lamborghini Diablo'}, Kotse{model='Fiat Ducato'}] Natapos namin ang "Ford" sa tuktok ng listahan , at "Fiat" sa dulo.
peekFirst() , peekLast() : Ibinabalik ng mga pamamaraan ang una/huling elemento sa listahan. Ibinabalik nila ang null kung walang laman ang listahan.
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() : Ibinabalik ng mga pamamaraang ito ang una/huling elemento sa listahan at alisin ito sa listahan. Ibinabalik nila ang null kung walang laman ang listahan
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);
}
Output: Kotse{model='Ferrari 360 Spider'} Kotse{model='Lamborghini Diablo'} Ano ang natitira sa listahan? [Kotse{model='Bugatti Veyron'}]
toArray() : Ang pamamaraang ito ay nagbabalik ng array na naglalaman ng mga item sa listahan
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));
}
Output: [Kotse{model='Ferrari 360 Spider'}, Kotse{model='Bugatti Veyron'}, Kotse{model='Lamborghini Diablo'}] Ngayon alam na natin kung paano gumagana ang LinkedList at kung paano naiiba ang organisasyon nito sa ArrayList . Ano ang mga pakinabang ng paggamit ng LinkList ? Higit sa lahat, nakikinabang tayo kapag nagtatrabaho sa gitna ng listahan. Ang mga pagpapatakbo ng pagpasok at pagtanggal sa gitna ng isang LinkedList ay mas simple kaysa sa isang ArrayList . Ina-update lang namin ang mga link ng mga kalapit na elemento, at ang hindi gustong elemento ay "bumababa" sa kadena ng mga link. Ngunit sa isang ArrayList , kailangan natin
suriin kung may sapat na espasyo (kapag ipinapasok)
kung hindi, pagkatapos ay lumikha kami ng isang bagong array at kopyahin ang data doon (kapag ipinasok)
inaalis/ipasok natin ang elemento, at inililipat ang lahat ng iba pang elemento sa kanan/kaliwa (depende sa uri ng operasyon). At ang pagiging kumplikado ng prosesong ito ay lubos na nakasalalay sa laki ng listahan. Isang bagay ang kopyahin/ilipat ang 10 elemento, at isa pa ang gawin ang parehong sa isang milyong elemento.
Sa madaling salita, kung ang mga pagpapatakbo ng pagpapasok/pag-alis sa gitna ng listahan ay pinakakaraniwan sa iyong programa, ang LinkList ay dapat na mas mabilis kaysa sa ArrayList .
Sa teorya
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));
}
}
Output: Oras na kinuha ng LinkedList (sa millisecond) = 1873
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));
}
}
Output: Oras na kinuha ng ArrayList (sa millisecond) = 181 Iyon ay hindi inaasahan! Nagsagawa kami ng operasyon kung saan dapat maging mas mahusay ang LinkedList : paglalagay ng 100 item sa gitna ng isang listahan. At napakalaki ng aming listahan: 5,000,000 elemento. Kinailangan ng ArrayList na maglipat ng ilang milyong item sa bawat pagpapasok! Paano ito nanalo? Una, ang oras na kinakailangan para sa ArrayList upang ma-access ang mga elemento ay naayos (pare-pareho). Kapag sumulat ka
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
pagkatapos ArrayList [2_000_000] ay isang tiyak na memory address (pagkatapos ng lahat, ang listahan ay may panloob na array). Ngunit, ang isang LinkList ay walang array. Hahanapin nito ang numero ng elemento 2_000_000 kasama ang chain ng mga link. Para sa LinkedList, hindi ito memory address, ngunit isang link na kailangan pa ring maabot: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next……… Bilang resulta, sa bawat pagpasok (pag-alis) sa gitna ng listahan , alam na ng ArrayList ang eksaktong memory address na maa-access, ngunit kailangan pa rin ng LinkedList na "makapunta doon". Pangalawa, mayroong istraktura ng ArrayListmismo. Ang isang espesyal na panloob na function ( System.arrayCopy() ) ay nagpapalawak ng panloob na array, at kinokopya at inililipat ang lahat ng elemento. Ito ay napakabilis, dahil ito ay na-optimize para sa partikular na gawaing ito. Ngunit kapag hindi mo na kailangang "makapunta sa" isang partikular na index, ang LinkList ang panalo. Ipagpalagay na ipasok namin sa pinakadulo simula ng listahan. Subukan nating magpasok ng isang milyong elemento doon:
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());
}
}
}
Output: Ang resulta sa millisecond: 43448 Ang resulta sa milliseconds: 107 Ngayon ay nakakuha kami ng isang ganap na kakaibang resulta! Ang ArrayList ay gumugol ng higit sa 43 segundo sa pagpasok ng isang milyong item sa unahan ng listahan, habang nagawa ito ng LinkList sa loob ng 0.1 segundo! Nakinabang ang LinkedList dito, dahil hindi nito kailangang tumakbo sa hanay ng mga link sa gitna ng listahan sa bawat oras. Hinahanap agad nito ang kinakailangang index sa simula ng listahan, kaya isang kalamangan na ang ibang algorithm. :) Sa katunayan, ang talakayan ng " ArrayList versus LinkedList " ay napakalawak, at hindi namin ito susuriin nang malalim sa kasalukuyang antas. Ang pangunahing bagay na kailangan mong tandaan ay ito:
Hindi lahat ng teoretikal na bentahe ng anumang partikular na koleksyon ay palaging gumagana sa katotohanan (nakita namin ito kasama ang halimbawang kinasasangkutan ng gitna ng listahan)
Huwag gumamit ng isang matinding posisyon pagdating sa pagpili ng isang koleksyon (" ArrayList ay palaging mas mabilis. Gamitin ito at hindi ka maaaring magkamali. Walang sinuman ang gumagamit ng LinkedList sa mahabang panahon").
Bagama't kahit na ang may-akda ng LinkList na si Joshua Bloch, ay nagsabi na ito ang kaso. :) Gayunpaman, ang pananaw na ito ay malayo sa 100% tama, at nakumbinsi namin ang aming sarili tungkol dito. Sa aming nakaraang halimbawa, ang LinkList ay 400 (!) beses na mas mabilis. Ang isa pang bagay ay mayroon talagang ilang mga sitwasyon kung saan ang LinkList ay ang pinakamahusay na pagpipilian. Ngunit umiiral ang mga ito, at sa tamang sandali LinkListmakakaganti sayo ng maganda. Huwag kalimutan ang sinabi namin sa simula ng aralin: ang pinakamabisang istruktura ng data ay iba para sa iba't ibang gawain. Imposibleng maging 100% sigurado kung aling istraktura ng data ang magiging pinakamahusay hanggang sa malaman mo ang lahat ng mga kondisyon ng iyong gawain. Malalaman mo ang higit pa tungkol sa mga koleksyong ito sa ibang pagkakataon, na magpapadali sa pagpili. Ngunit ang pinakasimple at pinakaepektibong opsyon ay palaging pareho: subukan ang pareho sa aktwal na data na ginamit sa iyong programa. Pagkatapos ay makikita mo sa iyong sarili kung paano gumaganap ang parehong uri ng mga listahan at tiyak na hindi ka magkakamali. :) Upang palakasin ang iyong natutunan, iminumungkahi naming manood ka ng isang video lesson mula sa aming Java Course
Tingnan natin kung paano magdagdag ng bagong elemento. Ginagawa ito gamit ang add() na paraan.
Bilang resulta, ang str2 at str1 ay na-link sa pamamagitan ng susunod at nakaraang mga link na nakaimbak sa mga node na ito ng listahan: 
Ngayon ay dapat mong maunawaan ang pangunahing ideya ng isang dobleng naka-link na listahan. Ang hanay ng mga link na ito ay tiyak na ginagawang isang listahan ang mga elemento ng LinkList . Hindi tulad ng ArrayList , ang LinkedList ay walang array o anumang array-like sa loob. Anumang (mabuti, karamihan) na gumagana sa ArrayList ay bumababa sa pagtatrabaho sa panloob na hanay. Anumang gawain sa Java LinkedListbumababa sa pagbabago ng mga link. Malinaw itong makikita sa pamamagitan ng pagdaragdag ng elemento sa gitna ng listahan:
Pagkatapos baguhin ang mga panloob na link, matagumpay na naidagdag ang str2 sa listahan: 
Ngayon lahat ng 3 elemento ay konektado. Maaari kang lumipat sa susunod na link mula sa unang elemento sa chain hanggang sa huli at pabalik muli. Kaya, medyo komportable kami sa pagpapasok, ngunit paano ang pag-alis ng mga elemento? Ang prinsipyo ay eksaktong pareho. Ina-update lang namin ang mga link sa dalawang elemento "sa kaliwa at kanan" ng elementong inaalis:
Pagkatapos i-update ang mga link, makukuha natin ang ninanais na resulta: 
Hindi tulad ng operasyon sa pagtanggal sa ArrayList , dito hindi na kailangang maglipat ng mga elemento ng array o gawin anumang uri. Ina-update lang namin ang mga link para sa str1 at str3 . Nakaturo na sila ngayon sa isa't isa, at ang str2 ay " bumaba " sa kadena ng mga link at hindi na bahagi ng listahan.
GO TO FULL VERSION