LinkedList sa Java

Kamusta! Ang lahat ng kamakailang mga lektura ay nakatuon sa pag-aaral sa listahan ng ArrayList . Ang istraktura ng data na ito ay napaka-maginhawa at nagbibigay-daan sa iyo upang malutas ang maraming mga problema. Gayunpaman, ang Java ay may maraming iba pang mga istruktura ng data. Bakit? Una sa lahat, dahil ang hanay ng mga kasalukuyang gawain ay napakalawak, at para sa iba't ibang mga gawain iba't ibang mga istruktura ng data ang pinaka-epektibo . Ngayon ay makikilala natin ang isang bagong istraktura - isang dobleng naka-link na listahan na LinkedList . Alamin natin kung paano ito gumagana, bakit ito tinatawag na dobleng konektado, at kung paano ito naiiba sa ArrayList . Sa isang LinkedList, ang mga elemento ay talagang mga link sa isang chain. Ang bawat elemento, bilang karagdagan sa data na iniimbak nito, ay may link sa nakaraan at susunod na elemento . Binibigyang-daan ka ng mga link na ito na lumipat mula sa isang elemento patungo sa isa pa. Ito ay nilikha tulad nito:

public class Main {

   public static void main(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 Moscow");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

Konklusyon:

[Hello World! My name is Earl, I love Java, I live in Moscow]

Ito ang magiging hitsura ng istraktura ng aming listahan: Tingnan natin kung paano idinagdag ang isang bagong elemento. Ginagawa ito gamit ang add().

earlBio.add(str2);

Sa panahon ng linyang ito ng code, ang aming listahan ay binubuo ng isang elemento - ang string str1. Tingnan natin kung ano ang susunod na mangyayari sa larawan: Bilang resulta str2, at str1maging konektado sa pamamagitan ng mga link na nakaimbak sa kanila nextat previous: Ngayon ay dapat mong maunawaan ang pangunahing ideya ng isang dobleng naka-link na listahan. Ang mga elemento LinkedListay isang solong listahan na tiyak salamat sa hanay ng mga link na ito. Walang array sa loob LinkedList, tulad ng sa ArrayList, o anumang katulad. Ang lahat ng gumagana sa ArrayList (sa pamamagitan ng at malaki) ay bumaba sa pagtatrabaho sa panloob na array. Ang lahat ng trabaho LinkedListay bumababa sa pagbabago ng mga link. Ito ay napakalinaw na nakikita sa pamamagitan ng pagdaragdag ng isang elemento sa gitna ng listahan:

public class Main {

   public static void main(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 Moscow");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

Tulad ng nakikita mo, ang overloaded na pamamaraan add()ay nagbibigay-daan sa iyo upang tukuyin ang isang tiyak na index para sa bagong elemento. Sa kasong ito, gusto naming magdagdag ng linya str2sa pagitan str1ng at str3. Ito ang mangyayari sa loob: At bilang resulta ng pagbabago ng mga panloob na link, str2matagumpay na naidagdag ang elemento sa listahan: Ngayon lahat ng 3 elemento ay naka-link. Mula sa unang elemento sa kahabaan ng kadena nextmaaari kang pumunta sa huli at likod. Mas marami o mas kaunti ang naisip namin ang pagpapasok, ngunit paano ang pagtanggal ng mga elemento? Ang prinsipyo ng pagpapatakbo ay pareho. I-redefine lang namin ang mga link ng dalawang elemento "sa mga gilid" ng inaalis:

public class Main {

   public static void main(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 Moscow");

       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 elementong may index 1 (ito ay nasa gitna ng listahan): Pagkatapos muling tukuyin ang mga link, makukuha natin ang ninanais na resulta: Hindi tulad ng pagtanggal, ArrayListwalang mga pagbabago sa mga elemento ng array at mga katulad nito. I-redefine lang namin ang mga sanggunian ng str1at mga elemento str3. Ngayon ay itinuro nila ang isa't isa, at ang bagay str2ay "bumagsak" sa hanay ng mga link na ito at hindi na bahagi ng listahan.

Pangkalahatang-ideya ng mga pamamaraan

LinkedListMarami itong pagkakatulad sa ArrayListmga pamamaraan. Halimbawa, ang mga pamamaraan tulad ng add(), remove(), indexOf(), clear(), contains()(ay ang elementong nakapaloob sa listahan), set()(pagpasok ng elementong may kapalit) size()ay nasa parehong klase. Bagama't (gaya ng nalaman namin sa halimbawa add()at remove()) marami sa kanila ang gumagana nang iba sa loob, ngunit sa huli ginagawa nila ang parehong bagay. Gayunpaman, LinkedListmayroon itong magkahiwalay na mga pamamaraan para sa pagtatrabaho sa simula at pagtatapos ng listahan, na wala sa ArrayList:

• addFirst(), addLast(): mga pamamaraan para sa pagdaragdag ng isang elemento sa simula/katapusan 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 + '\'' +
               '}';
   }
}

Konklusyon:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
[Car{model='Ford Mondeo'}, Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]

Bilang resulta, ang Ford ay napunta sa tuktok ng listahan, at ang Fiat sa dulo.

• peekFirst(), peekLast(): ibalik ang una/huling elemento ng listahan. Ibalik nullkung 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());
}

Konklusyon:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}

• pollFirst(), pollLast(): ibalik ang una/huling elemento ng listahan at alisin ito sa listahan . Ibalik nullkung 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 left on the list?");
   System.out.println(cars);
}

Konklusyon:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]

• toArray(): nagbabalik ng hanay ng mga elemento ng 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));
}

Konklusyon:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]

Ngayon alam na natin kung paano ito gumagana LinkedListat kung paano ito naiiba sa ArrayList. Ano ang mga pakinabang ng paggamit nito LinkedList? Una sa lahat, sa pagtatrabaho sa gitna ng listahan . Ang pagpasok at pagtanggal sa gitna LinkedListay mas simple kaysa sa ArrayList. Tinutukoy lang namin ang mga link ng mga kalapit na elemento, at ang hindi kinakailangang elemento ay "nahuhulog" mula sa chain ng mga link. Habang ArrayListkami ay:

• suriin kung may sapat na espasyo (kapag ipinapasok)
• kung ito ay hindi sapat, lumikha ng isang bagong array at kopyahin ang data doon (kapag i-paste)
• tanggalin/ipasok ang isang elemento, at ilipat ang lahat ng iba pang elemento sa kanan/kaliwa (depende sa uri ng operasyon). Bukod dito, ang pagiging kumplikado ng prosesong ito ay lubos na nakasalalay sa laki ng listahan. Isang bagay ang kumopya/maglipat ng 10 elemento, ngunit iba ang gawin ang parehong sa isang milyong elemento.

Iyon ay, kung sa iyong programa ay nagaganap ang mga operasyon ng pagpapasok/pagtanggal nang mas madalas sa gitna ng listahan, LinkedListdapat itong 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 to run for LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Konklusyon:

Время работы для LinkedList (в мorсекундах) = 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 to run for ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Konklusyon:

Время работы для ArrayList (в миллисекундах) = 181

Bigla! Mukhang nagsasagawa kami ng operasyon na LinkedListdapat ay mas mahusay - pagpasok ng 100 elemento sa gitna ng listahan. At napakalaki ng aming listahan - 5,000,000 elemento: ArrayListkailangan naming maglipat ng ilang milyong elemento sa tuwing ipinapasok namin ang mga ito! Ano ang dahilan ng kanyang pagkapanalo? Una, ang isang elemento ay naa-access sa ArrayListisang nakapirming dami ng oras. Kapag ipinahiwatig mo:

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

pagkatapos ay sa kaso ng ArrayList[2_000_000] ito ay isang tiyak na address sa memorya, dahil mayroon itong array sa loob. Habang ang LinkedListarray ay hindi. Hahanapin nito ang numero ng elemento 2_000_000 kasama ang kadena ng mga link. Para sa kanya, hindi ito isang address sa memorya, 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 (pagtanggal) sa gitna ng listahan, ArrayListalam na nito ang eksaktong address sa memorya kung saan dapat itong ma-access, ngunit LinkedListkailangan pa rin nitong "alamin" sa tamang lugar. Pangalawa , ang bagay ay nasa istruktura ng ArrayList'a mismo. Ang pagpapalawak ng panloob na hanay, pagkopya ng lahat ng mga elemento at paglilipat ng mga elemento ay isinasagawa ng isang espesyal na panloob na function - System.arrayCopy(). Gumagana ito nang napakabilis dahil espesyal itong na-optimize para sa trabahong ito. Ngunit sa mga sitwasyon kung saan hindi na kailangang "stomp" sa nais na index, LinkedListito ay talagang nagpapakita ng sarili na mas mahusay. Halimbawa, kung ang pagpapasok ay nangyayari sa 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("Result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

Konklusyon:

Результат в миллисекундах: 43448
Результат в миллисекундах: 107

Isang ganap na kakaibang resulta! Tumagal ng higit sa 43 segundo upang magpasok ng isang milyong elemento sa simula ng listahan ArrayList, habang LinkedListnatapos ito sa loob ng 0.1 segundo! Ito ay tiyak na ang katotohanan na sa sitwasyong ito LinkedListay hindi namin kailangang "tumakbo" sa pamamagitan ng kadena ng mga link sa gitna ng listahan sa bawat oras. Kaagad niyang natagpuan ang kinakailangang index sa simula ng listahan, at doon ang pagkakaiba sa mga prinsipyo ng pagpapatakbo ay nasa kanyang panig :) Sa katunayan, ang " ArrayListversus LinkedList" na talakayan ay laganap na, at hindi na natin ito malalalim sa kasalukuyang antas. Ang pangunahing bagay na kailangan mong tandaan:

• Hindi lahat ng mga pakinabang ng isang partikular na koleksyon "sa papel" ay gagana sa katotohanan (tiningnan namin ito gamit ang halimbawa mula sa gitna ng listahan)
• Hindi ka dapat magpakalabis kapag pumipili ng isang koleksyon (" ArrayListito ay palaging mas mabilis, gamitin ito at hindi ka magkakamali. LinkedListWalang sinuman ang gumagamit nito nang mahabang panahon").

Bagama't kahit na ang tagalikha na LinkedListsi Joshua Bloch ay nagsabi ng gayon :) Gayunpaman, ang pananaw na ito ay malayo sa 100% tama, at kami ay kumbinsido dito. Sa aming nakaraang halimbawa LinkedListito ay gumana nang 400 (!) beses nang mas mabilis. Ang isa pang bagay ay talagang kakaunti ang mga sitwasyon kung kailan LinkedListito ang pinakamahusay na pagpipilian. Ngunit umiiral ang mga ito, at sa tamang panahon LinkedListay seryoso silang makakatulong sa iyo. Huwag kalimutan ang napag-usapan natin sa simula ng lecture: ang iba't ibang istruktura ng data ay pinakaepektibo para sa iba't ibang gawain. Imposibleng sabihin nang may 100% kumpiyansa kung aling istraktura ng data ang magiging mas mahusay hanggang sa malaman ang lahat ng mga kondisyon ng problema. Sa ibang pagkakataon malalaman mo ang higit pa tungkol sa mga koleksyong ito, at magiging mas madaling pumili. Ngunit ang pinakasimple at pinakaepektibong opsyon ay palaging pareho: subukan ang pareho sa totoong data mula sa iyong programa. Pagkatapos ay makikita mo sa iyong sariling mga mata ang mga resulta ng parehong mga listahan at tiyak na hindi ka magkakamali :)