Java Bağlantılı Listesi

MERHABA! En son derslerin tümü ArrayList'e ayrılmıştır . Bu veri yapısı çok uygun ve kullanışlıdır. Pek çok görevin üstesinden gelebilir. Ancak Java'nın birçok başka veri yapısı vardır. Neden? Her şeyden önce, çünkü görev yelpazesi çok büyük ve en verimli veri yapıları farklı görevler için farklı. Bugün yeni bir yapıyla tanışacağız: Java LinkedList , çift bağlantılı bir liste.

Nasıl organize edildiğini, neden çift bağlantılı olarak adlandırıldığını ve ArrayList'ten nasıl farklı olduğunu görelim . Java LinkedList'teki öğeler aslında tek bir zincirdeki bağlantılardır. Verilere ek olarak, her öğe önceki ve sonraki öğelere referansları saklar. Bu referanslar, bir öğeden diğerine geçmenizi sağlar. Bir tane şu şekilde oluşturursunuz:

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

   }
}

Çıktı: [Merhaba Dünya! Benim adım Earl, Java'yı seviyorum, Kanada'da yaşıyorum] Listemiz şöyle görünüyor: Bağlantılı Liste - 2

Yeni bir öğeyi nasıl ekleyeceğimizi görelim. Bu , add() yöntemi kullanılarak yapılır .

earlBio.add(str2);

Koddaki noktada, listemiz bir öğeden oluşur: String str1 . Resimde bundan sonra ne olduğunu görelim: Bağlantılı Liste - 3

Sonuç olarak, str2 ve str1, listenin bu düğümlerinde saklanan sonraki ve önceki bağlantılar aracılığıyla bağlanır : Bağlantılı Liste - 4

Şimdi çift bağlantılı bir listenin ana fikrini anlamalısınız. Bu bağlantılar zinciri, tam olarak LinkedList öğelerini tek bir liste yapan şeydir . ArrayList'ten farklı olarak , LinkedList'in içinde bir dizi veya dizi benzeri bir şey yoktur. ArrayList ile herhangi bir (çoğu, çoğu) çalışma, dahili dizi ile çalışmaya indirgenir. Java LinkedList ile herhangi bir çalışmadeğişen bağlantılara kadar kaynar. Bu, listenin ortasına bir öğe ekleyerek çok net bir şekilde görülebilir:

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

   }
}

Gördüğünüz gibi, aşırı yüklenmiş add() yöntemi, yeni bir öğe için belirli bir dizin belirlemenizi sağlar. Bu durumda, str1 ve str3 arasına String str2 eklemek istiyoruz . Dahili olarak şu şekilde olacak: Dahili linkleri değiştirdikten sonra, str2 listeye başarıyla eklendi: Artık 3 elemanın tümü birbirine bağlı. Bir sonraki halka aracılığıyla zincirdeki ilk elemandan sonuncuya ve tekrar geri gidebilirsiniz . Yani, ekleme konusunda oldukça rahatız, peki ya öğeleri kaldırmak? İlke tamamen aynıdır. Kaldırılan öğenin "sağındaki ve solundaki" iki öğedeki bağlantıları güncelliyoruz: Bağlantılı Liste - 5

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

Dizin 1'e sahip öğeyi (listenin ortasında) silersek ne olur: Bağlantılı Liste - 7

Bağlantıları güncelledikten sonra istenen sonucu elde ederiz: ArrayList'teki Bağlantılı Liste - 8

kaldırma işleminin aksine , burada dizi öğelerini kaydırmaya veya yapmaya gerek yoktur. türden herhangi bir şey. Sadece str1 ve str3 için bağlantıları güncelliyoruz . Artık birbirlerini işaret ediyorlar ve str2 , halkalar zincirinden " çıktı " ve artık listenin bir parçası değil.

Yöntemlere genel bakış

LinkedList'in ArrayList ile birçok ortak yöntemi vardır . Örneğin, her iki sınıfın da add() , remove() , indexOf() , clear() , include() (bir öğenin listede olup olmadığını gösterir), set() (mevcut bir öğenin yerine geçer) ve boyut() . Birçoğu dahili olarak farklı çalışsa da ( add() ve remove() ile bulduğumuz gibi ), sonuç aynıdır. Ancak LinkedList , listenin başı ve sonu ile çalışmak için ArrayList'te olmayan ayrı yöntemlere sahiptir:

addFirst() , addLast() : Listenin başına/sonuna bir öğe eklemek için bu yöntemler

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

Çıktı: [Araba{model='Ferrari 360 Spider'}, Araba{model='Bugatti Veyron'}, Araba{model='Lamborghini Diablo'}] [Araba{model='Ford Mondeo'}, Araba{model=' Ferrari 360 Spider'}, Araba{model='Bugatti Veyron'}, Araba{model='Lamborghini Diablo'}, Araba{model='Fiat Ducato'}] Listenin başında "Ford" yazıyoruz , ve sonunda "Fiat".

peekFirst() , peekLast() : Yöntemler, listedeki ilk/son öğeyi döndürür. Liste boşsa null döndürürler .

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

Çıktı: Araba{model='Ferrari 360 Spider'} Araba{model='Lamborghini Diablo'}

pollFirst() , pollLast() : Bu yöntemler listedeki ilk/son öğeyi döndürür ve listeden kaldırır. Liste boşsa null döndürürler

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

Çıktı: Araba{model='Ferrari 360 Spider'} Araba{model='Lamborghini Diablo'} Listede geriye ne kaldı? [Araba{model='Bugatti Veyron'}]

toArray() : Bu yöntem, liste öğelerini içeren bir dizi döndürü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));
}

Çıktı: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Artık LinkedList'in nasıl çalıştığını ve organizasyonunun ArrayList'ten nasıl farklı olduğunu biliyoruz . LinkedList kullanmanın faydaları nelerdir ? Her şeyden önce, listenin ortasında çalışırken fayda sağlıyoruz. LinkedList'in ortasındaki ekleme ve çıkarma işlemleri, ArrayList'tekinden çok daha basittir . Sadece komşu elemanların bağlantılarını güncelleriz ve istenmeyen eleman, bağlantı zincirinden "çıkar". Ancak bir ArrayList içinde ,

yeterli alan olup olmadığını kontrol edin (eklerken)
değilse, yeni bir dizi oluştururuz ve verileri oraya kopyalarız (eklerken)
öğeyi çıkarır/yerleştiririz ve diğer tüm öğeleri sağa/sola taşırız (işlemin türüne bağlı olarak). Ve bu sürecin karmaşıklığı büyük ölçüde listenin boyutuna bağlıdır. 10 öğeyi kopyalamak/taşımak bir şeydir ve aynısını bir milyon öğeyle yapmak tamamen başka bir şeydir.

Başka bir deyişle, programınızda listenin ortasındaki ekleme/çıkarma işlemleri en yaygınsa, LinkedList ArrayList'ten daha hızlı olmalıdır .

Teoride

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

Çıktı: LinkedList tarafından geçen süre (milisaniye cinsinden) = 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));
   }
}

Çıktı: ArrayList tarafından geçen süre (milisaniye olarak) = 181 Bu beklenmedik bir şeydi! LinkedList'in çok daha verimli olması gereken bir işlem gerçekleştirdik : bir listenin ortasına 100 öğe eklemek. Ve listemiz çok büyük: 5.000.000 element. ArrayList, her eklemede birkaç milyon öğeyi kaydırmak zorunda kaldı! Nasıl kazandı? İlk olarak, ArrayList'in öğelere erişmesi için gereken süre sabittir (sabit). yazdığınızda

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

ArrayList [2_000_000] belirli bir bellek adresidir (sonuçta, listenin dahili bir dizisi vardır) . Ancak, bir LinkedList'in bir dizisi yoktur. Bağlantı zinciri boyunca 2_000_000 numaralı öğeyi arayacaktır. LinkedList için bu bir bellek adresi değil, yine de ulaşılması gereken bir bağlantıdır: 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……… Sonuç olarak, listenin ortasındaki her ekleme (çıkarma) sırasında , ArrayList, erişilecek tam bellek adresini zaten biliyor, ancak LinkedList'in yine de "oraya ulaşması" gerekiyor. İkincisi, ArrayList'in yapısı var.kendisi. Özel bir dahili işlev ( System.arrayCopy() ), dahili diziyi genişletir ve tüm öğeleri kopyalar ve kaydırır. Bu özel iş için optimize edildiğinden çok hızlıdır. Ancak belirli bir dizine "ulaşmanız" gerekmediğinde, LinkedList kazanır. Diyelim ki listenin en başına ekledik. Oraya bir milyon öğe eklemeyi deneyelim:

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

}

Çıktı: Milisaniye cinsinden sonuç: 43448 Milisaniye cinsinden sonuç: 107 Şimdi tamamen farklı bir sonuç elde ediyoruz! ArrayList, listenin başına bir milyon öğe eklemek için 43 saniyeden fazla zaman harcarken, LinkedList bunu 0,1 saniyede yapmayı başardı! LinkedList burada fayda sağladı, çünkü her seferinde listenin ortasına bağlantılar zincirinden geçmek zorunda değildi. Listenin başında gerekli indeksi hemen bulur, bu nedenle farklı algoritma zaten bir avantajdır. :) Aslında, " ArrayList ve LinkedList " tartışması çok yaygın ve bu konuya şu anki düzeyde derinlemesine dalmayacağız. Hatırlamanız gereken en önemli şey şudur:

Belirli bir koleksiyonun tüm teorik avantajları gerçekte her zaman işe yaramaz (bunu listenin ortasındaki örnekte gördük)
Bir koleksiyon seçerken aşırı bir tutum benimsemeyin (" ArrayList her zaman daha hızlıdır. Kullanın ve yanlış gidemezsiniz. Kimse LinkedList'i uzun süredir kullanmıyor").

LinkedList'in yazarı Joshua Bloch bile durumun böyle olduğunu söylese de . :) Yine de bu bakış açısı %100 doğru olmaktan çok uzak ve kendimizi buna ikna ettik. Bir önceki örneğimizde LinkedList 400 (!) kat daha hızlıydı. Başka bir şey de, LinkedList'in en iyi seçim olduğu gerçekten çok az durum olmasıdır . Ama varlar ve doğru zamanda LinkedListcömertçe ödüllendirebilir. Dersin başında söylediğimizi unutmayın: En verimli veri yapıları farklı görevler için farklıdır. Görevinizin tüm koşullarını öğrenene kadar hangi veri yapısının en iyi olacağından %100 emin olmak imkansızdır. Bu koleksiyonlar hakkında daha sonra daha fazla bilgi edineceksiniz, bu da seçimi kolaylaştıracaktır. Ancak en basit ve en etkili seçenek her zaman aynıdır: her ikisini de programınızda kullanılan gerçek veriler üzerinde deneyin. O zaman her iki liste türünün de nasıl performans gösterdiğini kendi gözlerinizle görebileceksiniz ve kesinlikle yanılmayacaksınız. :) Öğrendiklerinizi pekiştirmek için Java Kursumuzdan bir video dersi izlemenizi öneririz.

Daha fazla okuma:
LinkedList Java Veri Yapısı