Məqalə
Başlamaq
Öyrənməyə başlayın
JavaRush /Java Blogu /Random-AZ /Java-da LinkedList
Зепп Бранниган
Səviyyə

Java-da LinkedList

Qrupda dərc edilmişdir
Salam! Bütün son mühazirələr ArrayList siyahısının öyrənilməsinə həsr edilmişdir . Bu məlumat strukturu çox rahatdır və bir çox problemləri həll etməyə imkan verir. Bununla belə, Java bir çox başqa məlumat strukturlarına malikdir. Niyə? Əvvəla, ona görə ki, mövcud tapşırıqların diapazonu çox genişdir və müxtəlif tapşırıqlar üçün müxtəlif məlumat strukturları ən effektivdir . Bu gün biz yeni strukturla tanış olacağıq - ikiqat əlaqəli siyahı LinkedList . Onun necə işlədiyini, niyə ikiqat bağlı adlandırıldığını və ArrayList- dən nə ilə fərqləndiyini anlayaq . LinkedList- də elementlər əslində zəncirin halqalarıdır. Hər bir element, saxladığı məlumatlara əlavə olaraq, əvvəlki və sonrakı elementə keçidə malikdir . Bu keçidlər bir elementdən digərinə keçməyə imkan verir. Bu belə yaradılmışdır: 
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);

   }
}
Nəticə: 

[Hello World! My name is Earl, I love Java, I live in Moscow]
Siyahımızın strukturu belə olacaq: LinkedList - 2Gəlin görək yeni element necə əlavə olunur. Bu istifadə edilir add(). 
earlBio.add(str2);
Bu kod sətri zamanı siyahımız bir elementdən ibarətdir - sətir str1. Şəkildə daha sonra nə baş verdiyini görək: LinkedList - 3Nəticədə str2, və str1onlarda saxlanılan keçidlər vasitəsilə əlaqə qurun nextvə previous: LinkedList - 4İndi ikiqat əlaqəli siyahının əsas fikrini başa düşməlisiniz. Bu bağlantılar zənciri sayəsində elementlər LinkedListvahid siyahıdır. İçəridə heç bir massiv yoxdur LinkedList, in kimi ArrayListvə ya buna bənzər bir şey. ArrayList ilə bütün işlər (və böyük ölçüdə) daxili massivlə işləməkdən irəli gəlir. Bütün işlər LinkedListkeçidlərin dəyişdirilməsi ilə bağlıdır. Bu, siyahının ortasına bir element əlavə etməklə çox aydın görünür: 
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);

   }
}
Gördüyünüz kimi, həddən artıq yüklənmiş metod add()yeni element üçün xüsusi bir indeks təyin etməyə imkan verir. Bu halda, və str2arasında bir xətt əlavə etmək istəyirik . İçəridə belə olacaq: Və daxili keçidlərin dəyişdirilməsi nəticəsində element siyahıya uğurla əlavə olunur: İndi hər 3 element əlaqələndirilir. Zəncir boyunca ilk elementdən sonuncuya və geriyə gedə bilərsiniz. Biz az-çox daxil etməyi başa düşdük, bəs elementləri silmək haqqında nə demək olar? Əməliyyat prinsipi eynidir. Sadəcə olaraq, çıxarılan elementin "yan tərəfindəki" iki elementin əlaqələrini yenidən müəyyənləşdiririk: str1str3LinkedList - 5str2LinkedList - 6next
Java-университет 
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);
   }
}
İndeksi 1 olan elementi silsək belə olacaq (siyahının ortasındadır): LinkedList - 7Əlaqələri yenidən təyin etdikdən sonra istədiyimiz nəticəni əldə edirik: LinkedList - 8Silməkdən fərqli olaraq ArrayListmassiv elementlərinin yerdəyişməsi və s. str1Biz sadəcə olaraq və elementlərinin istinadlarını yenidən müəyyənləşdiririk str3. İndi onlar bir-birinə işarə edir və obyekt str2bu bağlantılar zəncirindən “çıxıb” və artıq siyahının bir hissəsi deyil.

Metodlara ümumi baxış

Onun üsullarla LinkedListçox oxşar cəhətləri var . ArrayListMəsələn, add(), remove(), indexOf(), clear(), contains()(siyahıda olan elementdir), set()(əvəz etməklə elementin daxil edilməsi) kimi üsullar size()hər iki sinifdə mövcuddur. Baxmayaraq ki, (nümunədə add()və remove()) gördüyümüz kimi, onların bir çoxu daxili olaraq fərqli işləyir, lakin nəticədə eyni şeyi edirlər. Bununla birlikdə, LinkedListsiyahının əvvəli və sonu ilə işləmək üçün ayrı üsullara malikdir, bunlar aşağıda yoxdur ArrayList:
  • addFirst(), addLast(): siyahının əvvəlinə/sonuna element əlavə etmək üsulları
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 + '\'' +
               '}';
   }
}
Nəticə: 

[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'}]
Nəticədə siyahının başında Ford, sonda isə Fiat qərarlaşıb.
  • peekFirst(), peekLast(): siyahının birinci/son elementini qaytarır. nullSiyahı boşdursa geri qayıdın .
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());
}
Nəticə: 

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
  • pollFirst(), pollLast(): siyahının birinci/son elementini qaytarın və onu siyahıdan çıxarın . nullSiyahı boşdursa geri qayıdın
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);
}
Nəticə: 

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]
  • toArray(): siyahı elementləri massivini qaytarır
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));
}
Nəticə: 

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
LinkedListİndi bunun necə işlədiyini və ondan nə ilə fərqləndiyini bilirik ArrayList. Onu istifadə etməyin faydaları nələrdir LinkedList? Hər şeydən əvvəl siyahının ortası ilə işləyərkən . Ortaya daxil etmək və silmək LinkedListilə müqayisədə daha sadədir ArrayList. Biz sadəcə qonşu elementlərin əlaqələrini yenidən müəyyənləşdiririk və lazımsız element bağlantılar zəncirindən "düşür". Bizdə olarkən ArrayList:
  • kifayət qədər yer olub olmadığını yoxlayın (daxil edərkən)
  • kifayət deyilsə, yeni massiv yaradın və məlumatları oraya köçürün (yapışdırarkən)
  • elementi silin/daxil edin və bütün digər elementləri sağa/sola sürüşdürün (əməliyyat növündən asılı olaraq). Üstəlik, bu prosesin mürəkkəbliyi siyahının ölçüsündən çox asılıdır. 10 elementin surətini çıxarmaq/köçmək bir şeydir, amma milyon elementlə eyni şeyi etmək tamam başqadır.
Yəni, proqramınızda əlavə etmə/silmə əməliyyatları siyahının ortası ilə daha tez-tez baş verirsə, LinkedListbu, -dən daha sürətli olmalıdır ArrayList.

Nəzəriyyədə

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));
   }
}
Nəticə: 

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

Время работы для ArrayList (в миллисекундах) = 181
Birdən! Deyəsən, biz LinkedListdaha səmərəli olmalı olan bir əməliyyat həyata keçirirdik - siyahının ortasına 100 element daxil etmək. Siyahımız böyükdür - 5.000.000 element: ArrayListbiz hər dəfə onları daxil edəndə bir neçə milyon elementi dəyişməli olduq! Onun qələbəsinin səbəbi nədir? Birincisi, elementə ArrayListmüəyyən vaxt ərzində daxil olur. Göstərdiyiniz zaman: 
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
onda [2_000_000] vəziyyətində ArrayListbu, yaddaşdakı xüsusi ünvandır, çünki onun daxilində massiv var. Massiv LinkedListyoxdur. O, bağlantılar zənciri boyunca 2_000_000 nömrəli elementi axtaracaq. Onun üçün bu, yaddaşda olan bir ünvan deyil, hələ də əldə edilməli olan bir keçiddir: 

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………
Nəticədə, siyahının ortasına hər bir əlavə (silinmə) ilə ArrayListo, yaddaşda hansı ünvana daxil olmalı olduğunu artıq bilir, lakin LinkedListhələ də lazımi yerə "tapmaq" lazımdır. İkincisi , məsələ “bir”in öz quruluşundadır ArrayList. Daxili massivin genişləndirilməsi, bütün elementlərin surətinin çıxarılması və elementlərin dəyişdirilməsi xüsusi daxili funksiya ilə həyata keçirilir - System.arrayCopy(). Bu iş üçün xüsusi olaraq optimallaşdırıldığı üçün çox tez işləyir. Ancaq istədiyiniz indeksə "ayaqlamağa" ehtiyac olmadığı hallarda, LinkedListhəqiqətən də özünü daha yaxşı göstərir. Məsələn, əlavə siyahının əvvəlində baş verirsə. Oraya bir milyon element daxil etməyə çalışaq: 
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());
       }
   }

}
Nəticə: 

Результат в миллисекундах: 43448
Результат в миллисекундах: 107
Tamamilə fərqli bir nəticə! Siyahının əvvəlinə bir milyon element daxil etmək 43 saniyədən çox çəkdi ArrayList, halbuki LinkedListo, 0,1 saniyəyə tamamlandı! Məhz ondan ibarət idi ki, bu vəziyyətdə LinkedListbiz hər dəfə siyahının ortasına keçidlər zəncirindən “qaçmalı” deyildik. O, dərhal siyahının əvvəlində tələb olunan indeksi tapdı və orada iş prinsiplərindəki fərq artıq onun tərəfində idi :) Əslində, “ ArrayListqarşı LinkedList” müzakirəsi çox geniş yayılıb və indiki məqamda biz buna dərindən girməyəcəyik. səviyyə. Xatırlamaq lazım olan əsas şey:
  • "Kağız üzərində" müəyyən bir kolleksiyanın bütün üstünlükləri reallıqda işləməyəcək (biz buna siyahının ortasındakı nümunədən istifadə edərək baxdıq)
  • Kolleksiya seçərkən ifrata varmamalısınız (“ ArrayListo, həmişə daha sürətlidir, istifadə edin və yanılmazsınız. LinkedListUzun müddətdir heç kim istifadə etmir”).
Baxmayaraq ki, hətta yaradıcı LinkedListJoshua Bloch belə deyir :) Lakin, bu nöqteyi-nəzər 100% doğru deyil və biz buna əminik. Əvvəlki nümunəmizdə LinkedList400 (!) dəfə daha sürətli işləyirdi. LinkedListBaşqa bir şey odur ki , ən yaxşı seçim olacağı çox az vəziyyət var . Ancaq onlar mövcuddur və lazımi anda LinkedListsizə ciddi şəkildə kömək edə bilərlər. Mühazirənin əvvəlində nə haqqında danışdığımızı unutmayın: müxtəlif verilənlər strukturları müxtəlif tapşırıqlar üçün ən effektivdir. Problemin bütün şərtləri məlum olmayana qədər hansı məlumat strukturunun daha yaxşı olacağını 100% əminliklə söyləmək mümkün deyil. Daha sonra bu kolleksiyalar haqqında daha çox məlumat əldə edəcəksiniz və seçim etmək daha asan olacaq. Ancaq ən sadə və ən təsirli seçim həmişə eynidir: hər ikisini proqramınızdan real məlumatlar üzərində sınaqdan keçirin. O zaman hər iki siyahının nəticələrini öz gözlərinizlə görə bilərsiniz və mütləq yanılmayacaqsız :)
Şərhlər
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION