Java-da LinkedList

Salom! Barcha so'nggi ma'ruzalar ArrayList ro'yxatini o'rganishga bag'ishlangan . Ushbu ma'lumotlar strukturasi juda qulay va ko'plab muammolarni hal qilish imkonini beradi. Biroq, Java boshqa ko'plab ma'lumotlar tuzilmalariga ega. Nega? Birinchidan, chunki mavjud vazifalar doirasi juda keng va turli vazifalar uchun turli xil ma'lumotlar tuzilmalari eng samarali hisoblanadi . Bugun biz yangi tuzilma bilan tanishamiz - ikki marta bog'langan ro'yxat LinkedList . Keling, u qanday ishlashini, nima uchun u ikki marta bog'langan deb nomlanganini va ArrayList dan qanday farq qilishini aniqlaymiz . LinkedList- da elementlar aslida zanjirdagi havolalardir. Har bir element, saqlaydigan ma'lumotlarga qo'shimcha ravishda, oldingi va keyingi elementga havolaga ega . Ushbu havolalar bir elementdan ikkinchisiga o'tish imkonini beradi. U shunday yaratilgan:

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

   }
}

Xulosa:

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

Ro'yxatimizning tuzilishi shunday ko'rinadi: Keling, yangi element qanday qo'shilganligini ko'rib chiqaylik. Bu yordamida amalga oshiriladi add().

earlBio.add(str2);

Ushbu kod satrida bizning ro'yxatimiz bitta elementdan iborat - string str1. Keling, rasmda nima sodir bo'lishini ko'rib chiqaylik: Natijada str2va str1ularda saqlangan havolalar orqali bog'laning nextva previous: Endi siz ikki tomonlama bog'langan ro'yxatning asosiy g'oyasini tushunishingiz kerak. LinkedListUshbu bog'lanishlar zanjiri tufayli elementlar yagona ro'yxatdir. Ichkarida LinkedListkabi qator ArrayListyoki shunga o'xshash biror narsa yo'q. ArrayList bilan barcha ishlar (katta va katta) ichki massiv bilan ishlashga to'g'ri keladi. Barcha ishlar LinkedListhavolalarni o'zgartirishga to'g'ri keladi. Bu ro'yxatning o'rtasiga element qo'shish orqali juda aniq ko'rinadi:

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

   }
}

Ko'rib turganingizdek, haddan tashqari yuklangan usul add()yangi element uchun ma'lum bir indeksni belgilash imkonini beradi. Bunday holda, biz va str2orasiga qator qo'shmoqchimiz . Ichkarida shunday bo'ladi: Va ichki havolalarni o'zgartirish natijasida element ro'yxatga muvaffaqiyatli qo'shiladi: Endi barcha 3 element bog'langan. Zanjir bo'ylab birinchi elementdan siz oxirgi va orqaga o'tishingiz mumkin. Biz qo'shishni ko'proq yoki kamroq tushundik, lekin elementlarni o'chirish haqida nima deyish mumkin? Ishlash printsipi bir xil. Biz shunchaki olib tashlangan elementning "yon tomonlaridagi" ikkita elementning havolalarini qayta belgilaymiz: str1str3str2next

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

Indeks 1 bo'lgan elementni o'chirsak, shunday bo'ladi (u ro'yxatning o'rtasida): Bog'lanishlarni qayta aniqlagandan so'ng biz kerakli natijaga erishamiz: O'chirishdan farqli o'laroq, ArrayListmassiv elementlarining siljishi va shunga o'xshashlar yo'q. str1Biz shunchaki va elementlarning havolalarini qayta belgilaymiz str3. Endi ular bir-biriga ishora qiladilar va ob'ekt str2ushbu bog'lanishlar zanjiridan "tashlab qo'yilgan" va endi ro'yxatning bir qismi emas.

Usullarga umumiy nuqtai

U usullar LinkedListbilan juda ko'p o'xshashliklarga ega . ArrayListMasalan, add(), remove(), indexOf(), clear(), contains()(roʻyxatdagi element), set()(almashtirilgan elementni kiritish) kabi usullar size()ikkala sinfda ham mavjud. Garchi (misolda aniqlaganimizdek add()va remove()) ularning ko'pchiligi ichki jihatdan boshqacha ishlaydi, lekin oxir-oqibat ular xuddi shu narsani qiladilar. Biroq, LinkedListro'yxatning boshi va oxiri bilan ishlashning alohida usullari mavjud, ular quyidagilarda mavjud emas ArrayList:

• addFirst(), addLast(): roʻyxatning boshiga/oxiriga element qoʻshish usullari

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 + '\'' +
               '}';
   }
}

Xulosa:

[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'}]

Natijada Ford ro‘yxatning birinchi o‘rnini, Fiat esa oxirgi o‘rinni egalladi.

• peekFirst(), peekLast(): roʻyxatning birinchi/oxirgi elementini qaytaradi. nullRo'yxat bo'sh bo'lsa, qayting .

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

Xulosa:

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

• pollFirst(), pollLast(): roʻyxatning birinchi/oxirgi elementini qaytaring va uni roʻyxatdan olib tashlang . nullRo'yxat bo'sh bo'lsa, qayting

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

Xulosa:

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

• toArray(): roʻyxat elementlari qatorini qaytaradi

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

Xulosa:

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

LinkedListEndi biz uning qanday ishlashini va qanday farq qilishini bilamiz ArrayList. Undan foydalanishning qanday afzalliklari bor LinkedList? Avvalo, ro'yxatning o'rtasi bilan ishlashda . O'rtaga kiritish va o'chirish LinkedListga qaraganda ancha sodda ArrayList. Biz shunchaki qo'shni elementlarning havolalarini qayta aniqlaymiz va keraksiz element bog'lanishlar zanjiridan "tushadi". Bizda bo'lganimizda ArrayList:

• etarli joy mavjudligini tekshiring (qo'shayotganda)
• agar bu etarli bo'lmasa, yangi massiv yarating va u erda ma'lumotlarni nusxalang (joylashtirishda)
• elementni o'chirish/qo'shish va boshqa barcha elementlarni o'ngga/chapga siljitish (operatsiya turiga qarab). Bundan tashqari, ushbu jarayonning murakkabligi ko'p jihatdan ro'yxat hajmiga bog'liq. 10 ta elementdan nusxa ko‘chirish/ko‘chirish boshqa narsa, lekin million element bilan ham xuddi shunday qilish boshqa.

Ya'ni, agar dasturingizda qo'shish/o'chirish operatsiyalari ro'yxatning o'rtasida tez-tez sodir bo'lsa, LinkedListu dan tezroq bo'lishi kerak ArrayList.

Nazariy jihatdan

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

Xulosa:

Время работы для 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));
   }
}

Xulosa:

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

Birdan! Biz ancha samarali bo'lishi kerak bo'lgan operatsiyani bajarayotganga o'xshaymiz LinkedList- ro'yxatning o'rtasiga 100 ta elementni kiritish. Va bizning ro'yxatimiz juda katta - 5 000 000 element: ArrayListbiz ularni har safar kiritganimizda bir necha million elementni almashtirishga majbur bo'ldik! Uning g'alabasiga sabab nima? Birinchidan, elementga ArrayListma'lum vaqt ichida kirish mumkin. Siz ko'rsatganingizda:

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

keyin [2_000_000] holatida ArrayListbu xotiradagi aniq manzil, chunki uning ichida massiv bor. Massiv LinkedListbo'lmasa. U bog'lanishlar zanjiri bo'ylab 2_000_000 raqamli elementni qidiradi. Uning uchun bu xotiradagi manzil emas, balki haligacha erishish kerak bo'lgan havola:

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………

Natijada, ro'yxatning o'rtasiga har bir qo'shish (o'chirish) bilan ArrayListu kirishi kerak bo'lgan xotiradagi aniq manzilni allaqachon biladi, lekin LinkedListu hali ham kerakli joyga "topish" kerak. Ikkinchidan , masalaning o'zi "a" tuzilishida ArrayList. Ichki massivni kengaytirish, barcha elementlarni nusxalash va elementlarni o'zgartirish maxsus ichki funktsiya tomonidan amalga oshiriladi - System.arrayCopy(). Bu juda tez ishlaydi, chunki u bu ish uchun maxsus optimallashtirilgan. Ammo kerakli indeksga "to'g'rilash" kerak bo'lmagan holatlarda, LinkedListu haqiqatan ham o'zini yaxshiroq ko'rsatadi. Misol uchun, agar kiritish ro'yxatning boshida sodir bo'lsa. Keling, u erda million elementni kiritishga harakat qilaylik:

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

}

Xulosa:

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

Mutlaqo boshqacha natija! Roʻyxatning boshiga million elementni kiritish uchun 43 soniyadan koʻproq vaqt kerak boʻldi ArrayList, LinkedListu 0,1 soniyada yakunlandi! Aynan shu vaziyatda LinkedListbiz har safar ro'yxatning o'rtasiga bog'lanish zanjiri bo'ylab "yugurishimiz" shart emas edi. U darhol ro'yxatning boshida kerakli indeksni topdi va u erda ishlash tamoyillaridagi farq allaqachon uning tomonida edi :) Aslida, " ArrayListqarshi LinkedList" muhokamasi juda keng tarqalgan va biz hozirda unga chuqur kirmaymiz. Daraja. Eslash kerak bo'lgan asosiy narsa:

• Muayyan "qog'ozdagi" to'plamning barcha afzalliklari haqiqatda ishlamaydi (biz buni ro'yxatning o'rtasidan misol yordamida ko'rib chiqdik)
• To'plamni tanlashda siz haddan oshib ketmasligingiz kerak (" ArrayListu har doim tezroq, undan foydalaning va adashmaysiz. LinkedListUni uzoq vaqtdan beri hech kim ishlatmagan").

Hatto yaratuvchisi LinkedListJoshua Bloch ham shunday deydi :) Biroq, bu nuqtai nazar 100% to'g'ri emas va biz bunga aminmiz. Oldingi misolimizda LinkedListu 400 (!) marta tezroq ishlagan. Yana bir narsa shundaki, LinkedListbu eng yaxshi tanlov bo'lgan holatlar juda kam. Ammo ular mavjud va kerakli vaqtda LinkedListular sizga jiddiy yordam berishlari mumkin. Ma'ruza boshida nima haqida gaplashganimizni unutmang: turli xil ma'lumotlar tuzilmalari turli vazifalar uchun eng samarali hisoblanadi. Muammoning barcha shartlari ma'lum bo'lmaguncha, qaysi ma'lumotlar strukturasi yaxshiroq bo'lishini 100% ishonch bilan aytish mumkin emas. Keyinchalik siz ushbu to'plamlar haqida ko'proq bilib olasiz va tanlov qilish osonroq bo'ladi. Ammo eng oddiy va eng samarali variant har doim bir xil: ikkalasini ham dasturingizdagi haqiqiy ma'lumotlarda sinab ko'ring. Keyin ikkala ro'yxatning natijalarini o'z ko'zingiz bilan ko'rishingiz mumkin va siz, albatta, xato qilmaysiz :)