Soru ArrayList üzerinden LinkedList ne zaman kullanılır?


Ben sadece her zaman kullanmak için bir tane oldum:

List<String> names = new ArrayList<>();

Arabirim için tip adı olarak kullanıyorum taşınabilirlikBöylece, böyle sorular sorduğumda kodumu yeniden işleyebilirim.

Ne zaman LinkedList bitmek ArrayList ve tam tersi mi?


2568
2017-11-27 01:36


Menşei


Ayrıca bakınız: Bağlantılı listeye karşılık dizi - Hawkeye Parker
Sadece LinkedList'in yazarından alıntıyı gör stackoverflow.com/a/42529652/2032701 ve konuyla ilgili pratik bir fikir edineceksiniz. - Ruslan


Cevaplar:


özet  ArrayList ile ArrayDeque tercih edilir çok daha fazla kullanım vakası LinkedList. Emin değilim - sadece başla ArrayList.


LinkedList ve ArrayList Liste arayüzünün iki farklı uygulaması vardır. LinkedList çift ​​bağlantılı bir liste ile uygular. ArrayList Dinamik olarak yeniden boyutlandırma dizisiyle uygular.

Standart bağlantılı liste ve dizi işlemlerinde olduğu gibi, çeşitli yöntemler farklı algoritmik çalışma zamanlarına sahip olacaktır.

İçin LinkedList<E>

  • get(int index) olduğu O (n) (ile n / 4 ortalama adımlar)
  • add(E element) olduğu O (1)
  • add(int index, E element) olduğu O (n) (ile n / 4 ortalama adımlar) fakat O (1) ne zaman index = 0  <--- ana faydası LinkedList<E>
  • remove(int index) olduğu O (n) (ile n / 4 ortalama adımlar)
  • Iterator.remove() olduğu O (1). <--- ana faydası LinkedList<E>
  • ListIterator.add(E element) olduğu O (1)  Bu, ana faydalarından biridir LinkedList<E>

Not: İşlemlerin çoğu ihtiyaç duymaktadır n / 4 ortalama adımlar, sabit en iyi durumda adım sayısı (ör. index = 0) ve n / 2 en kötü durumda adımlar (listenin ortası)

İçin ArrayList<E>

  • get(int index) olduğu O (1)  <--- ana faydası ArrayList<E>
  • add(E element) olduğu O (1) itfa edildi, ama O (n) dizinin yeniden boyutlandırılması ve kopyalanması gerektiğinden en kötü durum
  • add(int index, E element) olduğu O (n) (ile n / 2 ortalama adımlar)
  • remove(int index) olduğu O (n) (ile n / 2 ortalama adımlar)
  • Iterator.remove() olduğu O (n) (ile n / 2 ortalama adımlar)
  • ListIterator.add(E element) olduğu O (n) (ile n / 2 ortalama adımlar)

Not: İşlemlerin çoğu ihtiyaç duymaktadır n / 2 ortalama adımlar, sabit en iyi durumda olan adım sayısı (listenin sonu), n en kötü durumda adımlar (listenin başlangıcı)

LinkedList<E> sabit zamanlı ekleme veya kaldırma olanağı sağlar yineleyicileri kullanarakancak sadece elemanların sıralı erişimi. Diğer bir deyişle, listeyi ileriye veya geriye doğru yürütebilirsiniz, ancak listede bir konum bulmak, listenin boyutuna orantılı olarak zaman alır. Javadoc diyor ki "Listeye indeksleyen işlemler listeyi en baştan veya sondan, hangisi daha yakınsa geçecek"bu yüzden bu yöntemler O (n) (n / 4 Ancak, ortalama) O (1) için index = 0.

ArrayList<E>Diğer taraftan, hızlı rastgele okuma erişimine izin verin, böylece sabit bir zamanda herhangi bir elemanı yakalayabilirsiniz. Ancak, herhangi bir yerden başka bir yere eklemek ya da çıkarmak, ya bir açıklık oluşturmak ya da boşluğu doldurmak için tüm ikinci unsurları değiştirmeyi gerektirir. Ayrıca, temeldeki dizinin kapasitesinden daha fazla öğe eklerseniz, yeni bir dizi (boyutun 1,5 katı) atanır ve eski dizi yenisine kopyalanır. ArrayList olduğu O (n) en kötü durumda ancak ortalama sabit.

Yani yapmak istediğiniz operasyonlara bağlı olarak, uygulamaları buna göre seçmelisiniz. Her iki Listede tekrarlamak neredeyse eşit derecede ucuzdur. (Bir üzerinde yineleme ArrayList teknik olarak daha hızlıdır, ancak gerçekten performansa duyarlı bir şey yapmıyorsanız, bunun için endişelenmeyin - ikisi de sabittir.)

Kullanmanın başlıca faydaları LinkedList Öğeleri eklemek ve kaldırmak için mevcut yineleyicileri yeniden kullandığınızda ortaya çıkar. Bu işlemler daha sonra yapılabilir O (1) Listeyi sadece yerel olarak değiştirerek. Bir dizi listesinde dizinin geri kalanının olması gerekir. taşındı (yani kopyalandı). Diğer tarafta, bir LinkedList içindeki bağlantıları takip etmek anlamına gelir O (n) (n / 2 en kötü durum için) ArrayList İstenen pozisyon matematiksel olarak hesaplanabilir ve O (1).

Kullanmanın bir başka yararı LinkedList listenin başından eklediğinizde veya listeden çıkardığınızda ortaya çıkar, çünkü bu işlemler O (1), onlar O (n) için ArrayList. Bunu not et ArrayDeque iyi bir alternatif olabilir LinkedList kafa eklemek ve çıkarmak için, ama bir List.

Ayrıca, büyük listeleriniz varsa, bellek kullanımının da farklı olduğunu unutmayın. Her bir öğenin LinkedList Sonraki ve önceki öğelere işaretçiler de depolandığından daha fazla yüke sahiptir. ArrayLists Bu yükü yok. Ancak, ArrayLists Öğelerin gerçekten eklenip eklenmediğine bakılmaksızın, kapasite için ayrılan kadar bellek al.

Varsayılan başlangıç ​​kapasitesi ArrayList oldukça küçüktür (Java 1.4 - 1.8'den 10). Ancak, temeldeki uygulama bir dizi olduğu için, çok sayıda öğe eklerseniz dizi yeniden boyutlandırılmalıdır. Çok fazla eleman ekleyeceğinizi bildiğinizde yeniden boyutlandırma maliyetinden kaçınmak için ArrayList daha yüksek bir başlangıç ​​kapasitesi ile.


2847
2017-10-06 06:46



Ekleme maliyetlerinden bahsetmeyi unuttum. Bir BağlantılıListede, doğru konuma sahip olduğunuzda, ekleme maliyeti O (1) olurken, bir ArrayList öğesinde O (n) ye gider - ekleme noktasından geçen tüm öğeler taşınmalıdır. - David Rodríguez - dribeas
Vector kullanımıyla ilgili olarak: Gerçekten Vector'a geri dönmeye gerek yok. Bunu yapmanın yolu, tercih edilen Liste uygulamanız ve senkronize edilmiş bir sarıcı sağlamak için senkronizeListeye çağrıdır. Görmek: java.sun.com/docs/books/tutorial/collections/implementations/... - Ryan Cox
Hayır, bir LinkedList için, o pozisyonu bilseniz bile hala get O (n), çünkü o pozisyona ulaşmak için, alttaki uygulamanın o pozisyonun değerine ulaşmak için bağlantılı listenin "sonraki" işaretçisini yürümesi gerekir. Rastgele erişim diye bir şey yoktur. 2. pozisyon için, işaretçiyi yürümek ucuz olabilir, ancak 1 milyonluk konum için bu kadar ucuz değil. Buradaki nokta, O (n) anlamına gelen konumla orantılıdır. - Jonathan Tran
@Kevin Hafızanın "birbirine yakın" olması önemli olabilir. Donanım, bitişik bellek bloklarını (dinamik RAM) L1 veya L2 önbelleğinde daha hızlı statik RAM'e önbelleğe alacaktır. Teoride ve çoğu zaman pratikte, bellek rastgele erişim olarak ele alınabilir. Ama gerçekte, bellekten ard arda okumak, rastgele sıralamaya göre biraz daha hızlı olacaktır. Performans açısından kritik bir döngü için bu önemli olabilir. Buna "mekânsal yerellik" diyorlar ya da referans yeri. - Jonathan Tran
Diye bir şey yok O(n/2) veya O(n/4). Büyük O notasyonu nasıl bir operasyon olduğunu anlatıyor terazi daha büyük n. ve ihtiyaç duyulan bir operasyon n/2 adım tam olarak ihtiyaç duyulan bir işlem gibi ölçeklendirir n Sabit summandların veya faktörlerin kaldırılmasının nedeni olan adımlar. O(n/2) ve O(n/4) her ikisi de sadece O(n). LinkedList ve ArrayList yine de farklı sabit faktörlere sahip, bu yüzden karşılaştırmak için O(n/2) bir ile bir O(n/4) diğerinin ikisi de doğrusal olarak ölçekleme işlemlerini gösterir. - Holger


Şimdiye kadar, hiç kimse genel fikir birliği dışında bu listelerin her birinin bellek ayak izini ele almamıştı. LinkedList bir "daha çok" ArrayList Bu yüzden, her iki listenin N null referansları için tam olarak ne kadar yer aldığını göstermek için bir miktar çentikleme yaptım.

Referanslar, ilgili sistemlerinde 32 veya 64 bit (null olsa bile) olduğundan, 32 ve 64 bit için 4 set veri ekledim LinkedLists ve ArrayLists.

Not: İçin gösterilen boyutlar ArrayList satırlar içindir kesilmiş listeler - Uygulamada, destek dizisinin kapasitesi ArrayList genellikle mevcut eleman sayısından daha büyüktür.

Not 2:  (teşekkürler BeeOnRope) CompressedOops varsayılan olarak JDK6 ve yukarısında olduğundan, 64 bit'lik makineler için aşağıdaki değerler temel olarak 32 bitlik eş değerlerle eşleşecektir.


Graph of LinkedList and ArrayList No. of Elements x Bytes


Sonuç açıkça gösteriyor ki LinkedList çok daha fazlası ArrayListÖzellikle çok yüksek bir eleman sayısı ile. Bellek bir faktör ise, LinkedLists.

Kullandığım formüller, yanlış bir şey yapıp yapmadığımı bana bildirin. 'b', 32 veya 64 bit sistemler için 4 veya 8'dir ve 'n' öğelerin sayısıdır. Modların sebebinin, java'daki tüm nesnelerin tümü kullanılıp kullanılmadığına bakılmaksızın 8 baytlık bir alan kaplayacağıdır.

ArrayList:

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList:

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

535
2017-11-27 14:20



LinkedList öğesinin tek bir öğeyi depolamak için ArrayList kadar çok bellek gerektirdiğini görmek oldukça ilginç. Ne kadar belirsiz! Örneğinizi -XX: + UseCompressedOops ile çalıştırırsanız ne olur? - jontejj
Matematik ile ilgili problem, grafiğinizin etkisini büyük ölçüde abartmasıdır. Her biri sadece bir nesneyi içeren nesneleri modellediyorsunuz intYani, 4 veya 8 bayt veri. Bağlantılı listede, esas olarak 4 "kelime" vardır. Böylece grafiğiniz, bağlantılı listelerin dizi listelerinin depolanmasını "beş kez" kullandığı izlenimini verir. Bu yanlış. Ek yük, bir ölçekleme faktörü değil, bir ek ayar olarak, nesne başına 16 veya 32 bayttır. - Heath Hunnicutt
ArrayList / LinkedList / Node nesnelerinin hiçbiri yalnızca bir int içerir, bu yüzden orada söylediklerinizi anlamadım. 'Nesne üstbilgisini' nesne başlığına 'açıklığa kavuşturmak için yeniden canlandırdım - sisteme bakılmaksızın her nesne için bir 8 baytlık üstbilgi var, ve tüm Bağlantılı Nesne içerisindeki tüm düğüm nesnelerini içeren evet. söylemek. Bu arada, tekrar baktığımda, LinkedList'teki matematiğimde bir iki problem buldum. Bu da aslında onu bölen ve ArrayList. daha da kötüsü. Güncellemeye devam etmekten mutluluk duyuyorum, bu yüzden lütfen daha açık ve netleştirmek için tereddüt etmeyin. - Numeron
bu not alınmalı CompressedOops şimdi tüm yeni JDK'larda (7, 8 ve birkaç yıl için 6 güncellemeleri) varsayılan, bu yüzden 64-bit bir fark yaratmayacak ArrayList veya LinkedList Bazı nedenlerle sıkıştırılmış yongaları açıkça kapatmadığınız sürece, boyutlar. - BeeOnRope
Grafiğin bu resmi ticari kullanım için mevcut mu? Kullanmak isterim. - Ogen


ArrayList istediğin şey. LinkedList neredeyse her zaman bir (performans) hatasıdır.

Niye ya LinkedList berbat:

  • Çok sayıda küçük bellek nesnesi kullanır ve bu nedenle işlem boyunca performansı etkiler.
  • Küçük nesneler bir sürü önbellek yeri için kötüdür.
  • Endekslenmiş herhangi bir işlem, bir çaprazlama gerektirir, yani O (n) performansa sahiptir. Bu, kaynak kodunda açıkça görülmemekte, O (n) algoritmalara göre daha yavaş ArrayListkullanıldı.
  • İyi performans almak zor.
  • Büyük-O performansı aynı olsa bile ArrayListZaten büyük ihtimalle daha yavaş olacak.
  • Görmek sarsıcı LinkedList kaynakta muhtemelen yanlış bir seçim olduğu için.

190
2018-01-01 20:23



Afedersiniz. seni işaretledi. LinkedList emmiyor. LinkedList'in kullanılacak doğru sınıf olduğu durumlar vardır. Bir arraylistten daha iyi olduğu birçok durum olmadığına katılıyorum, ama varlar. Aptalca şeyler yapan insanları eğitin! - David Turner
Gördüğüm için üzgünüm, bunun için çok fazla oy aldınız. Java'nın LinkedList'ini kullanmak için çok az sebep var. Kötü performansa ek olarak, diğer somut List sınıflarından çok daha fazla bellek kullanır (her düğümün iki ek işaretçisi vardır ve her düğüm, onlarla birlikte gelen ek yük baytları olan ayrı bir sarmalayıcı nesnesidir). - Kevin Brock
Bu, burada en yararlı cevaplardan biridir. Pek çok programcının anlayamadığı bir utançtır (a) soyut veri tipleri ile somut uygulamalar arasındaki fark, ve (b) performansın belirlenmesinde sabit faktörlerin ve bellek yükünün gerçek dünyadaki önemi. - Porculus
-1: Bu oldukça göz kamaştırıcı bir görüntüdür. Evet, ArrayList'in çok yönlü bir araç olduğu doğrudur. Bununla birlikte, onun sınırlamaları vardır. Bunun sizin için sorun yaratacağı durumlar var ve LinkedList'i kullanmanız gerekecek. Tabii ki, çok özel bir çözümdür ve herhangi bir özel araç olarak çoğu durumda çok yönlü bir performansla daha iyi performans gösterir. Fakat bu, "berbat" ya da bunun gibi bir şey anlamına gelmez, sadece onu ne zaman kullanacağınızı bilmeniz gerekir. - Malcolm
@DavidTurner: Varlar ama sanırım Tom'un amacı, eğer sormak zorunda kalırsan, muhtemelen ArrayList'i istiyorsun. - Mehrdad


Yaklaşık on yıl boyunca çok büyük ölçekli SOA web servislerinde operasyonel performans mühendisliği yapan biri olarak, Bağlantılı Listenin ArrayList üzerindeki davranışını tercih ederim. LinkedList'in kararlı durum verimi daha kötüyse ve bu nedenle daha fazla donanım satın almaya yol açabilirken - ArrayList'in baskı altındaki davranışı, dizilerdeki uygulamaların yakın senkronizasyonda dizilerini genişletmesine ve büyük dizi boyutlarının da yanıt vermemesine yol açabilir. uygulama ve bir kesinti, baskı altında iken, felaket davranışları.

Benzer şekilde, varsayılan çıkışlı tenured çöp toplayıcısından bir uygulamada daha iyi bir getiri elde edebilirsiniz, ancak 10GB yığınlar ile java uygulamalarını aldıktan sonra 25 saniye boyunca uygulamayı kilitleyen tam bir GC'ler sırasında SOA uygulamalarında zaman aşımına ve arızalara neden olabilirsiniz ve çok sık görülürse SLA'larınızı üfler. CMS toplayıcısı daha fazla kaynak alsa ve aynı ham çıktıya ulaşmasa da, daha öngörülebilir ve daha küçük gecikme olduğu için çok daha iyi bir seçimdir.

ArrayList, performansla elde etmek istediğiniz her şey çıktılanırsa ve gecikmeyi göz ardı ederseniz, yalnızca performans için daha iyi bir seçimdir. Benim işimdeki tecrübemde, en kötü durum gecikmesini göz ardı edemem.


125
2018-04-08 20:33



ArrayList'in warrantyCapacity () yöntemini kullanarak programın büyüklüğünü program aracılığıyla yönetmenin başka bir çözümü olmaz mı? Sorum şu: bir sürü kırılgan veri yapısında saklanabilecek bir şeyleri saklamak için neden bir önbellek veya db mekanizmasında saklanabiliyorlar? Geçen gün ArrayList'in kötülükleri hakkında aşağı yukarı yemin ettikleri bir röportaj yaptım, ama buraya geldim ve karmaşıklık analizinin daha iyi olduğunu düşünüyorum! TARTIŞMA İÇİN BÜYÜK NOKTASI, DÜŞÜNÜYOR. TEŞEKKÜRLER! - ingyhere
10GB yığınları ile java uygulamalarını aldıktan sonra, zaman aşımına neden olan Tam GC'ler sırasında 25 saniye boyunca uygulamayı kilitleyebilir Aslında LinkedList ile tüm GC'ler sırasında çöp toplayıcısını öldürdüğünüzde, her bir düğümde aşırı büyük LinkedList'i önbellek öznesiyle yinelemek zorunda. - bestsss
Bu ... korkunç bir çözüm. temelde sizin için GC temizlemeye güveniyorsunuz, ki bu inanılmaz pahalı bir şeydir, bunun yerine arraylist üzerinde ... - Philip Devine
@Andreas: A LinkedList  her zaman belleğin beş katını düz bir referans dizisinden ayırır. ArrayList geçici olarak 2,5 kat gerektiren bellek hala geri alınmazken bile daha az bellek tüketir. Büyük dizi ayırma Eden alanını atladığından, gerçekten yeterli bellek olmadıkça, GC davranışı üzerinde herhangi bir etkisi yoktur. LinkedList Daha önce havaya uçuruldu… - Holger
@Andreas Diğer konu hafızanın nasıl tahsis edildiğidir. LinkedListBir sonraki öğeye ayırmak için yalnızca küçük bir boş bellek parçası gerekir. ArrayList büyük olmalı ve sürekli yeniden boyutlandırılmış diziyi ayırmak için boş alan bloğu. Yığın parçalanmaya başlarsa, o zaman GC sadece uygun bir tek bellek bloğunu boşaltmak için tüm yığını yeniden sıralayabilir. - Piotr Kusmierczyk


Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Algoritmalar: Büyük-Oh Notasyonu

ArrayLists, bir kez yazma-okuma-çok veya ekleri için iyidir, ancak ön / ortadan ekleme / çıkartmada kötüdür.


111
2018-05-19 11:21



Büyük-O değerlerini sabit faktörleri düşünmeden doğrudan karşılaştıramazsınız. Küçük listeler (ve çoğu liste küçük) için, ArrayList's O (N), LinkedList'in O (1) 'den daha hızlıdır. - Porculus
Küçük listeler performansı umurumda değil ve bilgisayarım da yok olmadıkça bir şekilde bir döngüde kullanılır. - Maarten Bodewes
LinkedList gerçekten ortadakileri ekleyemez O(1). Ekleme noktasını bulmak için listenin yarısından geçmelidir. - Thomas Ahle
LinkedList: ortadaki yuvaya ekle O (1) - YANLIŞ! LinkedList boyutunun 1 / 10'luk konumuna yerleştirmenin bile, bir elemanı bir ArrayList'in 1 / 10'luk konumuna yerleştirmekten daha yavaş olduğunu öğrendim. Ve daha da kötüsü: koleksiyonun sonu. ArrayList'in son konumlarına (sonuncusunu değil) eklemek, daha sonra LinkedList'in son pozisyonlarına (sonuncusu değil) daha hızlıdır. - kachanov
kachanov ekleme LinkedList  olduğu  O(1)  ekleme pozisyonuna bir yineleyiciniz varsayani ListIterator.add sözde O(1) bir için LinkedList. - Anony-Mousse


Evet, biliyorum, bu eski bir soru, ama iki sentimde atacağım:

LinkedList şudur neredeyse her zaman Yanlış seçim, performans açısından. Bir BağlantılıListenin çağrıldığı bazı çok özel algoritmalar vardır, ancak bunlar çok, çok nadirdir ve algoritma özellikle de Bağlantılı Listenin öğelerin ortasında hızlı bir şekilde ekleme ve silme özelliklerine bağlıdır. ListIterator ile.

LinkedList'in ArrayList'den daha iyi performans gösterdiği ortak bir kullanım durumu vardır: bir sıradaki. Ancak, hedefiniz performans ise, BağlantılıList yerine, bir ArrayBlockingQueue kullanmayı da düşünmeniz gerekir (eğer zaman sınırında bir üst sınır belirleyebilirseniz ve tüm belleği ön tarafa ayırabiliyorsa) veya CircularArrayList uygulaması. (Evet, 2001'den beri, bu yüzden bunu genetikleştirmeniz gerekecek, ancak şu anda yeni bir JVM'de makalede alıntılananlara benzer performans oranları elde ettim)


92
2017-11-27 01:39



Java 6'dan kullanabilirsiniz ArrayDeque. docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html - Thomas Ahle
ArrayDeque daha yavaş LinkedList Tüm işlemler aynı anda olmadıkça. Bir yığın olarak kullanıldığında sorun değil ama iyi bir sıra yapmaz. - Jeremy List
Untrue - en azından Oracle'ın jdk1.7.0_60 sürümünde ve aşağıdaki testte uygulanması için. 10 milyon kere döngü yaptığım bir test yaptım ve 10 milyon rastgele Tamsayı bir Deque'im var. Döngüsün içinde bir elementi yokladım ve sabit bir eleman sunuyoruz. Bilgisayarımda, LinkedList, ArrayDeque'den 10 kat daha yavaş ve daha az bellek kullanıyor). Bunun nedeni, ArrayList'ten farklı olarak, ArrayDeque dizinin başına bir işaretçi tutar, böylece kafa çıkarıldığında tüm öğeleri taşımak zorunda kalmaz. - Henno Vermeulen
ArrayDeque daha hızlı olması muhtemeldir Stack bir yığın olarak kullanıldığında ve daha hızlı LinkedList sıra olarak kullanıldığında. - i_am_zero
Akhil_mittal'in yorumunun bir alıntı olduğunu unutmayın. ArrayDeque dokümantasyon. - Stuart Marks


Bu bir verimlilik sorusu. LinkedList eleman eklemek ve silmek için hızlıdır, ancak belirli bir öğeye erişmek yavaştır. ArrayList belirli bir öğeye erişmek için hızlıdır, ancak her iki tarafa da eklenmesi yavaş olabilir ve özellikle ortada yavaşça silinebilir.

ArrayList vs LinkedList vs Vector dizisiolduğu gibi daha da derinleşir Bağlantılı liste.


50
2017-09-21 22:59





Doğru veya Yanlış: Lütfen testi yerel olarak yürütün ve kendiniz karar verin!

Düzenle / Kaldır daha hızlıdır LinkedList göre ArrayList.

ArrayList, tarafından desteklenen Arraybüyüklüğü olan uygulamada boyutu iki katına çıkması gerekir.

Aşağıda, her işlem için birim test sonucu verilmiştir. Sürme, Nanosaniye cinsinden verilmiştir.


Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

İşte kod:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}

49
2018-04-21 00:03



ArrayList'in kesin olması için iki katına çıkmasına gerek yok. Lütfen önce kaynakları kontrol edin. - Danubian Sailor
Örneğinizin kusurlu olduğuna dikkat edilmelidir ... 18 + [2, 12] bytes ("true0false", "true500000false") arasındaki dizgeden kaldırılıyorsunuz, öğelerin boyutları olan ortalama 25 bayttır. ortada. Öğe boyutu arttıkça, öğe bayt boyutu arttıkça, listenin boyutu arttıkça, bitişik bir dizinin (liste) daha iyi performans göstereceği bilinmektedir. En önemlisi, dizeleri üzerinde .equals () yapıyorsunuz - bu ucuz bir işlem değil. Bunun yerine tamsayılar kullanırsanız, bir fark olacağını düşünüyorum. - Centril
- ve muhtemelen bu yüzden de / remove için çok az fark var. - Centril
" ... büyük hacimli uygulamada daha kötü": Bu bir yanlış anlaşılma. LinkedList çok daha fazla bellek yüküne sahiptir, çünkü her öğe için beş alanlı bir düğüm nesnesi vardır. 20 bayt yükü yapan birçok sistemde. Öğe başına ortalama bellek yükü ArrayList en kötü durumda 6 bayt ve 8 bayt yapan bir buçuk kelimedir. - Lii
Testinizin daha iyi bir versiyonunu yaptım burada, sonuçlarla - Arraylist için ek performans, sizinki için yapay olarak düşüktür, çünkü addAll EXACTLY başlangıç ​​boyutunda bir depolama dizisi verir, böylece ilk insert her zaman bir arraycopy'i tetikler. Ayrıca, bu veriler toplanmadan önce JIT derlemesine izin vermek için ısınma döngülerini içerir. - BobMcGee


ArrayList aslında bir dizidir. LinkedList çift ​​bağlantılı bir liste olarak uygulanır.

get oldukça açık. O için (1) ArrayList, Çünkü ArrayList indeksi kullanarak rastgele erişime izin verin. O (n) için LinkedListÇünkü önce dizini bulması gerekiyor. Not: farklı sürümleri vardır add ve remove.

LinkedList ekleme ve kaldırmada daha hızlıdır, ancak daha yavaştır. Kısaca, LinkedList aşağıdaki durumlarda tercih edilmelidir:

  1. çok sayıda rastgele eleman erişimi yok
  2. çok sayıda ekleme / çıkarma işlemi var

=== ArrayList ===

  • ekle (E e)
    • ArrayList öğesinin sonuna ekle
    • hafıza yeniden boyutlandırma maliyeti gerektirir.
    • O (n) en kötü, O (1) itfa edilmiş
  • ekle (int indeksi, E öğesi)
    • belirli bir dizin pozisyonuna ekle
    • vites değiştirme ve olası bellek yeniden boyutlandırma maliyeti gerektirir
    • O (n)
  • kaldır (int dizini)
    • belirtilen bir elemanı kaldırmak
    • vites değiştirme ve olası bellek yeniden boyutlandırma maliyeti gerektirir
    • O (n)
  • kaldır (Nesne o)
    • Belirtilen öğenin ilk oluşumunu bu listeden kaldır
    • önce öğeyi aramalı ve ardından değişen ve yeniden boyutlandıran bellek yeniden boyutlandırma maliyeti
    • O (n)

=== Bağlantılı liste ===

  • ekle (E e)

    • listenin sonuna ekle
    • O (1)
  • ekle (int indeksi, E öğesi)

    • belirtilen pozisyona ekle
    • önce pozisyonu bulmalıyız
    • O (n)
  • Kaldır()
    • listenin ilk elemanını kaldır
    • O (1)
  • kaldır (int dizini)
    • öğeyi belirtilen dizinle kaldır
    • önce öğeyi bulmalıyım
    • O (n)
  • kaldır (Nesne o)
    • Belirtilen öğenin ilk oluşumunu kaldır
    • önce öğeyi bulmalıyım
    • O (n)

İşte bir rakam programcreek.com (add ve remove ilk türdür, yani listenin sonuna bir eleman ekler ve öğeyi listede belirtilen konumdan kaldırır.):

enter image description here


38
2017-11-27 01:41



"LinkedList eklemek / kaldırmaktan daha hızlıdır". Yanlış, yukarıdaki cevabı kontrol et stackoverflow.com/a/7507740/638670 - Nerrve


ArrayList rasgele erişilebilir iken LinkedList öğeleri genişletmek ve kaldırmak için gerçekten ucuz. Çoğu durumda, ArrayList iyi.

Büyük listeler oluşturmamışsanız ve bir darboğaz ölçmediyseniz, muhtemelen hiçbir zaman bu konuda endişelenmenize gerek kalmayacaktır.


30
2017-07-07 09:22



LinkedList öğeleri eklemek için ucuz değildir. ArrayList'e bir milyon öğesi eklemek, onları bir BağlantılıListeye eklemekten çok daha hızlıdır. Ve gerçek dünyadaki koddaki çoğu liste, milyonlarca eleman bile uzun değildir. - Porculus
Herhangi bir noktada, LinkedList öğenize bir öğe ekleme maliyetini biliyorsunuz. ArrayList yok (genel olarak). Bir milyon öğe içeren bir ArrayList'e tek bir öğe ekleme could Çok uzun bir zaman ayırın - bir O (n) işlemi artı alan ayırdığınız sürece depolamayı ikiye katlayın. Bir LinkedList öğesine bir öğe eklemek O (1). Son ifadem duruyor. - Dustin
Bir ArrayList'e tek bir öğe eklemek O (1) 1 milyon veya 1 milyar olursa olsun. Bir LinkedList'e bir öğe eklemek de O (1) 'dir. "Ekleme" END'E EKLEMEK anlamına gelir. - kachanov
Uygulamayı benden farklı bir şekilde okumalısınız. Benim deneyimime göre, 1 milyar eleman dizisini kopyalamak 1 milyon eleman dizisini kopyalamaktan daha uzun sürüyor. - Dustin
@kachanov'u yanlış anlamalısın Dustin. 1 milyardan fazla dizi ilan etmediğiniz sürece, dizininizi yeniden boyutlandırmanız gerekecektir. Bu durumda, tüm öğeleri yeni bir büyük diziye kopyalamanız gerekecektir. Bu nedenle, bazen O (N) değerini alırsınız. O olsun (1) - Stan R.