LinkedList koleksiyonuyla tanışın

1. TarihiLinkedList

Java, C++ dilinden devralınan başka bir Java koleksiyon sınıfına sahiptir. Bu LinkedList, bir "bağlı liste" uygulayan sınıftır.

Dıştan bakıldığında a, LinkedLista ile aynı gibi görünür ArrayList. Sınıf LinkedList, sınıfla aynı yöntemlere sahiptir ArrayList. LinkedListPrensip olarak, an yerine her zaman a kullanabilirsiniz ArrayListve her şey çalışacaktır.

Öyleyse neden başka bir liste sınıfına ihtiyacımız var?

Cevap, sınıfın iç yapısıyla ilgili her şeye sahiptir LinkedList. Bir dizi yerine, çift bağlantılı bir liste kullanır . Bunun ne olduğunu biraz sonra açıklayacağız.

Sınıfın LinkedListfarklı iç yapısı, listenin ortasına öğe eklemede onu en hızlı hale getirir.

ArrayListİnternette, ve sınıflarının karşılaştırmalarını sıklıkla bulabilirsiniz LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Her şey yeterince açık görünüyor: Listeye sık sık öğe eklemeniz gerekiyorsa, LinkedList; nadiren ise ArrayList'i kullanın. Ama gerçek biraz farklı.

2. Kimse kullanmazLinkedList

Kimse kullanmaz LinkedList.

Sınıfın yazarı bile LinkedListkısa süre önce tweet attı: "Gerçekten kullanan var mı LinkedList? Ben yazdım ve hiç kullanmıyorum."

Peki anlaşma nedir?

İlk olarak, sınıf ArrayListçok hızlı bir şekilde listenin ortasına öğeler ekleyebilmeye başladı. Listenin ortasına bir öğe eklerken, ekleme noktasından sonraki tüm öğeleri listenin sonuna doğru 1 kaydırmanız gerekir. Bu eskiden zaman alırdı.

Ama şimdi her şey değişti. Bir dizinin tüm öğeleri aynı bellek bloğunda birbirine yakındır, bu nedenle öğeleri kaydırma işlemi çok hızlı, düşük seviyeli bir komutla gerçekleştirilir: .System.arraycopy()

Ek olarak, günümüzün işlemcileri, dizi öğelerinin bellek yerine önbellek içinde kaydırılmasına izin veren, genellikle tüm diziyi tutabilen büyük bir önbelleğe sahiptir. Bir milyon öğe, tek bir milisaniyede kolayca kaydırılır.

İkincisi, bir yineleyici kullanarak eklerseniz, sınıf öğeleri hızlı bir şekilde ekleyebilir . LinkedLista üzerinden gitmek ve sürekli olarak yeni öğeler eklemek (veya mevcut olanları kaldırmak) için bir yineleyici kullanırsanız LinkedList, işlem süper hızlıdır.

Bir döngü içindeki bir nesneye basitçe öğeler eklerseniz LinkedList, her hızlı ekleme işlemine yavaş bir "element alma" işlemi eşlik eder.

Gerçek şuna çok daha yakın:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Neden bu kadar yavaş bir işlemden bir eleman elde ediliyor LinkedList?

Nasıl yapılandırıldığına biraz aşina olduktan sonra bu soruya cevap verebilirsiniz LinkedList.

3. Nasıl LinkedListyapılandırılır ?

LinkedListdan farklı bir iç yapıya sahiptir ArrayList. Öğeleri depolamak için dahili bir dizisi yoktur. Bunun yerine, çift mürekkepli liste adı verilen bir veri yapısı kullanır .

Çift bağlantılı bir listenin her öğesi, önceki öğeye ve sonraki öğeye bir referans saklar. Bu biraz, bir mağazadaki sıraya benziyor, burada her kişi hem önünde duran kişiyi hem de arkasında duran kişiyi hatırlıyor.

Böyle bir liste bellekte şöyle görünür:

Baş ve kuyruk (gri arka plana sahip hücreler), nesnelere referansları saklayan firstve değişkenleridir .lastNode

Ortada, bir Nodenesneler zinciriniz var (nesneler, değişkenler değil). Her biri üç alandan oluşur:

• prev— önceki nesneye (sarı arka plana sahip hücreler) bir başvuru (bağlantı) depolar.Node
• value— listenin bu öğesinin değerini saklar (yeşil arka plana sahip hücreler).
• next— bir sonraki nesneye (mavi arka plana sahip hücreler) bir başvuru (bağlantı) depolarNode

nextİkinci nesne (Adres F24), birinci nesne için sonraki ( ) ve prevüçüncü nesne için önceki ( )'dir. Üçüncü nesnenin sarı alanı F24 adresini içerir ve ilk nesnenin mavi alanı F24 adresini içerir.

Birinci ve üçüncü nesnelerden gelen oklar, aynı ikinci nesneyi gösterir. O yüzden okları bu şekilde çizmek daha doğru olacaktır.

4. Bağlantılı bir listeye bir öğe ekleyin

Bu şekilde sıraya birini eklemek için yan yana duran iki kişiden izin almanız yeterli. Birinci kişi yeni gelen kişiyi “arkamdaki kişi” olarak, ikinci kişi ise “önümdeki kişi” olarak hatırlar.

Tek yapmanız gereken iki komşu nesnenin referanslarını değiştirmek:

İkinci ve üçüncü nesnelerin referanslarını değiştirerek listemize bir yenisini daha ekledik. Yeni nesne, eski ikinci nesne için sonraki ve eski üçüncü nesne için önceki nesnedir. Ve elbette, yeni nesnenin kendisinin doğru referansları saklaması gerekir: önceki nesnesi eski ikinci nesnedir ve sonraki nesnesi eski üçüncü nesnedir.

Bir öğeyi kaldırmak daha da kolaydır: Diyelim ki 100. nesneyi listeden kaldırmak istiyorsak, 99. nesnenin alanını 101. nesneyi gösterecek şekilde değiştirmemiz nextve prev101. nesnenin alanını değiştirmemiz yeterlidir. 99'uncuyu gösterecek şekilde nesne. Bu kadar.

Ancak 100. nesneyi elde etmek o kadar kolay değil.

5. Listeden bir öğeyi kaldırın

Bağlantılı bir listenin 100. öğesini almak için yapmanız gerekenler:

first1. nesneyi alın: Bunu nesnedeki değişkeni kullanarak yaparsınız LinkedList. 1. nesnenin alanı next, 2. nesneye bir referans depolar. Böylece ikinci nesneyi elde etmiş oluyoruz. 2. nesnenin üçüncüye bir referansı vardır ve bu böyle devam eder.

100. nesneye bir referans almamız gerekiyorsa, 1'den 100'e kadar tüm nesneler arasında sırayla hareket etmemiz gerekir. Ve bir listedeki milyonuncu öğeye ihtiyacımız varsa, birbiri ardına bir milyondan fazla nesneyi yinelememiz gerekir!

Ve bu nesneler listeye farklı zamanlarda eklendiyse, belleğin farklı bölümlerinde yer alacaklar ve aynı anda işlemcinin önbelleğinde yer almaları pek olası değil. Bu, bağlantılı bir listenin öğelerini yinelemenin yalnızca yavaş değil, aynı zamanda çok yavaş olduğu anlamına gelir.

Biz bununla uğraşıyoruz.

Öyleyse neden size bu yavaşlığın nasıl çalıştığını öğretiyoruz LinkedList?

Peki, iş görüşmeleri sırasında sizden ne kadar LinkedListfarklı olduğuArrayList sorulacak . Kesinlikle.