Jawa LinkedList

Hi! Kabeh pelajaran paling anyar wis dikhususake kanggo ArrayList . Struktur data iki trep banget lan migunani. Bisa nangani akeh tugas. Nanging Jawa duwe akeh struktur data liyane. Kenging punapa? Sing paling penting, amarga macem-macem tugas akeh banget, lan struktur data sing paling efisien beda kanggo tugas sing beda-beda. Dina iki kita bakal nemokake struktur anyar: Java LinkedList , dhaptar sing digandhengake kaping pindho. Ayo ndeleng carane diatur, kok diarani dobel-linked, carane iku beda saka ArrayList . Unsur-unsur ing Java LinkedList sejatine minangka pranala ing rantai siji. Saliyane data, saben unsur nyimpen referensi menyang unsur sadurunge lan sabanjure. Referensi iki ngidini sampeyan pindhah saka siji unsur menyang unsur liyane. Iki carane nggawe siji:

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! Jenengku Earl, Aku tresna Jawa, Aku manggon ing Kanada] Punika dhaftar kita katon kaya: Ayo ndeleng carane nambah unsur anyar. Iki ditindakake kanthi nggunakake metode add () .

earlBio.add(str2);

Ing titik ing kode, dhaptar kita kalebu siji unsur: String str1 . Ayo ndeleng apa sing kedadeyan ing gambar sabanjure: Akibaté, str2 lan str1 dadi disambung liwat pranala sabanjuré lan sadurungé sing disimpen ing simpul dhaptar iki: Saiki sampeyan kudu ngerti gagasan utama dhaptar sing disambung kaping pindho. Rantai pranala iki persis sing ndadekake unsur LinkedList dadi dhaptar siji. Ora kaya ArrayList , LinkedList ora duwe array utawa apa wae sing ana ing njero. Sembarang (uga, paling) karya karo ArrayList boils mudhun kanggo nggarap array internal. Sembarang karya karo Java LinkedListboils mudhun kanggo ngganti pranala. Iki bisa dideleng kanthi jelas kanthi nambahake unsur ing tengah dhaptar:

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

   }
}

Nalika sampeyan bisa ndeleng, nambah overloaded () cara ngijini sampeyan nemtokake indeks tartamtu kanggo item anyar. Ing kasus iki, kita pengin nambah String str2 antarane str1 lan str3 . Iki sing bakal kelakon internal: Sawise ngganti pranala internal, str2 wis kasil ditambahake menyang dhaftar: Saiki kabeh 3 unsur disambungake. Sampeyan bisa mindhah liwat link sabanjuré saka unsur pisanan ing chain kanggo pungkasan lan bali maneh. Dadi, kita cukup nyaman karo sisipan, nanging kepiye mbusak unsur? Prinsipe pancen padha. Kita mung nganyari pranala ing rong unsur "kiwa lan tengen" saka unsur sing dibusak:

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

Mangkene apa sing kedadeyan yen kita mbusak item kanthi indeks 1 (ing tengah dhaptar): Sawise nganyari pranala, kita entuk asil sing dikarepake: Ora kaya operasi penghapusan ing ArrayList , ing kene ora perlu ngowahi unsur array utawa nindakake. apa wae. Kita mung nganyari pranala kanggo str1 lan str3 . Dheweke saiki nuding siji liyane, lan str2 wis " mudhun " saka rantai pranala lan ora ana maneh ing dhaptar.

Ringkesan cara

LinkedList nduweni akeh cara sing padha karo ArrayList . Contone, loro kelas duwe cara kayata nambah () , mbusak () , indexOf () , cetha () , ngandhut () (nuduhake apa item ing dhaftar), nyetel () (ngganti unsur sing wis ana), lan ukuran () . Senajan akeh wong bisa beda njero (kaya kita ketemu karo nambah () lan mbusak () ), asil pungkasan padha. Nanging, LinkedList duwe cara sing kapisah kanggo nggarap wiwitan lan pungkasan dhaptar, sing ora ana ing ArrayList :

• addFirst() , addLast() : Cara iki kanggo nambah unsur ing wiwitan/akhir dhaptar

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: [Mobil{model='Ferrari 360 Spider'}, Mobil{model='Bugatti Veyron'}, Mobil{model='Lamborghini Diablo'}] [Mobil{model='Ford Mondeo'}, Mobil{model=' Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}] We ended with "Ford" in the top of the list , lan "Fiat" ing pungkasan.

• peekFirst () , peekLast () : Cara ngasilake unsur pisanan / pungkasan ing dhaptar. Padha bali null yen dhaftar kosong.

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

Output: Mobil{model='Ferrari 360 Spider'} Mobil{model='Lamborghini Diablo'}

• pollFirst () , pollLast () : Cara iki ngasilake unsur pisanan / pungkasan ing dhaptar lan mbusak saka dhaptar. Padha bali null yen dhaftar kosong

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: Mobil{model='Ferrari 360 Spider'} Mobil{model='Lamborghini Diablo'} Apa sing isih ana ing dhaptar? [Mobil{model='Bugatti Veyron'}]

• toArray () : Cara iki ngasilake array sing ngemot item dhaptar

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: [Mobil{model='Ferrari 360 Spider'}, Mobil{model='Bugatti Veyron'}, Mobil{model='Lamborghini Diablo'}] Saiki kita ngerti cara kerja LinkedList lan kepiye organisasine beda karo ArrayList . Apa keuntungan nggunakake LinkList ? Sing paling penting, kita entuk manfaat nalika kerja ing tengah dhaptar. Operasi selipan lan mbusak ing tengah LinkedList luwih gampang tinimbang ing ArrayList . Kita mung nganyari pranala saka unsur tetanggan, lan unsur sing ora dikarepake "mudhun" saka rantai pranala. Nanging ing ArrayList , kita kudu

• priksa manawa ana cukup spasi (nalika nglebokake)
• yen ora, banjur kita nggawe array anyar lan nyalin data ana (nalika nglebokake)
• kita mbusak / masang unsur, lan mindhah kabeh unsur liyane ing sisih tengen / kiwa (gumantung ing jinis operasi). Lan kerumitan proses iki gumantung banget marang ukuran dhaptar. Iku salah siji kanggo nyalin / mindhah 10 unsur, lan cukup liyane kanggo nindakake padha karo yuta unsur.

Ing tembung liyane, yen operasi sisipan / mbusak ing tengah dhaftar paling umum ing program sampeyan, LinkedList kudu luwih cepet saka ArrayList .

Ing teori

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: Wektu sing dijupuk LinkedList (ing milidetik) = 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: Wektu sing dijupuk dening ArrayList (ing milliseconds) = 181 Sing ora dikarepke! Kita nindakake operasi ing ngendi LinkedList kudu luwih efisien: nglebokake 100 item ing tengah dhaptar. Lan dhaptar kita gedhe banget: 5.000.000 unsur. ArrayList kudu ngganti sawetara yuta item kanthi saben sisipan! Kepiye carane menang? Kaping pisanan, wektu sing dibutuhake kanggo ArrayList kanggo ngakses unsur tetep (konstan). Nalika sampeyan nulis

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

banjur ArrayList [2_000_000] alamat memori tartamtu (sawise kabeh, dhaftar wis Uploaded internal). Nanging, LinkedList ora duwe array. Bakal nggoleki nomer unsur 2_000_000 ing sadawane rantai pranala. Kanggo LinkedList, iki dudu alamat memori, nanging link sing isih kudu digayuh: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. sabanjure.sabanjure.sabanjure.sabanjure.sabanjure.sabanjure.sabanjure.sabanjure.sabanjure.sabanjure.sabanjure.sabanjure.sabanjure.sabanjure.sabanjure……… Akibate, sajrone saben sisipan (mbusak) ing tengah dhaptar , ArrayList wis ngerti alamat memori sing tepat kanggo ngakses, nanging LinkedList isih kudu "tekan kono". Kapindho, ana struktur ArrayListdhewe. Fungsi internal khusus ( System.arrayCopy () ) nggedhekake array internal, lan nyalin lan ngalih kabeh unsur. Cepet banget, amarga dioptimalake kanggo karya khusus iki. Nanging yen sampeyan ora kudu "tekan" indeks tartamtu, LinkedList minangka pemenang. Upaminipun kita masang ing awal banget dhaftar. Coba lebokake sejuta unsur ing kana:

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: Asil ing milliseconds: 43448 Asil ing milliseconds: 107 Saiki kita entuk asil sing beda banget! ArrayList ngginakaken luwih saka 43 detik nglebokake yuta item ing ngarep dhaftar njupuk, nalika LinkedList ngatur kanggo nindakaken ing 0,1 detik! LinkedList entuk manfaat ing kene, amarga ora kudu ngliwati rantai pranala menyang tengah dhaptar saben wektu. Langsung nemokake indeks sing dibutuhake ing wiwitan dhaptar, mula algoritma sing beda wis dadi kauntungan. :) Nyatane, diskusi " ArrayList versus LinkedList " nyebar banget, lan kita ora bakal nyilem ing tingkat saiki. Ingkang utama sampeyan kudu ngelingi yaiku:

• Ora kabeh kaluwihan teoretis koleksi tartamtu mesthi bisa digunakake ing kasunyatan (kita weruh iki kanthi conto sing ana ing tengah dhaptar)
• Aja nganggo posisi sing ekstrem nalika milih koleksi (" ArrayList tansah luwih cepet. Gunakake lan sampeyan ora bisa salah. Ora ana sing wis suwe nggunakake LinkedList ").

Sanajan penulis LinkList , Joshua Bloch, ujar manawa iki kedadeyan. :) Isih, perspektif iki adoh saka 100% bener, lan kita wis nggawe percoyo dhéwé iki. Ing conto sadurunge, LinkedList 400 (!) kaping luwih cepet. Bab liyane yaiku ana sawetara kahanan sing LinkList minangka pilihan sing paling apik. Nanging ana, lan ing wektu sing tepat LinkedListbisa menehi ganjaran apik. Aja lali apa sing kita ucapake ing wiwitan pelajaran: struktur data sing paling efisien beda-beda kanggo tugas sing beda-beda. Ora mungkin 100% yakin struktur data sing paling apik nganti sampeyan ngerti kabeh kahanan tugas sampeyan. Sampeyan bakal ngerti luwih akeh babagan koleksi kasebut mengko, sing bakal nggawe pilihan luwih gampang. Nanging pilihan sing paling gampang lan paling efektif mesthi padha: coba loro ing data nyata sing digunakake ing program sampeyan. Banjur sampeyan bakal bisa ndeleng dhewe carane loro jinis dhaptar nindakake lan sampeyan mesthi ora bakal salah. :) Kanggo nguatake apa sing sampeyan sinau, disaranake sampeyan nonton video pelajaran saka Kursus Jawa